Here's my second program in C, and my time/space analysis of this code.
I have been reading Modern C and I attempted this challenge on page 26. The prior pages are pretty much the only exposure I have had to C, for reference. I have a rough understanding of pointers but I have read no formal material on the subject.
Ideas which I have not yet encountered
- test harnesses
- function contracts
- array slices
#include <stddef.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
// sort the subset of array whose first and last elements have indexes range_start and range_end, respectively
void quick_sort(size_t range_start, size_t range_end, double array[]) {
// the sub-array is trivially sorted, or has size 0
if (range_start >= range_end) {
return;
}
double current_element = array[range_start];
double const pivot = array[range_end];
// the array is overwritten at these indicies
size_t free_lower_index = range_start;
size_t free_upper_index = range_end;
while (free_lower_index + 1 < free_upper_index) {
if (current_element >= pivot) {
array[free_upper_index] = current_element;
current_element = array[--free_upper_index];
} else {
array[free_lower_index] = current_element;
current_element = array[++free_lower_index];
}
}
// now, free_lower_index and free_upper_index are adjacent
if (current_element >= pivot) {
array[free_lower_index] = pivot;
array[free_upper_index] = current_element;
} else {
array[free_lower_index] = current_element;
array[free_upper_index] = pivot;
}
// the elements in the lower subarray are all < pivot
quick_sort(range_start, free_lower_index, array);
// the elements in the upper subarray are all >= pivot
quick_sort(free_upper_index, range_end, array);
}
// returns true if the input is sorted
bool self_test(size_t num_elements, double array[num_elements]) {
for (size_t i = 0; i < num_elements-1; ++i) {
if (array[i] > array[i+1] ) {
return false;
}
}
return true;
}
int main(int argc, char* argv[argc+1]) {
printf("you want me to sort an array of length %d?\n", argc-1);
if (argc < 2) {
printf("you must provide at least one double to be sorted!\n");
return EXIT_FAILURE;
}
// allocate some memory to store an appropriate number of double values
double A[argc-1];
// process args
char* err;
for (size_t i = 1; i < argc; ++i) {
// arg -> double
double const a = strtod(argv[i], &err);
if (*err != 0) {
printf("bad input! %s isn't a valid double\n", argv[i]);
return EXIT_FAILURE;
}
A[i-1] = a;
}
// quick sort!
// the input array has length argc-1, so the last element has index argc-2
quick_sort(0, argc-2, A);
printf("here is your sorted array:\n");
for (size_t i = 0; i < argc - 1; ++i) {
printf("%f\n", A[i]);
}
if (self_test(argc-1, A)) {
printf("self-test passed\n");
} else {
printf("self-test failed\n");
return EXIT_FAILURE;
}
return EXIT_SUCCESS;
}
Complexity analysis
Here, I will assume the average case scenario, where the pivot element happens to be the median element of each sub-array to be sorted.
For ease of calculation I will also assume that n, the number of elements to be sorted, is an exact power of 2.
Time complexity
In each call to quick_sort, the pivot element is compared to every other element of the sub-array to be sorted, so this is roughly k comparisons, where k is the length of the sub-array.
With each recursive call, k shrinks by a factor of 2. But the number of recursive calls with this k also grows by a factor of 2.
So in total, the number of comparisons is: n + 2*(n/2) + 4*(n/4) + ... + n*(n/n)
This is n*ln(n) comparisons, so the time complexity is O(n*ln(n)) in the average case.
Space complexity
We require O(n) space for parsing arguments.
Given the assumptions above, quick_sort is called to a maximum depth of ln(n). In each call, we only require constant space.
So the space complexity is O(ln(n)) in the average case, ignoring the space required for parsing arguments.
