Bubble sort algorithm

First section of part one, this covers bubble sort algorithm.
Largest values are "Bubbled up" on each pass by swapping them between current element and next element. Each comparison is run n-1 times over n-1 passes. This leads to a time complexity of O((n-1)^2) or O(n^2). 
We can detect if data was sorted by checking if any swaps took place. If no swap, we stop the algorithm and this leads to O(n) time on data that is already sorted.

Let's look at how this works by using an unsorted array 6 1 3 2 7 5 4.
In the first pass we scan the entire array "bubbling up" the largest value to the end whose index starts from zero and goes up to six.
In the first pass we compare the entire array starting at index zero by comparing element at index with element at index + one. In our example we see if 6 > 1 and it is so we swap and have a new array 1 6 3 2 7 5 4.
We increment the counter still within first pass and now check if 6 > 3. Yes it is so we swap and get 1 3 6 2 7 5 4. Carrying on we get:
1 3 2 6 7 5 4
1 3 2 6 7 5 4
1 3 2 6 5 7 4
1 3 2 6 5 4 7
First pass done and the largest value, seven, in this pass is now at the end.

The second pass will start from zero again but only up to five because in the previous pass the 6th element has the largest value of the array and thus is in its final location.

For completeness here is what the second pass will look like:
initial: 1 3 2 6 5 4 7
1 3 2 6 5 4 7 //no change as 1 > 3 is not true.
1 2 3 6 5 4 7 //swapped 3 and 2 as 3 > 2.
1 2 3 6 5 4 7 //no change as 3 > 6 is not true.
1 2 3 5 6 4 7 //swapped 6 and 5 as 6 > 5.
1 2 3 5 4 6 7 //swapped 6 and 4 as 6 > 4.
Done second pass.

If we look at this carefully we can see that in any given pass, if no swap takes place then the data must already be in their correct sorted order. If we detect that no swap takes place we can reduce the time complexity on sorted data to a single pass of O(n).  In the above example at the completion of pass two we can see that the algorithm only needs to run pass three before all the data is sorted and no more passes is required. Without this check bubble sort is always an O(n^2) algorithm regardless of the condition of the collection.

The bubble sort algorithm code is shown below complete with a check for swaps. It returns the number of passes that was done.

public int BubbleSort(ref int[] array)
{
  int swapped = 0;
  int i;
  for (i = array.Length-1; i >= 0; i--)
  {
    swapped = 0;
    for (int j = 0; j < i; j++)
    {
      if (array[j] > array[j + 1])
      {
        Swap(ref array, j, j + 1);
        swapped++;
      }
    }
    //No swap, data is already sorted, no need to continue.
    if (swapped == 0) break; 
  }
  return array.Length - i; //Returns the pass count.
}

How does the above code work:
There are two for-loops where the first for loop determines the number of passes and runs through n passes referred to as index 'i'. The second loop using index 'j' will run from zero up to 'i' and since at each pass 'i' reduces by one then 'j' will always start at zero and run through to the length of the current pass 'i' each time the second loop executes. The second loop counts how many swaps have occurred and if zero swaps has occurred then this detects that the data must already be sorted and terminates the algorithm. In this second loop each item at index j and j+1 is compared and swapped as necessary. As an option the method returns the number of passes that has occurred during this run.

This concludes the bubble sort algorithm.
Next: Selection Sort.
Previous: Landing page Part One.