# Bubble Sort – Data Structures and Algorithms using C#

Bubble sort is conceptually the simplest sorting algorithm. It goes through an entire elements and compares each adjacent elements. It then swaps the elements if they are not in order. The process is repeated until no more swapping is needed.

The bubble sort algorithm is as follows:

1. Compare arr[0] and arr[1], If arr[0] is bigger than arr[1], swap the elements.
2. Move to the next element, arr[1], and compare it with arr[2]. If arr[1] is bigger than arr[2], swap the elements.
3. Continue step 1 and 2 n times.
##### Why is it called bubble sort?

The algorithm is called Bubble Sort, because with each iteration the smallest element in the list bubbles up to the top, just like a water bubble rises up to the water surface.

##### C# Implementation

Assume that Arr[] is an unsorted array of n elements. This array needs to be sorted in ascending order.

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 34 35 36 37 38 39 40 41 42 43 using System;   public class Program { public static void Main() { int[] arr = { 5, 12, 4, 32, 67, 23, 9, 14, 99, 21};   // call the function bubbleSort BuubleSort(arr);   // print the sorted array Console.WriteLine("Sorted Array: "); for (int i = 0; i < arr.Length; i++) { Console.Write(arr[i] + " "); } } public static void BuubleSort(int[] arr) { var changeCount = 0;   do { changeCount = 0; for (var i = 0; i < arr.Length - 1; i++) // Loop through all numbers { // Store the values of the 2 cards var left = arr[i]; var right = arr[i+1];   if (left > right) // The Comparison to the next number { //Swap them arr[i] = right; arr[i+1] = left; changeCount++; } } } while (changeCount > 0); // If any number swapped the last time, iterate again to sort again. } }

Try Out

##### Complexity of Algorithm

Worst and Average Case Time Complexity:
As you can see above sorting with 10 numbers, It makes 9 comparison on 1st pass, 8 comparison on the 2nd pass, and so on.
In general, when we have an array of size n, there are n-1 comparisons on the first pass, n-2 on the second, and so on. So the total number of comparisons will be
(n-1) + (n-2) + (n-3) + ….. + 3 + 2 + 1
Sum = n(n-1)/2
i.e O(n^2)

Hence, we can say that the bubble sort runs in O(n^2) time.

Best Case Time Complexity: O(n). Best case occurs when array is already sorted.

The space complexity for Bubble Sort is O(1), because only a single additional memory space is required i.e. for temporary variables.

##### In Practice

Although bubble sort is one of the simplest sorting algorithms to understand and implement, its O(n^2) complexity means that its efficiency decreases dramatically on lists of more than a small number of elements. Even among simple O(n^2) sorting algorithms, algorithms like insertion sort are usually considerably more efficient.

Bubble sort is asymptotically equivalent in running time to insertion sort in the worst case, but the two algorithms differ greatly in the number of swaps necessary. Experimental results have shown that insertion sort performs considerably better even on random lists.

Bubble sort also interacts poorly with modern CPU hardware. It produces at least twice as many writes as insertion sort, twice as many cache misses, and asymptotically more branch mispredictions.