Selection Sort

Overview of Selection sort

Selection sort is a very simple sorting algorithm. It is similar to insertion sort and is inefficient for sorting large arrays.

In this chapter, we’ll review the selection sort algorithm and analyze its performance.

Selection Sort Algorithm

Selection sort works by finding the smallest element in the array and swapping it with the first element of the array. Then find the smallest element in the remaining part of the array, and swap it with the second element of the array

for i in (0 to a.end)
    min = index of smallest element of a[i to a.end]
    swap(a[i], a[min])

Selection sort proceeds in stages. At the start of each stage, the array will be partitioned into a two disjoint regions. The upper region will contain those elements already in sorted order. The lower region will contain those elements that are not necessarily sorted. (They might be by chance.) The upper region will also have the property that every element in it is greater than or equal to any element in the unsorted region.

The action performed during each stage is therefore to and the largest key in the unsorted region and put it into the lowest position of the sorted region. Since it was in the unsorted region, it is less than or equal to every key in the sorted region. By placing it in the lowest position in the sorted region it preserves the ordering of that region. In addition, the size of the unsorted region is reduced by one. This implies that after n steps, where n is the number of elements, the unsorted region will be size zero, or that the array has been sorted.

The following function defines selection sort of an array A of size n. T is the underlying element type. The index_of_maximum_key() function performs a linear search of its array argument from index 0 to index last for the key with maximum value and returns its index. The swap() function swaps its arguments.

void SelectionSort(T A[], int n) {
  // Precondition: A[0..n-1] contains the data to be sorted
  // Postcondition: A[0..n-1] is sorted in ascending order.
  int largest; // index of largest item in unsorted part of array
  int last; // index of last item in unsorted part of array
  for (int last = n - 1; last >= 1; last--) {
    // Invariant: A[last+1...n-1] is already sorted and
    // if j <= last and k > last, A[j] <= A[k]
    largest = index_of_maximum_key(A, last);
    swap(A[largest], A[last]);
  }
}

Analysis of Selection sort (Time and Space Complexity)

In short,

  • Worst-case performance: \(O\left(N^{2}\right)\)
  • Worst-case space complexity: O(1) (in-place)

Let’s review the C++ function from the previous section. During each iteration of the loop, index_of_maximum_key() is called once with an array of size last+1. To find the maximum element in an array of size n, n-1 comparisons must be performed. (Why not n?) Therefore, the function performs last comparisons when its second argument is last. Since last runs from n-1 down to 1, the total number of key comparisons is the sum of the numbers 1, 2, 3,…, n-1, which is n(n − 1)/2. Notice that the total number of key comparisons performed by selection sort is the same in all cases - it does not depend on the data.

The swap() function performs a constant number of data exchanges. To swap two elements requires three assignments. It is called once in each iteration of the loop. Since there are (n − 1) iterations, there are 3(n − 1) data exchanges caused by swap(). As there is no other data movement in the algorithm, the total number of data exchanges is 3(n − 1). This too is independent of the original state of the data.

Expressing these results in order notation, we can see that selection sort has a worst case, average case, and best case running time that is \(O\left(N^{2}\right)\).

Common Selection Sort Questions

1. Is selection sort in-place sorting algorithm?

Yes, selection sort is an in-place sorting algorithm. It doesn’t use extra space and sorts the array in place.

2. Is selection sort adaptive?

No. In adaptive algorithms, the complexity (running time, performance) changes based on whether or not the input array is sorted. They perform better when the input is sorted. Selection sort is not adaptive because the initial order of the array has no impact on the number of comparisons.

3. Is selection sort stable?

No. Stable means that if two elements have the same value, they remain in the same position. Selection sort is not stable.

4. Is selection sort divide and conquer?

No. A divide and conquer algorithm continuously breaks down a bigger problem into sub-problems, until they become simple enough to be solved directly. Selection sort doesn’t do that and hence it is not a divide and conquer algorithm.

Code Examples

Selection sort in Java

private static void selectionSort(int a[]) {
    for (int i = 0; i < a.length-1; i++) {
        /* assume the min is the first element */
        int jMin = i;
        /* test against elements after i to find the smallest */
        for (int j = i+1; j < a.length; j++) {
            /* if this element is less, then it is the new minimum */
            if (a[j] < a[jMin]) {
                jMin = j;
            }
        }

        if (jMin != i) {
            swap(a[i], a[jMin]);
        }
    }
}

See this for a complete example and explanation of Selection Sort using Recursion.

Other Sorting Algorithms


Licenses and Attributions


Speak Your Mind

-->