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.py. Open it in your editor and enter the following code, or you can download it as a zip or clone/download the Github repo if you prefer. As it's a short program I have included all the code in one hit.
Source Code Links
selectionsort.py
import random RED = "\x1B[31m" GREEN = "\x1B[32m" RESET = "\x1B[0m" def main(): """ Here we just demonstrate selection sort by calling a couple of functions to create a list of random data and sort it. """ print("------------------") print("| codedrome.com |") print("| Selection Sort |") print("------------------\n") data = populate_data() selection_sort(data) def populate_data(): """ Create an empty list and add a few random integers to it. """ data = [] for i in range(0, 16): data.append(random.randint(1, 99)) return data def print_data(data, sortedto): """ Prints the data on a single line, with the sorted portion in green and the unsorted portion in red, using ANSI terminal codes. """ for i in range(0, len(data)): if i < sortedto: print(GREEN + "%-3d " % data[i] + RESET, end="") else: print(RED + "%-3d " % data[i] + RESET, end="") print("\n") def selection_sort(data): """ Applies the selection sort algorithm to a list of integers, also printing the data on each iteration to show progress. """ print("Unsorted...") print_data(data, 0) print("Selection Sorting...") sorted_to = 0; while(sorted_to < len(data) - 1): index_of_lowest = find_lowest_index(data, sorted_to) swap(data, sorted_to, index_of_lowest) sorted_to += 1 print_data(data, sorted_to) print("Sorted!") def swap(data, i1, i2): """ A neat little trick to swap integer values without using a third variable """ if i1 != i2: data[i1] = data[i1] ^ data[i2] data[i2] = data[i1] ^ data[i2] data[i1] = data[i1] ^ data[i2] def find_lowest_index(data, start): """ Finds the index of the lowest item in the unsorted part of the data. """ lowest_index = start for i in range(start, len(data)): if data[i] < data[lowest_index]: lowest_index = i return lowest_index main()
At the top we have three variables which hold ANSI codes for setting terminal colours. I'll cover this topic in a later post but for now just print these strings to change the text colour or reset it to the default.
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 list to random values.
The print_data function is also 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 list 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 the variable sorted_to which is the index of the end of the currently sorted part of the list, obviously initialized to 0.
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. Printing the list on every iteration gives a visual indication of how the algorithm does its stuff.
Now let's look at the two functions used by selection_sort. The first is swap, which takes a list and two indexes, and swaps the items at these positions. As we are only swapping integers we can use exclusive or, or ^ in Python. 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 list to find the lowest item, the index of which it returns.
We can now run the program with this command in the terminal . . .
Running the program
python3.7 selectionsort.py
. . . which gives us this output:
Program Output
------------------ | codedrome.com | | Selection Sort | ------------------ Unsorted... 3 39 39 95 99 86 78 10 38 16 75 16 13 11 18 43 Selection Sorting... 3 39 39 95 99 86 78 10 38 16 75 16 13 11 18 43 3 10 39 95 99 86 78 39 38 16 75 16 13 11 18 43 3 10 11 95 99 86 78 39 38 16 75 16 13 39 18 43 3 10 11 13 99 86 78 39 38 16 75 16 95 39 18 43 3 10 11 13 16 86 78 39 38 99 75 16 95 39 18 43 3 10 11 13 16 16 78 39 38 99 75 86 95 39 18 43 3 10 11 13 16 16 18 39 38 99 75 86 95 39 78 43 3 10 11 13 16 16 18 38 39 99 75 86 95 39 78 43 3 10 11 13 16 16 18 38 39 99 75 86 95 39 78 43 3 10 11 13 16 16 18 38 39 39 75 86 95 99 78 43 3 10 11 13 16 16 18 38 39 39 43 86 95 99 78 75 3 10 11 13 16 16 18 38 39 39 43 75 95 99 78 86 3 10 11 13 16 16 18 38 39 39 43 75 78 99 95 86 3 10 11 13 16 16 18 38 39 39 43 75 78 86 95 99 3 10 11 13 16 16 18 38 39 39 43 75 78 86 95 99 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.