Selection sort

1.Selection sort

• At each iteration 1 element is selected and compared with every other element in the list to find the smallest one

• Selection sort selects one element at a time, compare it to all other elements in the list

  • The correct position for that selected element is found before moving on to the next element

2.Procedures

1. 一開始選擇list中的第一個元素, 將這個元素依序與每個其他元素相比, 若是比較大則swap, 找到最小的元素

2. 選擇第2個元素與其他剩下的元素比較, 找到最小的元素

3. 重複1 ~ 2作完整個序列

3.Example code (Java)

• SelectionSort method

public static void selectionSort(int[] listToSort) {
    for (int i = 0; i < listToSort.length; i++) {
        for (int j = i + 1; j < listToSort.length; j++) {
            if (listToSort[i] > listToSort[j]) {
                swap(listToSort, i, j);
                print(listToSort);
            }
        }
    }
}

• Helper method

  • Swap

  public static void swap(int[] listToSort, int iIndex, int jIndex) {
      int temp = listToSort[iIndex];
      listToSort[iIndex] = listToSort[jIndex];
      listToSort[jIndex] = temp;
  }

  • Print

  public static void print(int[] listToSort) {
      for(int el: listToSort) {
          System.out.print(el + ",");
      }
      System.out.println();
  }

4.Complexity

• In the worst case "N" elements are checked for every selected element

  • Complexity of selection sort is O(N^2)

• It is not a stable sort: entities which are equal might be re-arranged

• It takes O(1) extra space, it sorts in space

  • 因為用原本的list儲存

• It makes O(N^2) comparisons and O(N) swaps

• It's not adaptive sort