//Time Complexity from O(n log(n)) to O(n^2)
//Space Complexity O(log(n))
//elements less than the middle one go left, greater go right,
//then each part is sorted the same way
void quickSort(int arr[], int first, int last) {
if (first >= last) {
return;
}
int i = first;
int j = last;
int x = arr[first + (last - first) / 2];
while (i <= j) {
while (arr[i] < x) {
i++;
}
while (arr[j] > x) {
j--;
}
if (i <= j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
quickSort(arr, first, j);
quickSort(arr, i, last);
}
void printArray(const char *name, const int arr[], size_t count) {
printf("%s is {", name);
for (size_t i = 0; i < count; i++) {
if (i > 0) {
printf(", ");
}
printf("%d", arr[i]);
}
printf("}\n");
}
int items[] = {4, 1, 5, 3, 2};
size_t count = sizeof items / sizeof items[0];
//the sort works in place: a copy keeps items as they are
int sortItems[5];
memcpy(sortItems, items, sizeof items);
quickSort(sortItems, 0, (int)count - 1);
//sortItems is {1, 2, 3, 4, 5}
//the library qsort sorts an array of any type
printArray("items", items, count);
printArray("sortItems", sortItems, count);