Quick Sort Array in C++
// Mon 27 Feb 15:03:30 2023
// FIX: a bug on pInx
int partitionX(int array[], int lo, int hi) {
int p = array[hi];
int pInx = lo;
for(int i=lo; i<=hi; i++) {
if(array[i] <= p) {
swap(array, i, pInx);
if(i != hi)
pInx++;
}
}
return pInx;
}
void quickSortX(int array[], int lo, int hi) {
if(lo < hi) {
int pInx = partition(array, lo, hi);
quickSortX(array, lo, pInx - 1);
quickSortX(array, pInx + 1, hi);
}
}
Quick Sort Vector in C++
Importent: Pass reference of vector
In Java, parameter is passed by reference in function.
In C++, parameter is passed by value in function
int partition(vector &vec, int lo, int hi){
int ret = 0;
int pivot = vec[hi];
int j = -1;
for(int i = 0; i < vec.size(); i++){
if(vec[i] <= pivot){
j++;
swap(vec, i, j);
}
}
return j;
}
void quickSort(vector &vec, int lo, int hi){
if(lo < hi){
int pInx = partition(vec, lo, hi);
quickSort(vec, lo, pInx - 1);
quickSort(vec, pInx + 1, hi);
}
}
void swap(vector &vec, int i, int j){
int tmp = vec[i];
vec[i] = vec[j];
vec[j] = tmp;
}