Selection Sort

From NovaOrdis Knowledge Base
Jump to navigation Jump to search

Internal

Overview

It is an in-place sorting algorithm.

The best case and the worst case running time are both Θ(n2).

Algorithm

Selection sort scans the input array from left to right, determining the minimum elements in the subarray spanning from the current position to the end of the input array and then swap the current element with the minimum.

public void sort(int[] a) {
  for(int i = 0; i < a.length - 1; i ++) {
    int minIndex = i;
    for(int j = i + 1; j < a.length; j ++) {
      if (a[j] < a[minIndex]) {
        minIndex = j;
      }
    }
    if (i != minIndex) {
      //
      // swap
      //
      int tmp = a[i];
      a[i] = a[minIndex];
      a[minIndex] = tmp;
    }
  }
}