Bubble sort in C#

Bubble sort - overview

Bubble sort is a simple sorting algorithm. It is used to sort an array of for example integers or strings.

Description of the bubble sort algorithm

Bubble sort starts by comparing the first two elements in the array. If the first element is greater than the second, the two values are swapped.

Then the algorithm moves to the next position in the array. It will compare the next two adjacent values and swap them if they are in the wrong order. It will continue doing this until the end of the array has been reached.

After one round is finished another round is started. The first two elements are compared and swapped if necessary, then it moves to the next position, then to the next, and so on.

In this way each round will "bubble" larger elements to the right and the array becomes more and more sorted.

When one sorting round has finished without any swaps it means that the array is sorted, and the bubble sort algorithm has finished its task.

Computational complexity

The algorithms average and worst-case performance is O(n²), which is quite bad compared to other algorithms. So if you want to use bubble sort then you should generally only use it to sort a small number of items.

One situtation when bubble sort actually has good performance is when the array contains elements that are almost sorted. Consider for example the following array: [1, 2, 4, 3]. In this case, where only one number is out of place by only one position, the algorithm would order the elements by one sorting round. In the second round of the algorithm no swaps would be performed, which means that the array is now sorted. In that case the algorithm runs in only 2n time.

Example of an implementation of bubble sort in C#

   private void SortArrayWithBubbleSort()
   {
       int[] array = { 7, 5, 3, 6, 6, 2 };
       int[] sortedArray = BubbleSort(array);

       // PrintResult(sortedArray);         
   }

   private int[] BubbleSort(int[] array)
   {
       for (int i = 0; i < array.Length - 1; i++)
       {
           bool swapped = false;

           for (int j = 0; j < array.Length - 1; j++)
           {
               if (array[j] > array[j + 1])
               {
                   SwapValues(array, j);
                   swapped = true;
               }
           }

           if (!swapped)
           {
               break;
           }
       }

       return array;
   }

   private static void SwapValues(int[] arr, int i)
   {
       int temp = arr[i + 1];
       arr[i + 1] = arr[i];
       arr[i] = temp;
   }

A possible optimization of bubble sort

After the first loop in the algorithm the last position in the array will always contain the largest element in the array. After the second loop the second last position will contain the second largest element and so on.

This behaviour could be described as "the n-th pass finds the n-th largest element and puts it into its final place" (from Wikipedia).

This means that the inner loop can avoid looking at the last n-1 items when running for the n-th time, since those items are already correctly sorted and placed at their final destination in the array.

In the following code example this optimization has been inmplemented by introducing the variable k, that increases by 1 for each loop. After each loop, the number of iterations now exclude the last item processed in the previous iteration.

Bubble sort with slightly better performance in C# code

    private int[] BubbleSort(int[] array)
    {
        for (int i = 0; i < array.Length - 1; i++)
        {
            bool swapped = false;
            int k = 0;

            for (int j = 0; j < array.Length - 1 - k; j++)
            {
                if (array[j] > array[j + 1])
                {
                    SwapValues(array, j);
                    swapped = true;
                }
            }

            k++;

            if (!swapped)
            {
                break;
            }
        }

        return array;
    }