Programming: Sort

Sort

Bubble Sort: O(N^2)

Repeatedly steps through the input list element by element, comparing the current element with the one after it, swapping their values if needed.

• It will start by comparing index 0 with 1
• If index 0 is greater than 1, it will swap them
• Then it will compare index 1 with 2
• At the end of the first iteration, the largest element will be at the end of the list
• In the second iteration, we will not include the last element. We will continue until we have no more elements to compare:

  # number of comparations
N
N-1
N-2
...

This is a Gauss sum:

N + N-1 + ... + 2 + 1 = N(N+1)/2 -> O(N^2)

void bubbleSort(int array[], int size) {
  // check if swapping occurs
  int swapped;

  // run loops two times: one for walking throught the array
  for (int i = 0; i < size - 1; ++i) {
    swapped = 0;
    // loop to compare array elements
    for (int j = 0; j < size - i - 1; ++j) {
      // compare two adjacent elements
      if (array[j] > array[j + 1]) {
        // swapping
        int temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;

        swapped = 1;
      }
    }
    // already sorted
    if (swapped == 0) {
      break;
    }
  }
}

Optimized Bubble Sort

• Worst-case performance: O(N^2), O(N^2) swaps
• Best-case performance: O(1)
• Average performance: O(lg N)
• Worst-case space complexity: O(1)

ℹ️ Note Code examples in different languages are available in gitgub.