## Bubble Sort and Quick Sort with C#

One of the most common questions you get asked in technical interviews (as happened to me recently!) is to describe a sorting algorithm, so it’s good to have a couple up your sleeve.

In this post I’ll cover two of the most common sorting algorithms, bubble sort and quicksort, and their implementations in C# – and as usual, you can find all the source code on Github here.

I’ll try and cover some other sorting algorithms in a future post.

**Bubble Sort**

First up, let’s cover bubble sort. This is one of the most basic sorting algorithms.

Bubble Sort works by looping through the numbers, swapping each element with its neighbour provided it’s less than (or greater than, depending on the order you want to sort by). Obviously, every time you swap two elements around, there’s a chance that the remaining elements are no longer in order. As such, we need two loops – the outer loop iterating over the elements, provided they aren’t all considered ordered, and an inner loop that iterates the elements, swapping as necessary (as mentioned above). Every time we swap elements, we need to carry on this process, if no elements are re-ordered, then we need to break out of the loops to save time.

To do this set up a boolean flag (I’ve called mine elementsLeftToSort), and have the first loop continue only if that flag is true (as well as having values left to iterate). This is set to false on each iteration of the outer loop, and is only set to true if numbers are re-ordered – because as mentioned above, if ever we re-order numbers, we then need to check the entire sequence of numbers to see if subsequent changes are required.

This gives you an implementation that may look like this:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | private static int[] BubbleSort(int[] numbersToSort) { bool elementsLeftToSort = true; // While ever we think there are elements that are out of order, continue to loop through all elements for (int i = 1; (i < numbersToSort.Length) && elementsLeftToSort; i++) { // Assume we're in order unless we find otherwise - this breaks the array if no changes are required elementsLeftToSort = false; // Loop around elements in the array, swapping elements as we go for (int j = 0; j < numbersToSort.Length - 1; j++) { // Reverse sorting order by changing the operand from < to > if (numbersToSort[j + 1] < numbersToSort[j]) { SwapElements(numbersToSort, j, j + 1); elementsLeftToSort = true; } } } return numbersToSort; } |

The SwapElements method, which is also used for the Quicksort algorithm below, is just a simple method to swap the position in the array of the two indexes you pass in:

1 2 3 4 5 6 | private static void SwapElements(int[] array, int elementOne, int elementTwo) { var temp = array[elementOne]; array[elementOne] = array[elementTwo]; array[elementTwo] = temp; } |

Given how this is structured, it’s clear that this is not an optimal algorithm for larger datasets, despite it being one of the simplest to understand. The nested looping gives this a worst case complexity of O(n2) – and if more than a few numbers need sorting in to place, you’ll find that this is more or less the average as well. If you’re unfamiliar with Big O Notation, you can find an overview on Wikipedia here.

**Quicksort**

Quicksort is a slightly more complex algorithm than bubble sort, but is still quite simplistic to implement.

Whereas bubble sort works by looping through elements and swapping them individually, quicksort works in a divide and conquer method, based on pivoting sections of the dataset around a value.

Quicksort does this recursively by finding a value to use as the pivot, this gives us two sections of the dataset around that value. This is then applied recursively on each section of the dataset doing the same thing, until each section is considered sorted.

To do this you give the algorithm the array of values, and the low and high indexes of the array. The first step is then to partition the array – a value from the array is picked as the initial value for pivoting (I’m using the last value of the array). We then loop through values in the array, swapping elements until the pivot is in the correct location – all values lower in the array are less than the pivot, all higher are greater than. The position of this pivot element is then used to recursively sort the remaining sections – by using the location +/- 1 to get the pivot value for the remaining sections of the array.

We know when a section of the array has been sorted as we’ll end up with a pivot location less than/greater than the low/high index of the section of array being sorted, thus breaking the recursion on that section.

The resulting implementation may looking something like this:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | private static void Quicksort(int[] numbersToSort, int lowestIndex, int highestIndex) { // If the lowest index is less than the highest index, the section of the array is sorted, and we break the recursion if (lowestIndex < highestIndex) { // Find the location of the pivot element and sort it into position int pivotLocation = PartitionArray(numbersToSort, lowestIndex, highestIndex); // The array is then split into two sections based around the pivot, and each of these sections is sorted recursively // in the same way Quicksort(numbersToSort, lowestIndex, pivotLocation - 1); Quicksort(numbersToSort, pivotLocation + 1, highestIndex); } } private static int PartitionArray(int[] numbersToSort, int lowestIndex, int highestIndex) { // Gets the value from the array to use as the pivot int pivot = numbersToSort[highestIndex]; int i = lowestIndex - 1; // Sort elements in this section of the array correctly around the pivot value // So that only elements less than the pivot are lower, and elements greater than are higher for (int j = lowestIndex; j < highestIndex; j++) { if (numbersToSort[j] <= pivot) { i++; SwapElements(numbersToSort, i, j); } } SwapElements(numbersToSort, i + 1, highestIndex); return i + 1; } |

The sample code I’ve uploaded on Github includes both implementations with a stop watch wrapped around each. An array of random numbers is generated and passed in to be sorted so you can see how long each algorithm takes for different sized arrays.

For example, when I run this locally, with an array of 1000 random integers, I get the following output:

Quicksort has taken 1 milliseconds to complete.

Bubble Sort has taken 8 milliseconds to complete.

While with an array of 10,000 random integers, I get:

Quicksort has taken 11 milliseconds to complete.

Bubble Sort has taken 752 milliseconds to complete.

This shows that while Bubble Sort can be equally effective in small arrays, it is (generally speaking) greatly outstripped by Quicksort on larger datasets.