Search

Selection Sort

Selection Sort is an unstable comparison sort algorithm with poor performance. Selection Sort uses the selection method and performs at O(n2) in the best, average, and worst case.

Table of contents

Performance

Best
Ω(n2)
Average
Θ(n2)
Worst
O(n2)

Code

public class SelectionSort {
    public static void main(String[] args)
    {
        int[] array = {12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8};
        selectionSort(array);
        System.out.println(java.util.Arrays.toString(array));
    }

    static void selectionSort(int[] array)
    {
        // step 1: loop from the beginning of the array to the second to last item
        for (int currentIndex = 0; currentIndex < array.length - 1; currentIndex++)
        {
            // step 2: save a copy of the currentIndex
            int minIndex = currentIndex;
            // step 3: loop through all indexes that proceed the currentIndex
            for (int i = currentIndex + 1; i < array.length; i++)
            {
                // step 4:  if the value of the index of the current loop is less
                //          than the value of the item at minIndex, update minIndex
                //          with the new lowest value index */
                if (array[i] < array[minIndex])
                {
                    // update minIndex with the new lowest value index
                    minIndex = i;
                }
            }
            // step 5: if minIndex has been updated, swap the values at minIndex and currentIndex
            if (minIndex != currentIndex)
            {
                int temp = array[currentIndex];
                array[currentIndex] = array[minIndex];
                array[minIndex] = temp;
            }
        }
    }
}
public class SelectionSortGeneric<T extends Comparable<? super T>> {
    public static void main(String[] args)
    {
        // example using Strings
        String[]                     arrayOfStrings = {"Andree", "Leana", "Faviola", "Loyce", "Quincy", "Milo", "Jamila", "Toccara", "Nelda", "Blair", "Ernestine", "Chara", "Kareen", "Monty", "Rene", "Cami", "Winifred", "Tara", "Demetrice", "Azucena"};
        SelectionSortGeneric<String> stringSorter   = new SelectionSortGeneric<>();
        stringSorter.selectionSort(arrayOfStrings);
        System.out.println(java.util.Arrays.toString(arrayOfStrings));

        // example using Doubles
        Double[]                     arrayOfDoubles = {0.35, 0.02, 0.36, 0.82, 0.27, 0.49, 0.41, 0.17, 0.30, 0.89, 0.37, 0.66, 0.82, 0.17, 0.20, 0.96, 0.18, 0.25, 0.37, 0.52};
        SelectionSortGeneric<Double> doubleSorter   = new SelectionSortGeneric<>();
        doubleSorter.selectionSort(arrayOfDoubles);
        System.out.println(java.util.Arrays.toString(arrayOfDoubles));
    }

    void selectionSort(T[] array)
    {
        // step 1: loop from the beginning of the array to the second to last item
        for (int currentIndex = 0; currentIndex < array.length - 1; currentIndex++)
        {
            // step 2: save a copy of the currentIndex
            int minIndex = currentIndex;
            // step 3: loop through all indexes that proceed the currentIndex
            for (int i = currentIndex + 1; i < array.length; i++)
            {
                // step 4:  if the value of the index of the current loop is less
                //          than the value of the item at minIndex, update minIndex
                //          with the new lowest value index */
                if (array[i].compareTo(array[minIndex]) < 0)
                {
                    // update minIndex with the new lowest value index
                    minIndex = i;
                }
            }
            // step 5: if minIndex has been updated, swap the values at minIndex and currentIndex
            if (minIndex != currentIndex)
            {
                T temp = array[currentIndex];
                array[currentIndex] = array[minIndex];
                array[minIndex] = temp;
            }
        }
    }
}
#include <iostream>
#include <vector>

