02. Selection Sort

Algorithm Pseudocode

  1. Start at beginning of the array, where index i = 0.
  2. Move through i to N where N is the length of the array.
  3. Select the min
  4. Swap the min with i.
  5. Increment i and loop.

Visualization

This visualization makes it seem like selection sorting is fast, but in reality, this algorithm iterates through all elements (gray bars) to select the smallest value.

Characteristics

Selection sort is not stable.

Having a runtime of always quadratic, selection sort may present itself as not the best sorting algorithm. However, this algorithm could be useful if the cost of swapping items is high.

Complexity

O(n2) comparisons, O(n) swaps

Implementation in Java

Here's a sample implementation written in Java. Note that it extends the Sort.java class.

import java.util.Arrays;
 
public class SelectionSort extends Sort {
 
  public static void main(String[] args) {
 
    int[] testInt = {1,6,2,3,6,7,4,2,5};
 
    selectionSort(testInt);
    System.out.println(Arrays.toString(testInt));
  }
 
  public static void selectionSort(int[] input) {
 
    for (int i = 0; i < input.length; i++) {
 
      int minIndex = i;
      int min = input[i];
 
      // Iterate through array to find minimal value
      for (int j = i; j < input.length; j++) {
        if (input[j] < min) {
 
          // Replace with new min if new min found
          minIndex = j;
          min = input[j];
        }
      }
 
      // Swap with index at start of search
      swap(input, minIndex, i);
    }
 
  }
 
}

Aching back from coding all day?

Inversion Therapy Table

Aching back from coding all day? Try Back Problems

Stretch out your back and relieve your back muscles with inversion therapy. This device counteracts the forces of gravity on the body by decompressing and elongating the spine. By using this product just ten minutes a day, you can be well on your way to improved circulation and posture while relieving muscle aches, back pain and stress.

$$ Check price
119.98119.98Amazon 4.5 logo(1,700+ reviews)

More Back Problems resources

Learn how data is stored

Data Structures and Algorithms in Java

Learn how data is stored Try Data Structures

Algorithms are the procedures that software programs use to manipulate data structures. Besides clear and simple example programs, the author includes a workshop as a small demonstration program executable on a Web browser. The programs demonstrate in graphical form what data structures look like and how they operate.

$ Check price
64.9964.99Amazon 4.5 logo(97+ reviews)

More Data Structures resources

Ad