Complete Python Selection Sort Algorithm | Code Complexity
As we know, sorting is a technique to arrange the elements in the array either in ascending or descending order. And there are multiple sorting algorithms such as bubble sort, insertion sort, quick sort, selections sort…
Here we will see Python selection sort.
Before writing the code…
What is Selection Sort Algorithm?
Here is pseudo-algorithm for selection sorting.
- Take the array (containing elements to sort) as an input
- Iterate through all the elements in the array (says element as i)
- Find the smallest elements from rest of the array (array elements next to i’s)
- Swap the smallest element with i
If you understand the pseudo-algorithm, I would like if you minimize the browser and try to write code yourself.
Python Selection Sort Program
#swap two elements in nArr at postion i and j def swap(i, j, nArr): if i!=j: temp = nArr[j] nArr[j] = nArr[i] nArr[i] = temp #function to sort elements in the list def selectionSort(nArr): for i in range(0, len(nArr)): small = i for j in range(i+1, len(nArr)): if nArr[j] < nArr[small]: small = j swap(i, small, nArr) #list containing elements to sort nArr = [34,456, 5, 5,67] selectionSort(nArr) print(nArr)
Here in the above program, I have a hardcoded list. You can even take the list elements as user input.
[5, 5, 34, 67, 456]
In the first pass, the first element in the array will be in sorted position. After the second pass, two elements in the array will be sorted.
If you have n elements, after n-1 pass, n-1 elements will be sorted. If you arrange first n-1 elements in the array in the right position, the last element automatically will be in the right position.
So in each pass, you need to swap the elements at most one time. So in selection sort, you need a maximum n-1 pass and so the swaps to sort all the elements in the array.
If you compare with the bubble sort, in every pass we swap the elements multiple times. So you can consider the selection sort as improvement in bubble sort.
Above code, sort the elements in ascending order. If you want the same program to sort elements in descending order, replace
> inside the function
For sorting, you need to take Numeric data types values. Just to give little tweak, you can also use a list containing characters to sort.
Time complexity of Selection Sort
As you have to compare each element with other elements from an array list, it has a time complexity of
o(n^2) in all three cases (best, average and worst case).
As it takes
O(n^2) time, it is not considered as an efficient algorithm for sorting if you have minimal time.
Memory Complexity of Selection Sort
Selection sort does not require any extra memory (except for swapping). So, it takes constant time
O(1), despite the number of elements in the array.
You need to swap the elements, only if it is required. If your array is already sorted, there will be zero numbers of swapping.
Just to clarify…
Here we are using the list to sort. As tuple is an immutable data structure in Python, you can not use tuple for sorting. For more, you can read List vs Tuple in Python.
If you understand the logic behind Python selection sort, it is easy to implement in any programming language. Any doubt? Write in the comment section.
Thanks for giving this simple explanation. I came here while searching for help for my assignment. Learning data structures with Python is fun especially we have to write really few lines of code.
You’re welcome, Salim. I hope you found whatever you were looking for your assignment.