Bubble Sort
Big O:
Bubble sort works by repeatedly swapping adjacent elements if they are in the wrong order. not really suitable for large data sets
How It Works
Say you have an array arr[] = {5,1,4,2,8}
.
First Pass
Bubble sort will start with the first to elements and compare them to see which is greater.
- ( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
- ( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4
- ( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2
- ( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.
Second Pass:
- ( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
- ( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2
- ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
- ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
Third Pass
The array is sorted, but it still needs to run through to ensure that it's still sorted.
Example C++
`// of Bubble sort`
`#include <bits/stdc++.h>`
`using` `namespace` `std;`
`// A function to implement bubble sort`
`void` `bubbleSort(``int` `arr[],` `int` `n)`
`{`
`int` `i, j;`
`for` `(i = 0; i < n - 1; i++)`
`// Last i elements are already`
`// in place`
`for` `(j = 0; j < n - i - 1; j++)`
`if` `(arr[j] > arr[j + 1])`
`swap(arr[j], arr[j + 1]);`
`}`
`// Function to print an array`
`void` `printArray(``int` `arr[],` `int` `size)`
`{`
`int` `i;`
`for` `(i = 0; i < size; i++)`
`cout << arr[i] <<` `" "``;`
`cout << endl;`
`}`
`// Driver code`
`int` `main()`
`{`
`int` `arr[] = { 5, 1, 4, 2, 8};`
`int` `N =` `sizeof``(arr) /` `sizeof``(arr[0]);`
`bubbleSort(arr, N);`
`cout <<` `"Sorted array: \n"``;`
`printArray(arr, N);`
`return` `0;`
`}`