Data Structures & Algorithms

What is Selection sort?

Selection sort is a simple sorting algorithm that sorts the elements of an array inplace, thereby taking constant memory space. The algorithm takes an unordered sequence of numbers as input and returns the numbers in sorted order. In this post, we will learn about the selection sort algorithm and its time complexity.

The algorithm works by placing exactly one element at its sorted position in each iteration. In the first iteration, the algorithm finds the smallest element in the array and exchanges it with the element at the first index. In iteration k of the algorithm, it finds the k’th smallest element in the array and replaces it with the element in the k’th index. After iteration k of the algorithm, the elements from the first index to the kth index will be sorted in order, and the remaining elements will be in unsorted order. In each iteration, the array becomes sorted for one more additional position.

The algorithm iterates for n-1 times to sort elements from the first index to the n-1 th index, where n is the number of elements in the array. The algorithm needs to run only for the first n-1 elements because, after n-1 iterations, there will be only the n’th element remaining. It will be the maximum element of the array. Hence, the algorithm sorts all elements in an array by n-1 iterations.

In iteration k, the algorithm picks the k’th smallest element. This can be done easily using a little trick. Since the array up to index k-1 is already in sorted order, the k th smallest element is the smallest element in the remaining unsorted array. Hence, the algorithm searches for the smallest element in the subarray beginning at index k. The smallest element in this subarray is the k th smallest element in the entire array.

Input: array A[1..n]

Step 1: Initialize i to 1.

Step 2: Pick the smallest element in A[i..n] and swap it with the element in position A[i].

Step 3: Increment i. If i == n-1, return. Else, go to step 2.

Example: [3, 6, 1, 9, 4, 8, 0]

Iteration 1: [0, 6, 1, 9, 4, 8, 3]

Explanation: The smallest element in A[1..n] is 0. Hence A[1] and 0 are swapped. In each iteration, exactly one element is placed in sorted order. Here, 0 is placed in its sorted position.

Iteration 2: [0, 1, 6, 9, 4, 8, 3]

Explanation: The smallest element in A[2..n] is 1. Hence, A[2] and 1 are swapped.

Iteration 3: [0, 1, 3, 9, 4, 8, 6]

Explanation: The smallest element in A[3..n] is 3. Hence, A[3] and 1 are swapped.

Note that the array A[1..2] remains sorted, and hence the third smallest element is the least element in A[3..n]

Iteration 4: [0, 1, 3, 4, 9, 8, 6]

Iteration 5: [0, 1, 3, 4, 6, 8, 9]

Iteration 6: [0, 1, 3, 4, 6, 8, 9]

Source Code

def selection_sort(arr, n):
    for i in range(0, n-1):
        # Find index of minimum element
    min_idx = i+1
    for j in range(i+1, n):
    if arr[j] <arr[min_idx]:
        min_idx = j
    # Swap the minimum element with the
        # element pointed by current index
    arr[min_idx], arr[i] = arr[i], arr[min_idx]
    return arr


if __name__ == "__main__":
    arr = [3, 6, 1, 9, 4, 8, 0]
    n = len(arr)
    arr = selection_sort(arr, n)
    print (arr)

The selection sort algorithm makes the minimum number of swaps when compared to other algorithms. It makes exactly n-1 swaps. In each iteration, the search for the minimum element takes O(n) time. The algorithm iterates n times for each element, and hence, the average case time complexity of selection sort is quadratic (O(n^2)).

About the author

Arun Palaniappan