c++ quicksort pivots

Question

Is this code for quicksort using the first index as a pivot correct? Also if I want to use the last or middle index as a pivot how would the whole code change?

#include <iostream>
using namespace std;
void quicksort(int list[], int arraySize);
void quickSort(int list[], int first, int last);
int partition(int list[], int first, int last);
void quickSort(int list[], int arraySize) {
 quickSort(list,0, arraySize - 1);
}
void quickSort(int list[], int first, int last) {
 if (first < last) {
 int pivotIndex = partition(list, first, last);
 quickSort(list, first, pivotIndex -1); 
 quickSort(list, pivotIndex + 1, last);
 }
}
int partition(int list[],int first, int last) {
 int pivot = list[first];
 int low = first + 1;
 int high = last;
 do {
 while(low <= high && list[low] <= pivot) 
 low++;
 while(low <= high && list[high] > pivot)
 high--;
 if (low < high) {
 int temp = list[low];
 list[low] = list[high];
 list[high] = temp;
 }
 } while (low <= high);
 int temp = list[high];
 list[high] = list[first];
 list[first] = temp;
 return high;
}

• Toby Speight: Your second question is off-topic - if you want to change the specification of your code, we can't help you. We can just review the code you have written and make suggestions for worthwhile improvements.

Answer 1

The algorithm appears to be correct. When the loop terminates, either list[high] <= pivot, or high == first (and consequently also list[high] <= pivot).

Since you are copying the pivot value to a variable, you could simplify the code by starting with low = first and omitting the last swap with the pivot element in the end. You'll have to tweak the loop a bit to get it to work. This also provides you with an answer to your second question.

The declaration of quicksort() has different case from the definition quickSort().

Since you are writing C++, not plain C, you should use std::swap() to swap elements.

You should use the type std::ptrdiff_t for array indices instead of int. I.e. for first, last, pivotIndex, etc.

Since this is C++, you could consider writing it as a template function to make it usable with types other than int.