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);
    }
 
  }
 
}

Learn how data is stored

Data Structures and Algorithms Made Easy

Learn how data is stored Try Data Structures

A handy guide of sorts for any computer science professional, Data Structures And Algorithms Made Easy in Java: Data Structure And Algorithmic Puzzles is a solution bank for various complex problems related to data structures and algorithms. It can be used as a reference manual by those readers in the computer science industry.

$ Check price
39.9939.99Amazon 4.5 logo(339+ reviews)

More Data Structures resources

Aching back from coding all day?

Self-Massage Tool

Aching back from coding all day? Try Back Problems

Relieve spasms, tight muscles, trigger points and pressure points with the Body Back Buddy! This trigger point massage is designed to help you self-message any area of your body - especially those that are hard to reach. Keeping your muscles relaxes and out of contraction is importan in helping to reduce pain and prevent muscle injury.

$ Check price
29.9529.95Amazon 4.5 logo(3,443+ reviews)

More Back Problems resources

Ad