I am trying to understand Quick sort algorithm and implement it in C language. I found this code in programiz;
// Quick sort in C
#include <stdio.h>
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
int partition(int array[], int low, int high) {
int pivot = array[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (array[j] <= pivot) {
i++;
swap(&array[i], &array[j]);
}
}
// please note Here!!!!!
swap(&array[i + 1], &array[high]);
return (i + 1);
}
void quickSort(int array[], int low, int high) {
if (low < high) {
int pi = partition(array, low, high);
quickSort(array, low, pi - 1);
quickSort(array, pi + 1, high);
}
}
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
int main() {
int data[] = {8, 7, 2, 1, 0, 9, 6};
int n = sizeof(data) / sizeof(data[0]);
quickSort(data, 0, n - 1);
printf("Sorted array in ascending order: \n");
printArray(data, n);
}
This code is working. But I can't understand why they iterate upto <high in partition function and do the final swap in another step. Instead why don't they just go like this;
int partition(int array[], int low, int high) {
int pivot = array[high];
int i = (low - 1);
for (int j = low; j <= high; j++) {
if (array[j] <= pivot) {
i++;
swap(&array[i], &array[j]);
}
}
return (i);
}
I checked geeksforgeeks also. They also have the same code. That's why I ask this. Please help me