Quick Sort troubleshooting (C++)

Question

I need to measure the amount of time it takes a system to perform a sorting algorithm. I have got everything to work except for quick sort. side note, I can't figure out how to measure time in milliseconds so if anyone knows how to do that I'm all ears. Basically, to counteract this I need to use massive arrays. The problem is that when using arrays above around 500-1000, my quick sort algorithm fails. I don't get any stack overflow errors anymore but it keeps running for obscene amounts of time (for doing a function). I have seen it run for over 40 or 50 seconds a couple times. I am not sure how to optimize/fix the code. I have been troubleshooting for a while.

I expect the function to run every time I run the code. I have tried messing around with the while loop in partition, adjusting the recursion start/end inputs. The smaller side first optimization doesn't seem to run at all (maybe I did it wrong though). Any tips would be greatly appreciated, thanks!

You need all of the code given along with an input array, and size variable for the function to work.

Here is the quick sort algorithm:

//partitioning for quick sort
int partition(int arr[], int start, int end) {
    int pivot = arr[start]; //array is randomly generated, so pivot selection is trivial
    int i = start + 1;
    int j = end;

    while (i < j) { //While I is less than J, increment closer to the pivot until a suitable switch is found.
        while (i <= j && arr[i] < pivot)
            i++;
        while (i <= j && arr[j] > pivot)
            j--;
        if (i < j)
            swap(arr, i, j);    //suitable match found, switch i and j only if theyre not out of scope of their proper placement
        else
            break;
    }
    swap(arr, start, j);    //put pivot in its correct position

    return j;
}

//Recursive Function for quick sort
void quickSort(int arr[], int start, int end) {
    if (start < end) { //as long as the array length is more than 1, continue recursing
        int p = partition(arr, start, end);

        if (p > start)
            quickSort(arr, start, p - 1); // Left side recursion
        if (p < end)
            quickSort(arr, p + 1, end); //right side recursion
    }
}

int main() {
//initialization of arrays, and array qualities
    const int size = 20000;
    int max = 0x80000000;
    int min = 0x7FFFFFFF;
    int *arr = new int [size];
    int *arrC1 = new int[size];
    int *arrC2 = new int[size];
    int *arrC3 = new int[size];
    int *arrC4 = new int [size];
    bool passed = true;
    bool sameArr = true;

//Random generation seeded by the time of day
    srand(static_cast<unsigned>(time(0)));

// Creation and printing of unsorted array  
    for (int i = 0; i < size; i++) {
        arr[i] = rand();
    }


//copying of array, along with ensuring they are the same
    for (int i = 0; i < size - 1; i++) {
        arrC1[i] = arr[i];
        arrC2[i] = arr[i];
        arrC3[i] = arr[i];
        arrC4[i] = arr[i];
    }
    for (int i = 0; i < size - 1; i++) {
        if (arr[i] != arrC1[i] || arrC1[i] != arrC2[i] || arrC2[i] != arrC3[i] || arrC3[i] != arrC4[i])
            sameArr = false;
    }
    cout << "Same Array (1 for true, 0 for false)? " << sameArr << endl;


//Run and test Quick sort algorithm
    passed = true;  //reset bool for further use

    start = getTime();
    quickSort(arrC2, 0, size - 1);
    finish = getTime();

    cout << "QUICK SORT:_______________" << endl;
    cout << "Time Elapsed:          " << chrono::duration_cast<chrono::milliseconds>(finish - start).count() << endl;
    for (int i = 1; i < size - 1; i++) {
        if (arrC2[i - 1] > arrC2[i])
            passed = false;
    }
    cout << "Array ordering: " << passed << endl;




    delete[] arr;
    delete[] arrC1;
    delete[] arrC2;
    delete[] arrC3;
    delete[] arrC4;
    return 0;
}

Answer 1

The issue you're facing is likely due to the fact that QuickSort has a worst-case time complexity of O(n^2) when the input array is already sorted or nearly sorted. This is because the pivot selection strategy you're using (always choosing the first element) results in very unbalanced partitions in these cases.

To improve the performance of QuickSort, you can use a better pivot selection strategy, such as choosing the median of the first, middle, and last elements of the array. This will result in more balanced partitions and a better average-case time complexity.

Here's how you can modify your partition function to use this pivot selection strategy:

int partition(int arr[], int start, int end) {
    // Choose the median of the first, middle, and last elements as the pivot
    int mid = start + (end - start) / 2;
    int pivotIndex = (arr[start] < arr[mid]) == (arr[mid] < arr[end]) ? mid
                     : (arr[start] < arr[end]) == (arr[end] < arr[mid]) ? end : start;
    int pivot = arr[pivotIndex];

    // Swap the pivot with the first element
    swap(arr, start, pivotIndex);

    // Rest of the function remains the same...
}

As for measuring time in milliseconds, you're already doing it correctly with chrono::duration_cast<chrono::milliseconds>(finish - start).count(). This will give you the elapsed time in milliseconds.