Bubble sort

1.Bubble sort

• For each iteration, every element is compared with its neighbor and swapped if they not in order

• The result s in smallest elements bubbling to the beginning of the list

• At the end of the first iteration, the smallest element is in the right position, at the end the second iteration the second smallest is in the right position and so on.

• 兩兩相比, 一次移動一格

• Bubble sort is adaptive: superior to selection sort

2.Procedures

3.Example code (Java)

• Bubble Sort method

public static void bubbleSort(int[] listToSort) {
    for (int i = 0; i < listToSort.length; i++) {
        booblean swapped = false;
        for (int j = i + 1; j < listToSort.length; j++) {
            if (listToSort[j] < listToSort[j - 1]) {
                swap(listToSort, j, j - 1);
                swapped = true;
            }
        }
        print(listToSort);
        if (!swapped) {
            break;
        }
    }
}

• 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

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

• It's adaptive sort

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

  • 因為用原本的list儲存 (in-place 演算法)

• It is a stable sort: logicical order will be maintained

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

  • 比較複雜度是O(N^2)

  • 交換次數是O(N^2)