Quicksort doesn't work on odd numbered arrays

[Extreme112]

As the title explains above I'm trying to implement Quicksort but it doesn't seems to work in odd numbered cases. I'd like for someone to see what condition I'm not checking correctly. I've been at it for a few hours and can't quite get it.

Thanks.

#include <iostream>

using namespace std;

template <class T>
void QuicksortHelper(T arr[], int low, int high,int &counter);
template <class T>
int QSPartition(T arr[], int low, int high,int &counter);

//n is the size of array
template <class T>
int Quicksort(T arr[], int n)
{
	int count = 0;
	QuicksortHelper(arr, 0, n - 1,count);
	return count;
}

template <class T>
void QuicksortHelper(T arr[], int low, int high,int &counter)
{
	if (low < high) {
		int partitionLocation = QSPartition(arr, low, high,counter);
		QuicksortHelper(arr, low, partitionLocation,counter);
	
		QuicksortHelper(arr, partitionLocation + 1, high,counter);
		
	}
}

//parition works
template <class T>
int QSPartition(T arr[], int low, int high,int &counter)
{
	int pivotindex = low;           //set pivot index to beginning of subarray
	T pivot = arr[high];			//stores the number of the last element in arr

	for (int j = low + 1; j < high; j++) {
		counter++;
		if (arr[j] <= pivot) {
			//swap pivotindex and j
			T temp = arr[pivotindex];
			arr[pivotindex] = arr[j];
			arr[j] = temp;
			//end of swap
			pivotindex++;
		}
	}
    //swap last element with pivotindex

//    if(pivotindex == (high - 1)){
//        //...Do nothing
//    } else
    if (arr[pivotindex] > arr[high]){
        T temp2 = arr[pivotindex];
        arr[pivotindex] = arr[high];
        arr[high] = temp2;
    }


    cout << "Pivot Returned:" << pivotindex << endl;
	return pivotindex;
}

void Test_Quicksort() {
	std::cout << "Original array:" << std::endl;
	int size = 9;
	int arr[size] = { 7,2,1,6,8,5,3,4,0};
	//Print array
	for (int i = 0; i <size; i++) {
		std::cout << arr[i] << ',';
	}
	std::cout << std::endl;

	Quicksort(arr, size);
	//Print array
	for (int i = 0; i < size; i++) {
		std::cout << arr[i] << ',';
	}
	std::cout << std::endl;
;
}
int main()
{
    Test_Quicksort();
}

[jgg2002]

Your T pivot = arr[high] . I think it should be arr[high-1] ?

[Extreme112]

Trying out your suggestion doesn't work. pivot = the last element in the array, which is high. I changed my code and tested it out just to be sure. Thanks for taking a look though.

[jgg2002]

#include<iostream>
using namespace std;
void swapt(int i,int j, int *a){
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}


void quicksort(int *arr, int left, int right){
    int min = (left+right)/2;
    cout<<"Pivot returned:"<<left<<","<<right<<"\n";

    int i = left;
    int j = right;
    int pivot = arr[min];

    while(left<j || i<right)
    {
        while(arr[i]<pivot)
        i++;
        while(arr[j]>pivot)
        j--;

        if(i<=j){
            swapt(i,j,arr);
            i++;
            j--;
        }
        else{
            if(left<j)
                quicksort(arr, left, j);
            if(i<right)
                quicksort(arr,i,right);
            return;
        }
    }
}


int main() {
    int arr[8] = {110, 5, 10,3 ,22, 100, 1, 23};
    quicksort(arr, 0, (sizeof(arr)/sizeof(arr[0]))-1);
    for (int i=0; i<8; i++){
        cout<<arr[i]<<" ";
    }
    return 0;
}