There are limited ways to search a list that is unsorted. It is often more efficient to sort a list and then search it. One of the most basic sorting algorithms is called
This basic approach to sorting narrows the scope of our problem to focusing on ordering just two elements at a time, instead of an entire array at a time. This approach is very straightforward, but possibly at the expense of making an inordinate number of swaps just to put one single element into position.
Bubble Sort Implementation
Bubble sort works by comparing two adjacent numbers in a list, and swapping them if they are out of order. Looking at the example on the left, if we are given an array of the numbers 5, 1, 6, 2, 4, and 3 and we wanted to sort it using bubble sort our pseudocode for one single pass might look something like this:
for every element in the array check if element to the right is smaller if so swap the two elements else move on to the next element in the list
When this is implemented on the example array, the program would start at 5 and compare it with 1. Since 1 is smaller than 5 it would swap them. It would then move on to compare 5 and 6 since those are in the correct order, we just move on to the next element. Next 6 and 2 are compared, and so on.
Finally, after doing this for all the elements in the array, we are left with the array 1, 5, 2, 4, 3, and 6. It’s not completely sorted, but notice that after the first pass through, the 6 is already in its correct location. After n pass-throughs, the last n elements are in their correct position. This fact can be used to optimize this algorithm since it is not necessary to look at those correctly sorted elements. It is this effect of the larger elements “bubbling” to the right side that gives this algorithm its name!
If bubble sort was implemented only as above, we would only go through one passthrough, but as the example shows, it is not guaranteed that the array will be sorted after one pass. So how many times should this algorithm be run? Well in the worst-case scenario, a reverse sorted
How can you ensure you only run this algorithm the necessary amount of times, maybe saving a few steps? Well, if this algorithm is run and no swaps are made, it must be true that the array is sorted (think about it)! Maybe then it would make sense to amend our implementation to include a counter for the
array. Now we only decide at the end of every passthrough whether more pass-throughs are necessary!