Selection Sort in Python

Introduction to Selection Sort in Python

The selection sort algorithm maintains two sub-arrays by breaking the given array into sorted and unsorted parts.

In every iteration of the selection sort algorithm, the minimum element from the unsorted sub-array is picked and is moved to the sorted sub-array.

For more detailed information about how the selection sort works, you can visit Learn about Selection Sort Algorithm.

Python Program for Selection Sort

Output:

Time Complexity Calculation

To understand time complexity of selection sort in python, we can break the operation cost into the following parts:

• Loop Operation to iterate over the array of elements – part 1
• swapping the elements. – part 2
• Loop to iterate over the unsorted subarray elements. – part 3

Let us consider the number of elements in the array to be N. Now, considering Part 1, the loop will be running N times.

So, the number of times the element will swap is N times, which will be done in constant time complexity that is O(1). Therefore we can conclude that part one of the insertion sort algorithm in python will take O(N) time complexity.

Part 2 is a nested loop inside part 1 loop where swapping of elements occurs. The nested loop will help in searching for the smallest. The if statement will be making N number of comparisons which takes constant time for execution. If the part 1 loop is executed N times, then the nested loop in part 2 will be executed.

From this observation, we can conclude that the insertion sort algorithm in python has $O(N^2)$ time complexity.

Now, let us discuss the worst, average, and best cases while considering insertion sort in python to solve a problem.

• Worst Case: The worst case can occur when we want to sort an array in ascending order, but the array is sorted in descending order, resulting in the time complexity of $O(N^2`)$.

  Example : Given an array [5,4,3,2,1] and the required array is [1,2,3,4,5] so since selection in python does the sorting in-place, it is required to traverse the array repeatedly by keeping an element fixed and swapping it with lowest which results to time complexity of O(N^2).

• Average Case: The average Case can occur when the array has elements arranged in jumbled order, resulting in O's time complexity $O(N^2)$.

  Example : Given an array [1,4,5,2,67,0] and the required array is [0,1,2,4,5,67] since all elements are in jumbled order it is required to traverse the array repeatedly by keeping an element fixed and swapping it with lowest which results to time complexity of $O(N^2)$.

• Best Case: The best case can occur when the list is already sorted in the desired order, which makes us go through all the elements once while checking their order reducing the time complexity to O(N).

  Example: Given an array [1,2,3,4,5] and we want to sort the array in ascending order, therefore the resultant array is similar to the array provided in the input, i.e [1,2,3,4,5]. Thus selection algorithm in python will traverse through the array once and return the output, which results to time complexity of O(N) i.e linear.

Explore Scaler Topics Python Tutorial and enhance your Python skills with Reading Tracks and Challenges.

Read More:

• Sort a String in Python.
• Sort Dictionary by Key in Python.
• Sort Dictionary by Value in Python.
• Sorted Function in Python.