Bubble Sort - Visual-Rock/CodeSnippets GitHub Wiki
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order.
| ' | Worst case | Average case | Best case |
|---|---|---|---|
| comparisons | O(nĀ²) | O(nĀ²) | O(n) |
| swaps | O(nĀ²) | O(nĀ²) | O(1) |
| space total | O(n) | O(n) | O(n) |
| space auxiliary | O(1) | O(1) | O(1) |
youtube video: https://www.youtube.com/watch?v=nmhjrI-aW5o
Unoptimized:
procedure bubbleSort(A : list of sortable items)
n := length(A)
repeat
swapped := false
for i := 1 to n-1 inclusive do
/* if this pair is out of order */
if A[i-1] > A[i] then
/* swap them and remember something changed */
swap(A[i-1], A[i])
swapped := true
end if
end for
until not swapped
end procedureOptimized:
procedure bubbleSort(A : list of sortable items)
n := length(A)
repeat
swapped := false
for i := 1 to n - 1 inclusive do
if A[i - 1] > A[i] then
swap(A[i - 1], A[i])
swapped = true
end if
end for
n := n - 1
until not swapped
end procedure
( 5 1 4 2 8 ) ā> ( 1 5 4 2 8 ), Here, the 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.
( 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 )
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.
( 1 2 4 5 8 ) ā> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ā> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ā> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ā> ( 1 2 4 5 8 )
// Creates a template parameter T
template <class T>
// Swaps two Array Element pointers
void swap(T* a, T* b)
{
// Stores a pointer to a's value in t
T t = *a;
// asigns the value of b to a
*a = *b;
// asigns the value of t to b
*b = t;
}
// Creates a template parameter T
template <class T>
// Bubble Sort repeatedly steps through the list,
// compares adjacent elements and swaps them if they are in the wrong order
void bubble_sort(T arr, int arr_length)
{
// a boolean that shows if the Array is sorted or not
bool is_sorted = false;
// Sorts the Array until isSorted is true what means that
// the Array is sorted
while (!is_sorted)
{
// Sets isSorted to true (even if the array is not sorted)
// to escape from the loop when it is sorted
is_sorted = true;
// loops through the Array and compares adjacent elements
for (int i = 0; i < arr_length - 1; i++)
{
// Checks if the current Array Element is Bigger than the next
// Array Element.
// if you want the Array from Biggest to Smallest just change
// the > to an <.
if (arr[i] > arr[i + 1])
{
// swaps the Current Array Element and the
// next Array Element because ther are out of order
swap(&arr[i], &arr[i + 1]);
// sets isSorted to false because the Array is possibly not sorted
is_sorted = false;
}
}
}
}// Creates a template parameter T
template <class T>
// Bubble Sort repeatedly steps through the list,
// compares adjacent elements and swaps them if they are in the wrong order
// Ignores all Sorted Elements
void bubble_sort_optimized(T arr, int arr_length)
{
// loops through the Array and splits sorted and unsorted Array
for (int i = arr_length; i != 0; i--)
{
// loops through the unsorted Array to sort it
for (int j = 0; j < i; j++)
{
// Checks if the current Array Element is Bigger than the next
// Array Element.
// if you want the Array from Biggest to Smallest just change
// the > to an <.
if (arr[j] > arr[j + 1])
{
// swaps the Current Array Element and the
// next Array Element because ther are out of order
swap(&arr[j], &arr[j + 1]);
}
}
}
}https://www.geeksforgeeks.org/bubble-sort/
https://en.wikipedia.org/wiki/Bubble_sort