Skip to content

Instantly share code, notes, and snippets.

# jonenzl/sort.c Last active Jun 11, 2017

Three sorting functions - bubble sort (O(n^2)), selection sort (O(n^2)), and counting sort (O(n))
 /**************************************************************************** * sort.c * * HarvardX - CS50 * * A selection of sorting functions * Bubble sort, selection sort, and counting sort ***************************************************************************/ /** * Bubble sort function */ void bubble_sort(int values[], int n) { // declare temp and initialise swapped variable int temp, i, j; bool swapped = false; // iterate through all the elements of the array for (i = 0; i < n - 1; i++) { // iterate through the numbers falling ahead for (j = 0; j < n - i - 1; j++) { // check whether the current element of the array is greater than the following element of the array if (values[j] > values[j + 1]) { // swap elements in the array temp = values[j]; values[j] = values[j + 1]; values[j + 1] = temp; swapped = true; } } // if no elements are being swapped, the array is now sorted, break loop if (!swapped) { break; } } } //////////////////////////////////////////////////////////////////////////////////////////// /** * Selection sort function */ void selection_sort(int values[], int n) { // declare temp variable int temp; // iterate through all the elements of the array for (int i = 0; i < n; i++) { int smallest_index = i; // iterate through the following element in the array for (int j = i + 1; j < n; j++) { // check whether the current element is less than the preceding element if (values[smallest_index] > values[j]) { smallest_index = j; } } // swap elements in the array temp = values[smallest_index]; values[smallest_index] = values[i]; values[i] = temp; } } //////////////////////////////////////////////////////////////////////////////////////////// /** * Counting sort function */ void counting_sort(int values[], int n) { // create output array that will have sorted array int output[n]; // create a count array to store count of integers and initialise count array as 0 int count[65536]; memset(count, 0, sizeof(count)); // store count of each integer for (int i = 0; values[i]; i++) { count[values[i]]++; } // change count[i] so that it contains actual position of integer in output array for (int i = 1; i <= 65536; i++) { count[i] += count[i - 1]; } // build the output array for (int i = 0; values[i]; i++) { output[count[values[i]] - 1] = values[i]; count[values[i]]--; } // copy the output array to the values array in sorted order for (int i = 0; values[i]; i++) { values[i] = output[i]; } }
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.