QuickSort (c++)

Quicksort is a popular sorting algorithm. It runs in O(n log n). The sort is not stable meaning equal values may not appear in the same order. For this post we'll write a simple quick sort implementation.

Lets start with the entire code listing then we'll break it apart:

void swap(int &a, int &b) {
    int temp = a ;
    a = b;
    b = temp;
}

int partition(int * arr,int left, int right, int pivotIndex) {
    int pivotValue = arr[pivotIndex];
    swap(arr[right],arr[pivotIndex]);
    int storeIndex = left;
    for (int i=left;i<right -1; ++i) {
        if (arr[i] < pivotValue) {
            swap(arr[i],arr[storeIndex]);
            storeIndex++;
        }
    }
    swap(arr[storeIndex],arr[right]);
    return storeIndex;
}

void quicksort(int * arr, int left , int right) {
    if  (right > left) {
        int pivotIndex = left;
        int pivotNewIndex = partition(arr,left,right,pivotIndex); 
        quicksort(arr,left,pivotNewIndex-1);
        quicksort(arr,pivotNewIndex+1,right);
    }
    
}


int main(int argc, char** argv) {
    int arr[10] = { 3, 6, 1, 5, 3, 2, 6, 8, 9, 6};
    quicksort(&arr[0],0,9);
    for(int i = 0 ; i < 10; ++i) {
        printf("%d" , arr[i]);
    }
}

We have 3 methods not including main. Swap is a utility method that swaps the values.

The heart of the algorithm is the partition method. We choose value in the array and do a O(n) walk of the list putting all elements with value less than the chosen value before and all elements greater than the chosen value after the value. Our code is optimized to do it in place without requiring an extra array by moving the pivot to the end and then swapping it back at the end.

Once we have the partition method we simply recursively call quicksort and the list will be sorted.