Instantly share code, notes, and snippets.

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

Embed
What would you like to do?
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];
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment