Loop Control Statements in C Introduction to HTML How to use the Github API The image tag, anchor tag and the button tag Ordered and Unordered Lists in HTML The division tag HTML Forms Tables in HTML Introduction to C Programming Introduction to Python Varibles and Datatypes in Python Operators in Python Typecasting in Python Input and Output in Python If Else in Python Loops in Python Break, Continue and Pass in Python Python practice section 1 Lists in Python Tuple in Python

Selection Sort in Python

Sorting means arranging the elements of a sequence in either ascending or descending order. Selection sort is a sorting algorithm that works by repeatedly scanning the unsorted portion of the array and then placing the smallest element at the beginning of the unsorted part in every step.

Dry Run

At every pass, we find the smallest element in the array from the current position to the last position. Initially, we assume that the current element is the smallest and set min_idx = index of the current element. Then we compare the current element to the elements present on the right side and if the current element is greater than any element, then we change the index of the smallest element to that element. In the end, we swap the smallest element with the current element. Hence after the first pass, the smallest element reaches the 0th index. Or we can say, after the ith pass, the ith smallest element will be at its correct position. Hence after N passes, the array will be completely sorted. 

arr= [2,5,3,8,7,1,6]

Pass 1, i=0  min_idx=0 

At j=1, arr[1] > arr[0] so, min_idx remains 0
At j=2, arr[2] > arr[0] so, min_idx remains 0
At j=3, arr[3] > arr[0] so, min_idx remains 0
At j=4, arr[4] > arr[0] so, min_idx remains 0
At j=5, arr[5] < arr[0] so, min_idx becomes 5
At j=6, arr[6] > arr[5] so, min_idx remains 5

Now, min_idx=5 ≠ 0, so swap arr[5] & arr[0] arr becomes [1,5,3,8,7,2,6]
The smallest element reaches the 0th index.

Pass 2, i=1  min_idx=1

At j=2, arr[2] < arr[1] so, min_idx becomes 2 
At j=3, arr[3] > arr[2] so, min_idx remains 2
At j=4, arr[4] > arr[2] so, min_idx remains 2
At j=5, arr[5] < arr[2] so, min_idx becomes 5
At j=6, arr[6] > arr[5] so, min_idx remains 5

Now, min_idx=5 ≠ 1, so swap arr[5] & arr[1] arr becomes [1,2,3,8,7,5,6]
The second smallest element reaches the 1st index.

Pass 3, i=2  min_idx=2 

At j=3, arr[3] > arr[2] so, min_idx remains 2
At j=4, arr[4] > arr[2] so, min_idx remains 2
At j=5, arr[5] > arr[2] so, min_idx remains 2
At j=6, arr[6] > arr[5] so, min_idx remains 2

Now, min_idx=2, so no swap happens arr remains [1,2,3,8,7,5,6]
The third smallest element is already present the 2nd index.

Pass 4, i=3  min_idx=3

At j=4, arr[4] < arr[3] so, min_idx becomes 4
At j=5, arr[5] < arr[4] so, min_idx becomes 5
At j=6, arr[6] > arr[5] so, min_idx remains 5

Now, min_idx=5 ≠ 3, so swap arr[5] & arr[3] arr becomes [1,2,3,5,7,8,6]
The fourth smallest element reaches the 3rd index.

Pass 5, i=4  min_idx=4

At j=5, arr[5] > arr[4] so, min_idx remains 4
At j=6, arr[6] > arr[4] so, min_idx becomes 6

Now, min_idx=6 ≠ 4, so swap arr[6] & arr[4] arr becomes [1,2,3,5,6,8,7]

Pass 6, i=5  min_idx=5

At j=6, arr[6] < arr[5], so min_idx becomes 6

Now, min_idx=6 ≠ 5, so swap arr[6] & arr[5] arr becomes [1,2,3,5,6,8,7]

The array is fully sorted.

Implementation

In the first pass, we run a loop from 0 to (n-1) so that the smallest element reaches the 0th index. In the second pass, we run a loop from 1 to (n-1) so that the second element reaches the 1st index and the smallest element remains at the 0th index. This is done for all the elements. To repeat this process n times, we use an outer loop from 0 to n-1. 

def selection_sort(arr):
    for i in range(0,len(arr)-1):
        min_idx=i
        for j in range(i+1,len(arr)):
            if arr[j]<arr[min_idx]:
                min_idx=j

        if min_idx!=i:
            arr[i],arr[min_idx]=arr[min_idx],arr[i]

        print(f"After pass {i+1}, arr = ",arr)
        print()

arr=[1,5,3,8,7,2,6]
print("Initial unsorted list = ",arr)
print()
      
selection_sort(arr)

print("Final Sorted list = ",arr)
Output
Initial unsorted list =  [2, 5, 3, 8, 7, 1, 6]

After pass 1, arr =  [1, 5, 3, 8, 7, 2, 6]

After pass 2, arr =  [1, 2, 3, 8, 7, 5, 6]

After pass 3, arr =  [1, 2, 3, 8, 7, 5, 6]

After pass 4, arr =  [1, 2, 3, 5, 7, 8, 6]

After pass 5, arr =  [1, 2, 3, 5, 6, 8, 7]

After pass 6, arr =  [1, 2, 3, 5, 6, 7, 8]

Final Sorted list =  [1, 2, 3, 5, 6, 7, 8]
Time Complexity : O(n2)
Space Complexity : O(1) no extra space used.

Time Complexity Analysis

Selection sort has the same best case, average case, and worst case complexity i.e it does not perform faster even if the array is almost sorted or fully sorted or sorted in the reverse order. At every step, it picks the smallest element from the unsorted portion of the array and puts it in the right position. Hence, it does not know It takes O(n2) time in all the cases.
Explanation : In the first pass,i=0 so we run a loop from j=i+1 to j=n-1 and compare arr[j] and arr[i]. Hence, there are (n-1) iterations and a total of (n-1) comparisons. After the first pass, the 0th index contains the smallest element. In one pass, there is only one swap. In the next pass, we run our loop from j=2 to j=n-1. Hence, there will be (n-2) iterations and a total of (n-2) comparisons.
Hence, the total number of iterations for an array of size n is:
= (n-1)+(n-2)+(n-3)+...+(n-(n-2))+(n-(n-1))+(n-n)
= (n-1)+(n-2)+(n-3)+...+2+1+0
= Sum of numbers from 1 to (n-1)
= ((n-1)+1).(n-1)/2
= n.(n-1)/2
= (n2-n)/2
Total no. of iterations = O(n2)
Total no. of comparisons = n.(n-1)/2 = O(n2)
Total no. of swaps = (n-1) = O(n)
So, the time complexity will be O(n2).

Advantages and Disadvantages

Advantages :
  1. Easy to understand.
  2. No additional space required.
Disadvantages :
  1. Takes O(n2) time to sort the elements. Hence, not very efficient to sort large data.
  2. Has the same best case, average case, and worst case complexity i.e. O(n2). There is no provision to break the loop early if the array is sorted before completing all the passes.
  3. It is a non-stable algorithm i.e. relative order of the same elements is not preserved.