# Bubble Sort

Bubble sort is a sorting algorithm that repeatedly goes through an array and swaps adjacent elements if they are not in order. The algorithm is repeated until the list is sorted.

Example

Sort the given array {3, 2, 5, 1, 4}.

To start we compare 3 and 2.

3 is less than 2 so they are swapped.

Now compare 3 to 5.

3 is less than 5 so they are not swapped.

Next compare 5 to 1.

5 is greater than 1 so they are swapped.

Now compare 5 to 4.

5 is greater than 4 so they are swapped.

Now that we are at the end of the array we will go through the array again and complete the same process. This time we do not need to check the last element of the array because it will be the largest number.

Compare 2 to 3.

2 is less than 3 so they are not swapped.

Compare 3 to 1.

3 is larger than 1 so they are swapped.

Compare 3 to 4.

3 is less than 4 so they are not swapped.

This time around 4 is considered the last element of the array so this loop is done.

Going back through we compare 2 to 1.

2 is greater than 1 so they are swapped.

Compare 2 to 3.

2 is less than 3 so they are not swapped.

3 is the new last element of the array so this loop is done. Because there was a swap in this loop we have to go through the loop again.

Compare 1 to 2.

1 is less than 2 so they are not swapped.

2 was the new last element so the loop is done. Because there were no swaps the loop does not need to run again.

This algorithm's best-case scenario has a time complexity of O(n) when the array is already sorted. The algorithm’s worst-case scenario has a time complexity of O(n²) when the array is reverse sorted.

Code Implementation

To implement bubble sort you will create a function to sort an array. It will take two parameters. One is an array and the second is the size of the array.

In this function, you will create a bool variable to determine if a swap has occurred.

Create a for loop to pass through the array. At the start of each pass, you will set the swapped variable to false.

Now you will create a nested for loop that will pass through the array. This for loop will compare each element in the array and swap them if they are not in the correct order. If a swap happens you will set the swapped variable to true.

After the nested for loop completes you will check if the swapped variable is false. If it is false you will break out of the for loop. If it is true you will run the loop again.

For this example, I have created a function to print the array.

In the main function, I created an array and a variable to hold the size of the array. I then ran the print array function and sort function.

When this is run it will print the original array and the sorted array.

This is the full script.

--

--