Selection Sort
by Isai Damier, Android Engineer @ Google

/****************************************************************************
 * Author: Isai Damier
 * Title: Selection Sort
 * Project: geekviewpoint
 * Package: algorithm.sorting
 *
 * Statement:
 *   Given a disordered list of integers (or any other items),
 *   rearrange the integers in natural order.
 *
 * Sample Input: {18,5,3,1,19,6,0,7,4,2,5}
 * Sample Output: {0,1,2,3,4,5,5,6,7,18,19}
 *
 * Time Complexity of Solution:
 *   Best O(n^2); Average O(n^2); Worst O(n^2).
 *
 * Approach:
 *   Selection sort is a step up from insertion sort from a memory viewpoint.
 *   It only swaps elements that need to be swapped. In terms of time
 *   complexity, however, insertion sort is better.
 ***************************************************************************/ 
 public void selectionsort(int[] input) {
  for (int i = 0, k, least; i < input.length; i++) {
    for (k = i + 1, least = i; k < input.length; k++) {
      if (input[k] < input[least]) {
        least = k;
      }
    }
    swap(input, least, i);
  }
}

private void swap(int[] input, int a, int b) {
  int tmp = input[a];
  input[a] = input[b];
  input[b] = tmp;
}

import org.junit.Test;
import static org.junit.Assert.*;

public class SortingTest {

  @Test
  public void testSelectionsort() {
    System.out.println(""selectionsort"");
    int[] input = {18, 5, 3, 1, 19, 6, 0, 7, 4, 2, 5};
    Sorting instance = new Sorting();
    instance.selectionsort(input);
    for (int i = 1; i < input.length; i++) {
      if (input[i - 1] > input[i]) {
        fail(""selectionsort method fails."");
      }
    }
  }
}