What will we cover in this tutorial
Selection sort is one of the simplest sorting algorithms, which is a good algorithm to start with. While the algorithm is considered to be slow, it has the advantage of not using auxiliary space.
Step 1: Understand the Selection Sort algorithm
The goal of sorting is to take an unsorted array of integers and sort it.
Example given below.
[97, 29, 53, 92, 42, 36, 12, 57, 90, 76, 85, 81, 12, 61, 45, 3, 83, 34, 7, 48] to [3, 7, 12, 12, 29, 34, 36, 42, 45, 48, 53, 57, 61, 76, 81, 83, 85, 90, 92, 97]
The algorithm is the most intuitive way of sorting a list.
It works as follows.
- Go through the list to be sorted and find the smallest element.
- Switch the smallest element with the first position.
If you started with the following list.
[97, 29, 53, 92, 42, 36, 12, 57, 90, 76, 85, 81, 12, 61, 45, 3, 83, 34, 7, 48]
You would now have this list.
[3, 29, 53, 92, 42, 36, 12, 57, 90, 76, 85, 81, 12, 61, 45, 97, 83, 34, 7, 48]
Notice, that now we have the smallest element in the front of the list, we know that the second smallest element must be somewhere in the list starting from the second position all the way to the end.
Hence, you can repeat step the above 2 steps on the list excluding the first element.
This will give you the following list.
[3, 7, 53, 92, 42, 36, 12, 57, 90, 76, 85, 81, 12, 61, 45, 97, 83, 34, 29, 48]
Now we have that the first two elements are sorted, while the rest of the list is not sorted.
Hence, we can repeat the two steps again on the unsorted part of the list.
If we continue this until the we reach the end of the list. This should give us a sorted list.
Step 2: Implementation of Selection Sort
A beautiful thing about Selection Sort is that it does not use any auxiliary memory. If you are new to sorting, then this can be a big advantage if sorting large data sets.
The disadvantage of Selection Sort is the time complexity.
We will come back to that later.
The code of Selection Sort can be done in the following manner.
def selection_sort(list_to_sort): for i in range(len(list_to_sort)): index_of_min_value = i for j in range(i + 1, len(list_to_sort)): if list_to_sort[j] < list_to_sort[index_of_min_value]: index_of_min_value = j list_to_sort[i], list_to_sort[index_of_min_value] = list_to_sort[index_of_min_value], list_to_sort[i] list_to_sort = [97, 29, 53, 92, 42, 36, 12, 57, 90, 76, 85, 81, 12, 61, 45, 3, 83, 34, 7, 48] selection_sort(list_to_sort) print(list_to_sort)
This will produce the correct output.
[3, 7, 12, 12, 29, 34, 36, 42, 45, 48, 53, 57, 61, 76, 81, 83, 85, 90, 92, 97]
Step 3: The time complexity of Selection Sort algorithm
Now this is the sad part of this simple algorithm. It does not perform good. A sorting algorithm is considered efficient if it runs in O(n log(n)), which Selection Sort does not.
The simple time complexity analysis is as follows.
Assume we have a list of n unsorted integers. Then the first iteration of the list will make n – 1 comparisons, the second iteration will make n – 2 comparisons, and so forth all the way down to 1 comparison.
This is the sum of 1 to n – 1, which is found by this formula (n – 1)(n – 2)/2, which is O(n^2).
Other than that the algorithm does n swapping of numbers. This is O(n).
This combines the algorithm to O(n + n^2) = O(n^2).
This should wake your appetite to understand how you can make more efficient sorting.
Another good example of a simple sorting algorithm is the Insertion Sort algorithm.
For more efficient algorithm you should check out the Merge Sort algorithm.
Python for Finance: Unlock Financial Freedom and Build Your Dream Life
Discover the key to financial freedom and secure your dream life with Python for Finance!
Say goodbye to financial anxiety and embrace a future filled with confidence and success. If you’re tired of struggling to pay bills and longing for a life of leisure, it’s time to take action.
Imagine breaking free from that dead-end job and opening doors to endless opportunities. With Python for Finance, you can acquire the invaluable skill of financial analysis that will revolutionize your life.
Make informed investment decisions, unlock the secrets of business financial performance, and maximize your money like never before. Gain the knowledge sought after by companies worldwide and become an indispensable asset in today’s competitive market.
Don’t let your dreams slip away. Master Python for Finance and pave your way to a profitable and fulfilling career. Start building the future you deserve today!
Python for Finance a 21 hours course that teaches investing with Python.
Learn pandas, NumPy, Matplotlib for Financial Analysis & learn how to Automate Value Investing.
“Excellent course for anyone trying to learn coding and investing.” – Lorenzo B.