Selection Sort

Selection: Google Images

Selection sort is another O(N²) worst case time complexity algorithm.

It repeatedly finds the minimum element from the unsorted part.
As the name suggests it "selects" a position in the array and finds out the minimum element from current position till the last index.

Algorithm:

// for an array of size n
1. for i = 0 to n-1
2.  for j = i+1 to n-1
3.   if arr[i] > arr[j]
4.    swap(arr[i], arr[j])
5.   end if
6.  end for
7. end for

Example:

Let the arr = [3, 2, 4, 1, 5]
n = 5
1.  i = 0, j = 1
    arr[i] = 3, arr[j] = 2
    arr[i] > arr[j] -> swap(3, 2)
    updated arr = [2, 3, 4, 1, 5]
    
    i = 0, j = 2
    arr[i] = 2, arr[j] = 4
    arr[i] < arr[j] -> skip
    
    i = 0, j = 3
    arr[i] = 2, arr[j] = 1
    arr[i] > arr[j] -> swap(2, 1)
    updated arr = [1, 3, 4, 2, 5]
    
    i = 0, j = 4
    arr[i] = 1, arr[j] = 5
    arr[i] < arr[j] -> skip
    
    i = 0, j = 5
    j > n-1 -> break internal loop

Updated arr after 1st iteration -> arr = [1, 3, 4, 2, 5]
As you can see the smallest element of the arr[0...(n-1)], 1, came at index 0 

after the first iteration completed.

2.  i = 1, j = 2
    arr[i] = 3, arr[j] = 4
    arr[i] < arr[j] -> skip
    
    i = 1, j = 3
    arr[i] = 2, arr[j] = 2
    arr[i] > arr[j] -> swap(3, 2)
    updated arr = [1, 2, 4, 3, 5]
    
    i = 1, j = 4
    arr[i] = 2, arr[j] = 5
    arr[i] < arr[j] -> skip
    
    i = 1, j = 5
    j > n-1 -> break internal loop

Updated arr after 2nd iteration -> arr = [1, 2, 4, 3, 5]
As you can see the smallest element of the arr[1...(n-1)], 2, came at index 1 

after the second iteration completed.

Similarly after the 3rd iteration updated arr will be -> arr = [1, 2, 3, 4, 5]
Similarly after the 4rd iteration updated arr will be -> arr = [1, 2, 3, 4, 5]

Code in Python:

# selection sort function
def selection_sort(arr):
    n = len(arr)
    for i in range(0, n):
        for j in range(i+1, n):
            # if the value at i is > value at j -> swap
            if arr[i] > arr[j]:
                arr[i], arr[j] = arr[j], arr[i]


# input arr
arr = [3, 2, 4, 1, 5]
print('Before selection sort:', arr)

# call selection sort function
selection_sort(arr)
print('After selection sort:', arr)

"""
Output:
Before selection sort: [3, 2, 4, 1, 5]
After selection sort: [1, 2, 3, 4, 5]
"""

Time Complexity:

Selection sort has the same worst case and average case time complexity i.e. O(N²) as in each iteration we traverse the complete array from i to (n-1) even if the array is sorted.

Here is the code in C language: Selection Sort in C

--
Have any questions or suggestions? Post in the comments below!!

By,

Anubhav Shrimal