Visual Understanding of Selection Sort Algorithm

In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. Efficient sorting is important for optimizing the efficiency of other algorithms (such as search and merge algorithms) that require input data to be in sorted lists. Sorting is also often useful for canonicalizing data and for producing human-readable output. - From Wikipedia

There are many sorting algorithms. One of the most important factor when choosing which sorting algorithm to use is its algorithm complexity, represented in Big-O notations. Figure (1) summarizes the the algorithm complexity of various sorting methods. Note that $N$ is is an array size, $O$ is the worst-case scenario, $\Omega$ is the best-case scenario, and $\theta$ is the average-case scenario. This post focuses on Selection Sort.

Figure 1: Algorithm complexities and their efficiencies

1. Selection Sort¶

Selection sort is an in-place comparison sorting algorithm. It has an $O(N^2)$ time complexity at all times, according to figure (1). Effectively, the only reason that schools still teach selection sort is because it's an easy-to-understand, teachable technique, on the path to more complex and powerful algorithms. It has the follwoing Pros and Cons:

Pros

1. It is a straightforward and teachable technique.
2. It does no more than $N$ swaps, and thus is useful where swapping is expensive. However, this is rarely an important design factor, because there are better algorihtms for it.
3. It is an in-place algorithm. No additional temporary storage is required beyond what is needed to hold the original list (space complexity = $O(1)$)

Cons

1. Bad for large lists due to $O(N^2)$ time complexity
2. Other sorting algorithms are better.

1.1. Understanding Selection Sort¶

The selection sort algorithm works by repeatedly finding the smallest element from unsorted part and putting it at the beginning of the sorted part. Effectively, the algorithm divides the list into two parts:

1. The sublist which is already sorted.

2. Remaining sublist which is unsorted.

For each iteration, the smallest element from the unsorted sublist is picked and moved to the end of the sorted sublist. Let's dive into the illustrations for better understanding of selection sort. Imagine that you want to sort the books shown in figure (2) in ascending order of sizes.

Figure 2: Books to sort

1st Iteration

Selection sort divides a list into sorted & unsorted sublists. The grey divider represents the split between sorted (left) vs unsorted (right) array. At the beginning, nothing is sorted.

Figure 3: Selection sort 1

The algorithm finds the smallest value in the unsorted sublist, and then put it in the last index of the sorted sublist. Since this is the first iteration, the smallest value in the unsorted sublist becomes the first element in the sorted sublist.

Figure 4: Selection sort 2

2nd Iteration

After the 1st iteration, the grey divider (that splits sorted vs unsorted) moves 1 index to the right. The smallest value in the new unsorted sublist is identified, and then moved to the last index of the sorted sublist. From now on, the same procedures are repeated until sorting is completed.

Figure 5: Selection sort 3

3rd Iteration

Figure 6: Selection sort 4

4th Iteration

Figure 7: Selection sort 5

5th Iteration

Figure 8: Selection sort 6

6th Iteration

Sorting is now over. Notice that the grey divider moved N=6 times total, as mentioned in the 2nd Pros of selection sort above.

Figure 9: Selection sort 7

Figure (10) is the gif represention of the selection sort algorithm described above. Notice that the left of grey divider is sorted sublist, and right is the unsorted sublist. At the last iteration, the grey wall is at the end of the books, representing the fact that all books are now sorted in ascending order. Also notice that the grey divider moved only 6 times, which supports the 2nd pros of selection sort mentioned above.

Figure 10: Selection sort gif

1.2. Code Implementation¶

    
import java.util.Arrays;
//@author: Violet Oh

public class Selection_Sort {
    public static void main(String[] args) {
        int[] array = {2, 6, 1, 5, 3, 4}; // The array we discussed.
        System.out.println(Arrays.toString(array));
        SelectionSort(array);
        System.out.println(Arrays.toString(array));
    }
    public static void SelectionSort(int[] array) {
        for (int i = 0; i < array.length - 1; ++i)
        {
            int idxMin = i;
            for (int j = i + 1; j < array.length; ++j)  // Using nested loop.
            {
                if (array[j] < array[idxMin])   // If value at the index of j is smaller than that of i.
                {
                    idxMin = j;
                }
            }
        int temp = array[i];    // The value at the index of i gets stored in an instance variable.
        array[i] = array[idxMin]; // Put the smaller value to the index of i.
        array[idxMin] = temp;   // Replace the swapped value with the smaller value.

        System.out.println(Arrays.toString(array)); // Print it out to see the changes.
        }
    }
}