void selectionSort(std::vector<int> &arr) {
    // step 1: loop from the beginning of the array to the second to last item
    for (int currentIndex = 0; currentIndex < arr.size() - 1; currentIndex++) {
        // step 2: save a copy of the currentIndex
        int minIndex = currentIndex;
        // step 3: loop through all indexes that proceed the currentIndex
        for (int i = currentIndex + 1; i < arr.size(); i++) {
          /* step 4:  if the value of the index of the current loop is less
                      than the value of the item at minIndex, update minIndex
                      with the new lowest value index */
            if (arr[i] < arr[minIndex]) {
                // update minIndex with the new lowest value index
                minIndex = i;
            }
        }
        // step 5: if minIndex has been updated, swap the values at minIndex and currentIndex
        if (minIndex != currentIndex) {
            int temp = arr[currentIndex];
            arr[currentIndex] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

int main() {
    std::vector<int> arr = {12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8};
    selectionSort(arr);
    for (int i; i < arr.size(); i++) {
        std::cout << arr[i];
        if (i < arr.size() - 1) std::cout << ", ";
    }
}
func selectionSort(array: inout [Int]) {
    // step 1: loop from the beginning of the array to the second to last item
    for currentIndex in 0..<(array.count - 1) {
        // step 2: save a copy of the currentIndex
        var minIndex = currentIndex;
        // step 3: loop through all indexes that proceed the currentIndex
        for i in (currentIndex + 1)..<array.count {
            // step 4:  if the value of the index of the current loop is less
            //          than the value of the item at minIndex, update minIndex
            //          with the new lowest value index */
            if (array[i] < array[minIndex]) {
                // update minIndex with the new lowest value index
                minIndex = i;
            }
        }
        // step 5: if minIndex has been updated, swap the values at minIndex and currentIndex
        if (minIndex != currentIndex) {
            let temp = array[currentIndex];
            array[currentIndex] = array[minIndex];
            array[minIndex] = temp;
        }
    }
}

var array = [12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8]
selectionSort(array: &array)
print(array)
function selectionSort(array) {
  // step 1: loop from the beginning of the array to the second to last item
  for (let currentIndex = 0; currentIndex < array.length - 1; currentIndex++) {
    // step 2: save a copy of the currentIndex
    let minIndex = currentIndex;
    // step 3: loop through all indexes that proceed the currentIndex
    for (let i = currentIndex + 1; i < array.length; i++) {
      /* step 4:  if the value of the index of the current loop is less
                  than the value of the item at minIndex, update minIndex
                  with the new lowest value index */
      if (array[i] < array[minIndex]) {
        // update minIndex with the new lowest value index
        minIndex = i;
      }
    }
    // step 5: if minIndex has been updated, swap the values at minIndex and currentIndex
    if (minIndex != currentIndex) {
      let temp = array[currentIndex];
      array[currentIndex] = array[minIndex];
      array[minIndex] = temp;
    }
  }
}

let array = [12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8]
selectionSort(array)
alert(array)
def selection_sort(array):
    # step 1: loop from the beginning of the array to the second to last item
    currentIndex = 0
    while (currentIndex < len(array) - 1):
        # step 2: save a copy of the currentIndex
        minIndex = currentIndex
        # step 3: loop through all indexes that proceed the currentIndex
        i = currentIndex + 1
        while (i < len(array)):
            # step 4:   if the value of the index of the current loop is less
            #           than the value of the item at minIndex, update minIndex
            #           with the new lowest value index
            if (array[i] < array[minIndex]):
                # update minIndex with the new lowest value index
                minIndex = i
            i += 1
        # step 5: if minIndex has been updated, swap the values at minIndex and currentIndex
        if (minIndex != currentIndex):
            temp = array[currentIndex]
            array[currentIndex] = array[minIndex]
            array[minIndex] = temp
        currentIndex += 1

if __name__ == '__main__':
    array = [12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8]
    selection_sort(array)
    print(array)

Walkthrough

Selection Sort executes in the following steps:

  1. Loop from the beginning of the array to the second to last item.
  2. Save a copy of the currentIndex. This index will represent the index with the lowest value so we named it minIndex.
  3. Loop through all indexes that proceed the currentIndex.
  4. If the value of the index of the current loop is less than the value of the item at minIndex, update minIndex with the new lowest value index.
  5. if minIndex has been updated, swap the values at minIndex and currentIndex.

Discussion