Selection Sort

Selection sort works on a simple idea: repeatedly pick the smallest element from the unsorted part of the list and put it at the beginning. Unlike bubble sort, which pushes large elements to the end by swapping neighbours, selection sort directly places the smallest remaining element into its correct position in one swap per pass.

The list is treated as two virtual parts — a left part that is sorted and a right part that is unsorted. Initially, the sorted part is empty and the entire list is unsorted. With each pass, one element moves from the unsorted part to the sorted part, growing the sorted section from left to right.

To sort a list of n elements in ascending order, selection sort makes exactly n-1 passes. In the first pass, the algorithm scans all n elements to find the smallest element. That smallest element is then swapped with the element at index 0 (the leftmost position of the unsorted list). After this swap, the element at index 0 is in its final sorted position and is no longer considered in subsequent passes.

In the second pass, the algorithm scans the remaining n-1 elements (from index 1 to n-1) to find the next smallest element. This element is swapped with the element at index 1. Now the first two positions contain the two smallest elements in sorted order.

This process continues. In the k-th pass, the algorithm finds the smallest element among the unsorted elements (from index k-1 to n-1) and swaps it with the element at index k-1. After n-1 passes, the first n-1 smallest elements are in their correct positions. The n-th element is automatically in its correct place — no further pass is needed.

How it works — step by step

Consider the list numList = [8, 7, 13, 1, -9, 4] (6 elements) — the same list used for Bubble sort and Insertion sort. The figure in the textbook (Figure 5.2) shows the comparisons made in each pass.

Pass 1: Scan the whole list (index 0 to 5) to find the smallest element. Comparing 8, 7, 13, 1, -9, 4 in turn, the smallest value is -9 (at index 4). It is swapped into index 0, its final sorted position. List: [-9, 8, 7, 13, 1, 4].

Pass 2: Scan indices 1 to 5 (index 0 is already sorted). The smallest remaining value is 1. It is swapped into index 1. List: [-9, 1, 7, 13, 8, 4].

Pass 3: Scan indices 2 to 5. The smallest remaining value is 4. It is swapped into index 2. List: [-9, 1, 4, 13, 8, 7].

Pass 4: Scan indices 3 to 5. The smallest remaining value is 7. It is swapped into index 3. List: [-9, 1, 4, 7, 8, 13].

Pass 5: Scan indices 4 to 5. 8 is already smaller than 13, so no swap is needed. List remains [-9, 1, 4, 7, 8, 13], now fully sorted.

The final sorted list in ascending order is [-9, 1, 4, 7, 8, 13], matching the result from Bubble sort.

Algorithm 5.2: Selection Sort

SELECTIONSORT(numList, n)
Step 1:  SET i = 0
Step 2:  WHILE i < n REPEAT STEPS 3 to 11
Step 3:    SET min = i, flag = 0
Step 4:    SET j = i + 1
Step 5:    WHILE j < n REPEAT STEPS 6 to 10
Step 6:      IF numList[j] < numList[min] THEN
Step 7:        min = j
Step 8:        flag = 1
Step 9:    IF flag = 1 THEN
Step 10:     swap(numList[i], numList[min])
Step 11: SET i = i + 1

The outer loop (controlled by i) runs from 0 to n-1, representing the current position where the next smallest element should be placed. Inside, a variable min is set to i, assuming the current position holds the smallest element, and flag is reset to 0. An inner loop (controlled by j) runs from i+1 to n-1, comparing each element with numList[min]. If a smaller element is found, min is updated to that index and flag is set to 1. After the inner loop completes, if flag is 1, a swap is performed between numList[i] and numList[min]. The outer loop then increments i and the process repeats.

Program 5-2: Implementation of selection sort using Python.

def selection_Sort(list2):
    flag = 0                          # to decide when to swap
    n = len(list2)
    for i in range(n):                # traverse through all list elements
        min = i
        for j in range(i + 1, len(list2)):   # the left elements are already
                                              # sorted in previous passes
            if list2[j] < list2[min]:  # element at j is smaller than the
                                        # current min element
                min = j
                flag = 1
        if flag == 1:                  # next smallest element is found
            list2[min], list2[i] = list2[i], list2[min]

numList = [8, 7, 13, 1, -9, 4]
selection_Sort(numList)
print("The sorted list is :") …