Search

# Bubble Sort

It is the simplest sorting algorithm that repeatedly steps through the list, compares adjacent elements and swap them if they are in wrong order.

The pass through the list is repeated until the list is sorted.

Example:

First pass:

(8 3 5 4 9) => (3 8 5 4 9), Here it compares the first two elements and swaps since 8>3.

(3 8 5 4 9) => (3 5 8 4 9), Swap since 8>5.

(3 5 8 4 9) => (3 5 4 8 9), Swap since 8>4.

(3 5 4 8 9) => (3 5 4 8 9), Now since these elements are already in order(8>5), algorithm does not swap them.

Second Pass:

(3 5 4 8 9) => (3 5 4 8 9)

(3 5 4 8 9) => (3 4 5 8 9), Swap since 5>4

(3 4 5 8 9) => (3 4 5 8 9)

(3 4 5 8 9) => (3 4 5 8 9)

Now, the array is already sorted, but our algorithm does not know if it is sorted or not. The algorithm needs one whole pass without any swap to know it is sorted.

Third Pass:

(3 4 5 8 9) => (3 4 5 8 9)

(3 4 5 8 9) => (3 4 5 8 9)

(3 4 5 8 9) => (3 4 5 8 9)

(3 4 5 8 9) => (3 4 5 8 9)

Another visual example:

Pseudo code:

```procedure bubble_Sort( list : array of items )

loop = list.count;

for i = 0 to loop-1 do:
swapped = false

for j = 0 to loop-1 do:

if list[j] > list[j+1] then
// swap them
swap( list[j], list[j+1] )
swapped = true
end if

end for

/*if no number was swapped that means
array is sorted now, break the loop.*/

if(not swapped) then
break
end if

end for

end procedure return list```

Implementation using C:

```#include <stdio.h>

void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}

// An optimized version of Bubble Sort
void bubbleSort(int arr[], int n)
{
int i, j;
int swapped=1;
for (i = 0; i < n-1; i++)
{
swapped = 0;
for (j = 0; j < n-i-1; j++)
{
if (arr[j] > arr[j+1])
{
swap(&arr[j], &arr[j+1]);
swapped = 1;
}
}

// IF no two elements were swapped by inner loop, then break
if (swapped == 0)
break;
}
}

/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}

// Driver program to test above functions
int main()
{
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr);
bubbleSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}```
```Output:
Sorted array:
11 12 22 25 34 64 90```

Miscellaneous:

In-place: Yes

Stable: Yes

Worst case & Average case: O(n*n), occurs when array is reverse sorted.

Best case: O(n), occurs when array is already sorted.

13 views

See All