Selection Sort

Selection sorting a list of N items:

  • Find the smallest item
  • Move it to the front
  • Selection sort the remaining N-1 items (without touching front item!).
Selection sort

Code with Java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// Background: Using Selection to sort a String Array
// 1. Find the Smallest item
public static int findSmallest(String[] x, int start){
    int smallestIndex = start;
    for(int i = start;i<x.length;i++){
        int cmp = x[i].compareTo(x[smallestIndex]);
        if(cmp < 0){
            smallestIndex = i;
        }
    }
    return smallestIndex;
}

// 2. Move it to the front 
public static void swap(String[] x, int a, int b){
    String temp = x[a];
    x[a] = x[b];
    x[b] = temp;
}

// 3. Selection sort the remaining N-1 items (recursion)
public static void sort(String[] x, int start){
    if(start == x.length){
        return;
    }
    int smallestIndex = findSmallest(x,start);
    swap(x,start,smallestIndex);
    sort(x,start+1);
}