Time complexity:

Worst-case: \(O(n^2)\)

Best-case: \(O(n)\)

Average-case: \(O(n^2)\)

Sort array elements in ascending order. If the first element is greater than the second element, swap the first two elements.

Then, we go to the “next pair” and so on.

void BubbleSort(int *list, int size)
{
    int i, j, swapCount = 0, runningCount = 0, isSwapped = 0;
    for(i=0;i<size;i++)
    {
        isSwapped = 0;
        for(j=0;j<size-i-1;j++)
        {
            runningCount++;
            if(list[j] > list[j+1])
            {
                swap(&list[j], &list[j+1]);
                swapCount++;
                isSwapped++;
            }
        }
        if(isSwapped == 0)
            break;
    }
}

void swap(int *x, int *y)
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

For example, to sort an array of size 7.

Case I: Worst-case

int worstList[] = {23,20,18,14,10,6,3};

swapCount = 21 and runningCount = 21

Case II: Best-case

int bestList[] = {3, 6, 10, 14, 18, 20, 23};

swapCount = 0 and runningCount = 6

Case III: Average-case

int averageList[] = {20, 6, 23, 3, 18, 14, 10};

swapCount = 13 and runningCount = 20

 

Unsorted Array: 20, 6, 23, 3, 18, 14, 10

Step01. (20, 6), 23, 3, 18, 14, 10  ->  (6, 20), 23, 3, 18, 14, 10

Step02. 6, (20, 23), 3, 18, 14, 10  ->  without swapping

Step03. 6, 20, (23, 3), 18, 14, 10  ->  6, 20, (3, 23), 18, 14, 10

Step04. 6, 20, 3, (23, 18), 14, 10  ->  6, 20, 3, (18, 23), 14, 10

Step05. 6, 20, 3, 18, (23, 14), 10  ->  6, 20, 3, 18, (14, 23), 10

Step06. 6, 20, 3, 18, 14, (23, 10)  ->  6, 20, 3, 18, 14, (10, 23)

——————————————————————————————

Step07. (6, 20), 3, 18, 14, 10, 23  ->  without swapping

Step08. 6, (20, 3), 18, 14, 10, 23  ->  6, (3, 20), 18, 14, 10, 23

Step09. 6, 3, (20, 18), 14, 10, 23  ->  6, 3, (18, 20), 14, 10, 23

Step10. 6, 3, 18, (20, 14), 10, 23  ->  6, 3, 18, (14, 20), 10, 23

Step11. 6, 3, 18, 14, (20, 10), 23  ->  6, 3, 18, 14, (10, 20), 23

——————————————————————————————​

Step12. (6, 3), 18, 14, 10, 20, 23  ->  (3, 6), 18, 14, 10, 20, 23

Step13. 3, (6, 18), 14, 10, 20, 23  ->  without swapping

Step14. 3, 6, (18, 14), 10, 20, 23  ->  3, 6, (14, 18), 10, 20, 23

Step15. 3, 6, 14, (18, 10), 20, 23  ->  3, 6, 14, (10, 18), 20, 23

——————————————————————————————​

Step16. (3, 6), 14, 10, 18, 20, 23  ->  without swapping

Step17. 3, (6, 14), 10, 18, 20, 23  ->  without swapping

Step18. 3, 6, (14, 10), 18, 20, 23  ->  3, 6, (10, 14), 18, 20, 23

——————————————————————————————​

Step19. (3, 6), 10, 14, 18, 20, 23  ->  without swapping

Step20. 3, (6, 10), 14, 18, 20, 23  ->  without swapping -> Break!!

—————————————————————————————––​

Sorted Array: 3, 6, 10, 14, 18, 20, 23 

 

Python:

def BubbleSort(data):
   data_len = len(data)
   print("Data Length: ",data_len)
   for i in range(0,data_len):
      swapped = 0;
      for j in range(0,data_len-i-1):
         if data[j] > data[j+1]:
            tmp = data[j]
            data[j] = data[j+1]
            data[j+1] = tmp
            swapped += 1;
      if swapped == 0:
         break;