So friends, in Selection Sort Python tutorial, we will learn how to sort data using selection sort method. We will also see selection sort algorithm, complexity and its implementation in python. So let’s start this tutorial.
Before diving into selection sort, we have to understand some basics of sorting. So first of all i am figuring out the most popular topic of data structure i.e., Sorting.
What Is Sorting – A Quick Overview
- Sorting means ordering the data either into ascending or descending order within the array.
- It is one of the most common data structure processing application.
- Sorting can be done on names, numbers and records
Why Sorting Is Effective ?
For understanding the effectiveness of sorting, we will take an example.
- Consider you are searching a phone number from your phone dictionary.
- You will easily get number because the names in the phone book have been sorted into alphabetical order.
- But if in your phone, numbers are not sorted then you can’t find phone numbers easily. And it takes long time.
So the conclusion is that if your numbers are in sorted order then it takes less time for searching. That means sorting greatly improves the efficiency of searching.
Sorting Methods
Sorting can be performed using several methods, they are following:
- Selection sort
- Merge sort
- Insertion sort
- Heap sort
- Bubble sort
- Quick sort
- Radix sort
So guys, we have just learned some basics of sorting, now we will discuss selection sort and see how to implement it in python.
Selection Sort Python Tutorial – Learn With Examples
Selection sort is very simple method. It is in-place comparison based method. In this method, we need to compare the numbers and need to place them in the correct position. So let’s start selection sort in python.
Selection Sort Mechanism ?
Now we will understand the mechanism of selection sort.
- In selection sort, we pick a minimum element from a list and place it in the sorted part of list.
- Initially we consider first element as minimum element and compare it with other elements of list.
- And during comparison, if we find a minimum element then its refers as new minimum element.
- When we complete one full round of comparison then the minimum element is swapped with first element.
- And this process will continued until we sort all the elements.
Selection Sort Algorithm
And now the question is that how we perform selection sort. So this is the answer :
- Let’s consider the first element as sorted and the rest as unsorted
- Assume the first element is the smallest element.
- Checking, if the first element is less than each of the other elements in list, then do:
- If yes, do nothing
- If no, choose the other smaller element as minimum and repeat step 3
- When one iteration is completed, swap the minimum element with the first element of the list.
- Now take the sublist(ignore sorted part) and and repeat all the above steps until all the elements in the list are sorted.
Selection Sort Working Examples
Now let us take a example for understanding selection sort mechanism.
So consider a list which contains some elements.
|
1 2 3 |
mylist = [6,7,9,0,2] |
And now we have to sort this list in ascending order. So let’s start the sorting process.
Round 1
In round 1, we select first element as minimum.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
6 is the minimum 6<7: nothing happens 6<9: nothing happens 6>0: 0 is new minimum 0<2: nothing happens Swap 0 and 6 mylist = [0,7,9,6,2] |
Round 2
In round, our minimum element is 7 and list is mylist = [0,7,9,6,2].
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
7 is the minimum 7<9: nothing happens 7>6: 6 is new minimum 6>2: 2 is new minimum Swap 2 and 7 mylist = [0,2,9,6,7] |
Round 3
In round 3, our minimum element is 9 and list is mylist = [0,2,9,6,7].
|
1 2 3 4 5 6 7 8 9 10 11 |
9 is the minimum 9>6: 6 is new minimum 6<7: nothing happens Swap 6 and 9 mylist = [0,2,6,9,7] |
Round 4
In round 4, minimum element is 9 and list is mylist = [0,2,6,9,7].
|
1 2 3 4 5 6 7 8 9 |
9 is the minimum 9>7: 7 is new minimum Swap 7 and 9 mylist = [0,2,6,7,9] |
Finally our list has been sorted successfully and the sorted list is mylist = [0,2,6,7,9].
Selection Sort – Big Oh Analysis
- Selection sort is not a fast sorting algorithm because it uses nested loop to sort.
- It is best suited for only small data sets.
- It runs in O(n2).
Selection Sort Python Logic(Algorithm)
|
1 2 3 4 5 6 7 |
Step 1 − Set MINIMUM to location 0 Step 2 − Search the minimum element in the list Step 3 − Swap with value at location MINIMUM Step 4 − Increment MINIMUM to point to next element Step 5 − Repeat until list is sorted |
Selection Sort Python Implementation
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
def Selection_Sort(mylist): #Traverse through all list elements for i in range(len(mylist)): # Searching the minimum element in remaining unsorted list minpos = i for j in range(i+1, len(mylist)): if mylist[j] < mylist[minpos]: minpos = j # Swap the found minimum element with the first element temp = mylist[i] mylist[i] = mylist[minpos] mylist[minpos] = temp mylist = [9,8,3,4,2] print("Unsorted List : ", mylist) Selection_Sort(mylist) print("Sorted List By selection Sort : ", mylist) |
Let’s check the output :
Now we will see, how it looks like in each iteration. For doing this print list during swapping. So write following code –
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
def Selection_Sort(mylist): print("\n Sorting process :") for i in range(len(mylist)): minpos = i for j in range(i+1, len(mylist)): if mylist[j] < mylist[minpos]: minpos = j temp = mylist[i] mylist[i] = mylist[minpos] mylist[minpos] = temp print(mylist) # add this line for printing sorting process mylist = [9,8,3,4,2] print("Unsorted List : ", mylist) Selection_Sort(mylist) print("\n Sorted List By selection Sort : ", mylist) |
And now you can see how sorting has been performed in each iteration.
You have noticed that even though after round 2, we can see the list is sorted, but there is no way for the algorithm to know this. Hence only after completely traversing the entire list, the algorithm stops.
Time Complexity Of Selection Sort
| Best Case | O(n2) |
| Average Case | O(n2) |
| Worst Case | O(n2) |
Related Articles :
- Python Binary To Decimal Tutorial With Examples
- Python Sort Dictionary By Value – Sort With Lambda Function And Operator Module
- Linear Search Python – Learn Linear Search With Example
- Join Two Lists Python – Learn Joining Two Lists With Examples
- Python Regular Expression Example : Learn RegEx with Python
So that’s it for Selection Sort Python tutorial. If you found this post helpful then please SHARE it with your friends. And for any question you can leave your comments below. Thank You 🙂