There are many sorting algorithms, often with variations and optimizations, and every now and again I will be coding some of them for this site.
A while ago I wrote a post on bubble sort and here is a follow up on another sorting algorithm called selection sort. As with bubble sort it's not particularly efficient but it is simple to understand and implement.
The basic selection sort algorithm is as follows.
- Search the entire list for the smallest item
- Swap it with the first item - it is now in its correct place
- Search the remainder of the list for its smallest item and swap it with the second item
- Repeat until you reach the last but one item in the list
The list being sorted can be regarded as being in two parts, the sorted part on the left which gets ever larger and the unsorted part on the right which gets ever smaller. We stop before getting to the last item because if all other items are in their correct place the last item will automatically be in the right place.
Create a new folder and within it create an empty file called selectionsort.c. Open it in your editor and enter the following code, or download it as a zip or from Github if you prefer. As it's a short program I have included all the code in one hit.
Source Code Links
selectionsort.c
#include<stdio.h> #include<time.h> #include<stdlib.h> #define RED "\x1B[31m" #define GRN "\x1B[32m" #define RESET "\x1B[0m" //-------------------------------------------------------- // FUNCTION PROTOTYPES //-------------------------------------------------------- void populate_data(int* data, int size); void print_data(int* data, int size, int sortedto); int find_lowest_index(int* data, int size, int start); void swap(int* data, int i1, int i2); void selection_sort(int* data, int size); //-------------------------------------------------------- // FUNCTION main //-------------------------------------------------------- int main(int argc, char* argv[]) { puts("------------------"); puts("| codedrome.com |"); puts("| Selection Sort |"); puts("------------------\n"); const int size = 16; int data[size]; populate_data(data, size); selection_sort(data, size); return EXIT_SUCCESS; } //-------------------------------------------------------- // FUNCTION populate_data //-------------------------------------------------------- void populate_data(int* data, int size) { srand(time(NULL)); for(int i = 0; i < size; i++) { data[i] = (rand() % 128); } } //-------------------------------------------------------- // FUNCTION print_data //-------------------------------------------------------- void print_data(int* data, int size, int sortedto) { for(int i = 0; i < size; i++) { if(i < sortedto) printf(GRN "%-3d " RESET, data[i]); else printf(RED "%-3d " RESET, data[i]); } printf("\n"); } //-------------------------------------------------------- // FUNCTION selection_sort //-------------------------------------------------------- void selection_sort(int* data, int size) { puts("Unsorted..."); print_data(data, size, 0); puts("Selection Sorting..."); int sorted_to = 0; int index_of_lowest; while(sorted_to < size - 1) { index_of_lowest = find_lowest_index(data, size, sorted_to); swap(data, sorted_to, index_of_lowest); sorted_to++; print_data(data, size, sorted_to); } puts("Sorted!"); } //-------------------------------------------------------- // FUNCTION swap //-------------------------------------------------------- void swap(int* data, int i1, int i2) { if(i1 != i2) { data[i1] = data[i1] ^ data[i2]; data[i2] = data[i1] ^ data[i2]; data[i1] = data[i1] ^ data[i2]; } } //-------------------------------------------------------- // FUNCTION find_lowest_index //-------------------------------------------------------- int find_lowest_index(int* data, int size, int start) { int lowest_index = start; for(int i = start; i < size; i++) { if(data[i] < data[lowest_index]) { lowest_index = i; } } return lowest_index; }
I'll gloss over main which basically calls other functions to create a list of random numbers and then sort them.
The populate_data function is very simple - it just sets the elements of the supplied array to random values.
The print_data is quite simple in that it iterates the supplied array and prints it out, but it also takes a sortedto argument. This deliniates the sorted/unsorted parts of the array mentioned above and is used to print the sorted numbers in green and the unsorted numbers in red.
We now get to the selection_sort function itself, which starts off by calling print_data to display the unsorted list. We then declare a couple of variables: sorted_to is the index of the end of the currently sorted part of the list, obviously initialized to 0, and index_of_lowest will hold the index of the lowest item in the unsorted part of the list.
We then enter a loop which calls a function to find the index of the lowest item in the unsorted part of the list, and then calls another function to swap it with the first item in the unsorted part. We then increment sorted_to and print the list.
Now let's look at the two functions used by selection_sort. The first is swap, which takes an array and two indexes, and swaps the items at these positions. As we are only swapping integers we can use exclusive or, or ^ in C. I won't describe how this works here as it was described in the post on bubble sort which you might like to refer to.
The last function is find_lowest_index. This simply iterates the unsorted part of the array to find the lowest item, the index of which it returns.
We can now compile and run the program. In the terminal enter the following.
Compile and Run
gcc selectionsort.c -std=c11 -lm -o selectionsort ./selectionsort
Program Output
------------------ | codedrome.com | | Selection Sort | ------------------ Unsorted... 9 49 19 104 93 49 1 13 105 63 36 69 16 82 21 9 Selection Sorting... 1 49 19 104 93 49 9 13 105 63 36 69 16 82 21 9 1 9 19 104 93 49 49 13 105 63 36 69 16 82 21 9 1 9 9 104 93 49 49 13 105 63 36 69 16 82 21 19 1 9 9 13 93 49 49 104 105 63 36 69 16 82 21 19 1 9 9 13 16 49 49 104 105 63 36 69 93 82 21 19 1 9 9 13 16 19 49 104 105 63 36 69 93 82 21 49 1 9 9 13 16 19 21 104 105 63 36 69 93 82 49 49 1 9 9 13 16 19 21 36 105 63 104 69 93 82 49 49 1 9 9 13 16 19 21 36 49 63 104 69 93 82 105 49 1 9 9 13 16 19 21 36 49 49 104 69 93 82 105 63 1 9 9 13 16 19 21 36 49 49 63 69 93 82 105 104 1 9 9 13 16 19 21 36 49 49 63 69 93 82 105 104 1 9 9 13 16 19 21 36 49 49 63 69 82 93 105 104 1 9 9 13 16 19 21 36 49 49 63 69 82 93 105 104 1 9 9 13 16 19 21 36 49 49 63 69 82 93 104 105 Sorted!
You can clearly see the sorted part of the list getting larger and the unsorted part getting smaller. As I mentioned above we can stop before we get to the last item which is bound to be in the correct place if all the other items are.