Schnelle Sorte

#include  #include  #include  void _quick_sort(uint32_t *arr, size_t low, size_t high); void quick_sort(uint32_t *arr, size_t size); int32_t main(void) { uint32_t list[] = {1, 4, 5, 10, 2, 9, 17, 100, 4, 2, 1000}; // 11 is the number of elements list has // this is really usefull, because whenever we pass an array to a function, it decays as a pointer // due to this, if the function is in another translation layer it won't be able to know, so it can do the // sizeof(list) / sizeof(list[1]) trick quick_sort(list, 11); for (size_t i = 0; i < 11; ++i) { printf("%u ", list[i]); } return EXIT_SUCCESS; } // Just a helper to have a cleaner interface void quick_sort(uint32_t *arr, size_t size) { // Note: here we are passing the high bound as the size - 1, // so in here we are having an inclusive range // this is important because it makes the algorithm slightly simpler // and it requires less -1's which usually causes a lot of off-by one mistakes _quick_sort(arr, 0, size - 1); } size_t partition(uint32_t *arr, size_t low, size_t high) { // Partition is the operation that puts all the elements smaller than the pivot // We are picking the last element as the pivot always, // I guess we could be more clever and pick a random element // or the median of the first, middle and last elements // but this is just a simple example size_t pivot_index = high; uint32_t pivot = arr[pivot_index]; // This is going to be the index of the pivot at the end // of the loop size_t i = low; for (size_t j = low; j <= high; ++j) { // If the current element is less than the pivot, // we swap it with the element at index i // and increment i, // doing this we will know exacyly where the pivot // should be placed after the iteration is done // because all the elements of index < i are less than the pivot // and all the elements of index > i are greater than the pivot // so we just need to swap the pivot with the element at index i if (arr[j] < pivot) { uint32_t temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; ++i; } } // putting the pivot at the right spot, remember, it could've been anywhere arr[pivot_index] = arr[i]; arr[i] = pivot; return i; } void _quick_sort(uint32_t *arr, size_t low, size_t high) { // The main idea of this function, is to use a window, that has the bounds // [low, high] inclusive, so if the window has length 0, low = high // it means we reached our base case, and the list is already sorted // since an array without elements is always going to be sorted // I guess if (low >= high) { return; } // The pivot index is the index of the pivot element after partitioning, // so it means that the list is weakly sorted around the pivot, // (i.e. all elements to the left of the pivot are less than the pivot) // and all elements to the right are greater then size_t pivot_index = partition(arr, low, high); // Here we have a cool implementation detail // since pivot_index is a size_t, it is unsigned // and if we subtract 1 from an unsigned 0, // we get undefined behavior // This would happen, if the last element should be the first // in this case, no sorting is necessary, since there is nothing // before it if (pivot_index > 0) { // Sorting the left hand window // they have the bounds, [low, pivot_index - 1] // the -1 is so it is inclusive // because we now know the pivot is in the right spot _quick_sort(arr, low, pivot_index - 1); } // Same thing with before, now, we are sorting the right side of the window _quick_sort(arr, pivot_index + 1, high); }