[Algorithm] Bubble sort

Bubble Sort

• At the i th iteration (0<= i <= n - 1)
  • There are two parts: L[0, n - i - 1] and L[n - i - 1, n - 1]
    • L[0, n - i - 1]: a sublist of items to be already sorted.
    • L[n - i - 1, n - 1]: a sublist of itemsto be sorted.
  • Compare each pair of adjacent itemsand swap them if they are in the wrong order from the unsorted part.

/*
do
  swapped = false
  for i = 1 to indexOfLastUnsortedElement-1
    if leftElement > rightElement
      swap(leftElement, rightElement)
      swapped = true; ++swapCounter
while swapped
*/

void BubbleSort(Data* list, int n)
{
	int temp;
    for (int i = n -1; i > 0; i--)
    {
    	for (int j = 0; j < i; j++)
        {
        	// Compare each pair of adjacent items.
        	if (list[j] > list[j + 1])
            {
            	// Swap if they are in the wrong order.
                SWAP(list[j], list[j + 1], temp);
            }
        }
    }
}

• Time complexity
  • Best case: O(n)
  • Worst case: O(n²)
• Bubble sort is stable.