Sorting arrays is quite a common problem in programming. The bubble sort algorithm is simple to implement as it involves comparing adjacent elements and swapping them when they are in the wrong order. We are going to learn how Bubble Sort in C# works.\u00a0<\/p>\n
Let’s dive in.\u00a0<\/p>\n
So, how does bubble sort in C# work?<\/p>\n
Let’s say we want to sort an array that has seven elements:<\/p>\n
Using the bubble sort algorithm, let’s start by comparing 73 and 57. 57 is less than 73, so we swap their positions and the array becomes:<\/p>\n 49 is less than 73, which triggers the algorithm to swap their positions:<\/p>\n 73 is less than 99 while 99 is less than 133, so the algorithm skips these positions. Next, we compare 133 with 20 and swap their positions as 20 is less than 133:<\/p>\n Since 1 is less than 33, the algorithm swaps their positions:<\/p>\n The bubble sort algorithm repeats this process until all the elements are in the correct order with the final result being:<\/p>\n We are going to define an integer array property Let’s create a method that implements the bubble sort algorithm in C# that sorts the values in the The variable The outer loop iterates through the array while the inner loop compares adjacent elements. Since 57 is less than 73, they swap their positions and the inner loop continues comparing adjacent values until it gets to the last element of that array. For each iteration of the outer loop, the inner loop iterates while performing comparisons.<\/p>\n Let’s check if our loop performed correctly:<\/p>\n The space complexity of the bubble sort algorithm is O(1) because it requires a single additional space that holds the temporary value we are using to swap the elements.\u00a0<\/p>\n Nested loops have detrimental effects on how algorithms perform as the size of the array grows. The bubble sort algorithm has a time complexity of O(N\u00b2) as it has two nested loops. Let’s analyze how the algorithm performs in different levels of complexity.<\/p>\n Best Case Complexity: <\/strong>this case occurs when we want to sort an array that is already in required order. The algorithm traverses the array without swapping values, which means, its complexity is O(N).\u00a0<\/p>\n Average Case Complexity: <\/strong>this case occurs when an array has some elements that are in the correct order. The bubble sort algorithm performs comparisons while swapping some values, which means, it has a complexity of O(N\u00b2).\u00a0<\/p>\n Worst Case Complexity: <\/strong>this scenario occurs when assuming we have a list of numbers that are in descending order and we need to sort them in ascending order, the algorithm would encounter a worst-case complexity as the length of that array grows to N. Therefore, the algorithm compares all elements while swapping them, which means, it has a complexity of O(N\u00b2).\u00a0<\/p>\n The bubble sort algorithm is easy to learn and implement. On top of that, it has little memory overhead as the sorting is done in place, which is similar to selection sort<\/a>. This attribute comes in handy in memory-intensive applications. This algorithm performs well in cases where an array is almost in order as it is an example of the <\/strong>best case complexity<\/a> scenario<\/strong>.\u00a0<\/p>\n On the other hand, the bubble sort algorithm has high levels of time complexity O(N\u00b2), which is inefficient when compared to other algorithms<\/strong> such as merge sort.\u00a0<\/p>\n We can see that the bubble sort algorithm still iterates even in cases where an array is already in order. We can optimize the swapping process by checking whether we need to swap elements or not. Let’s optimize our previous implementation and see what’s different about it:<\/p>\n We introduce a boolean value Let’s check if our optimal bubble sort algorithm performs correctly:<\/p>\n Let’s verify the bubble sort algorithm has a time complexity of O(N\u00b2) by measuring the time it takes for the algorithm to sort an array.<\/p>\n First, let’s write a method to generate a set of random numbers that are going to be added into the array:<\/p>\n The To simulate a scenario where we have a sorted array, we are going to define a method that generates a sequence of elements:<\/p>\n Next, we are going to implement a performance benchmark to assess how the normal bubble sort algorithm performs versus the optimized bubble sort algorithm when sorting randomly generated numbers:\u00a0<\/p>\n The array objects have different sizes (to simulate time complexity scenarios) and hold random numbers<\/a> that are added by the The worst-case execution demonstrates this concept as the Next, are going to re-run the same benchmark but with the arrays holding values that have already been sorted invoking the And let’s assess the results of this benchmark:<\/p>\n The optimized bubble sort algorithm implementation is faster than the normal version of the bubble sort algorithm in all case scenarios. We can also see that the time complexity of this algorithm worsens exponentially as the number of elements increases.<\/p>\n We can also see that the algorithm takes less time for an array that is already in order from the second benchmark which means that the complexity is lower. This would be even more emphasized with the larger arrays.<\/p>\nint[] array = { 73, 57, 49, 99, 133, 20, 1 };<\/code><\/p>\n57<\/span>, 73<\/span>, 49, 99, 133, 20, 1<\/code><\/p>\n57, 49<\/span>, 73<\/span>, 99, 133, 20, 1<\/code><\/p>\n57, 49, 73, 99, 20<\/span>, 133<\/span>, 1<\/code><\/p>\n57, 49, 73, 99, 20, 1<\/span>, 133<\/span><\/code><\/p>\n1, 20, 49, 57, 73, 99, 133\u00a0<\/code><\/p>\n<\/a>How to Implement Bubble Sort in C#?<\/h2>\n
NumArray<\/code>, that we are going to use to implement the bubble sort algorithm:<\/p>\npublic int[]? NumArray { get; set; }<\/code><\/p>\nNumArray<\/code> property:<\/p>\npublic int[] SortArray() \r\n{\r\n var n = NumArray.Length;\r\n\r\n for (int i = 0; i < n - 1; i++)\r\n for (int j = 0; j < n - i - 1; j++)\r\n if (NumArray[j] > NumArray[j + 1])\r\n {\r\n var tempVar = NumArray[j];\r\n NumArray[j] = NumArray[j + 1];\r\n NumArray[j + 1] = tempVar;\r\n }\r\n\r\n return NumArray;\r\n}<\/pre>\nn<\/code> holds the size of the array while the tempVar<\/code> variable holds values temporarily during the swap process. Let’s use our array example to understand how the code works:<\/p>\nvar array = new int[] { 73, 57, 49, 99, 133, 20, 1 };\r\nvar expected = new int[] { 1, 20, 49, 57, 73, 99, 133 };\r\nvar sortFunction = new Bubble();\r\nsortFunction.NumArray = array;\r\n\r\nvar sortedArray = sortFunction.SortArray();\r\n\r\nAssert.IsNotNull(sortedArray);\r\nCollectionAssert.AreEqual(sortedArray, expected);<\/pre>\n<\/a>Time and Space Complexity<\/h2>\n
<\/a>Advantages and Disadvantages<\/h2>\n
<\/a>How to Optimize the Bubble Sort Algorithm in C#?<\/h2>\n
public int[] SortOptimizedArray()\r\n{\r\n var n = NumArray.Length;\r\n bool swapRequired;\r\n\r\n for (int i = 0; i < n - 1; i++) \r\n {\r\n swapRequired = false;\r\n\r\n for (int j = 0; j < n - i - 1; j++)\r\n if (NumArray[j] > NumArray[j + 1])\r\n {\r\n var tempVar = NumArray[j];\r\n NumArray[j] = NumArray[j + 1];\r\n NumArray[j + 1] = tempVar;\r\n swapRequired = true;\r\n }\r\n if (swapRequired == false)\r\n break;\r\n }\r\n\r\n return NumArray;\r\n}<\/pre>\nswapRequired<\/code> to track whether we need to swap the elements or not. The swapRequired<\/code> variable becomes true when we swap elements, otherwise, it’s set to false. In iterations where swapping is not required, the swapRequired<\/code> will be false, which means, the array elements are in order and we break the loop before it finishes to the end.\u00a0 This way we save a lot of time.<\/p>\nvar array = new int[] { 73, 57, 49, 99, 133, 20, 1 };\r\nvar expected = new int[] { 1, 20, 49, 57, 73, 99, 133 };\r\nvar sortFunction = new Bubble();\r\n\r\nsortFunction.NumArray = array;\r\nvar sortedArray = sortFunction.SortOptimizedArray();\r\n\r\nAssert.IsNotNull(sortedArray);\r\nCollectionAssert.AreEqual(sortedArray, expected);<\/pre>\n<\/a>Bubble Sort Performance<\/h2>\n
public static int[] GenerateRandomNumber(int size)\r\n{\r\n var array = new int[size];\r\n var rand = new Random();\r\n var maxNum = 10000;\r\n\r\n for (int i = 0; i < size; i++)\r\n array[i] = rand.Next(maxNum + 1);\r\n\r\n return array;\r\n}<\/pre>\nGenerateRandomNumber<\/code> method takes an integer as its sole input. Using the inbuilt Random<\/code> class, we generate integer values (less than 10000) that we’re going to put into the array.<\/p>\npublic static int[] GenerateSortedNumber(int size)\r\n{\r\n var array = new int[size];\r\n\r\n for (int i = 0; i < size; i++)\r\n array[i] = i;\r\n\r\n return array;\r\n}<\/pre>\nint[] smallArray = GenerateRandomNumber(200);\r\nint[] mediumArray = GenerateRandomNumber(2000);\r\nint[] largeArray = GenerateRandomNumber(200000);<\/pre>\n
GenerateRandomNumber<\/code> method. Let’s assess the sample best, average, and worst-case complexity performance results of the algorithm:<\/p>\n| Method | NumArray | Mean | Error | StdDev |\r\n|------------------- |-------------- |--------------------:|------------------:|--------------------:|\r\n| SortArray | Int32[200000] | 34,217,602,373.3 ns | 680,856,233.76 ns | 1,852,319,597.83 ns |\r\n| SortOptimizedArray | Int32[200000] | 404,684.5 ns | 22,163.41 ns | 64,300.07 ns | \r\n| SortArray | Int32[2000] | 3,188,246.8 ns | 32,947.14 ns | 30,818.77 ns |\r\n| SortOptimizedArray | Int32[2000] | 3,191.4 ns | 23.51 ns | 21.99 ns | \r\n| SortArray | Int32[200] | 32,333.2 ns | 512.23 ns | 766.68 ns |\r\n| SortOptimizedArray | Int32[200] | 323.9 ns | 6.34 ns | 6.51 ns |<\/pre>\n
SortArray<\/code> method takes approximately 34,217,602,373.3 ns (~34.21 seconds) to run while the SortOptimizedArray<\/code> method takes 404,684.5 ns (~0.000404 seconds) which is a huge difference.<\/p>\nGenerateSortedNumber<\/code> method. These are the array objects we are going to use for the next benchmark run:<\/p>\nint[] sortedSmallArray = GenerateSortedNumber(200);\r\nint[] sortedMediumArray = GenerateSortedNumber(2000);\r\nint[] sortedLargeArray = GenerateSortedNumber(200000);<\/pre>\n
| Method | NumArray | Mean | Error | StdDev |\r\n|------------------- |-------------- |--------------------:|------------------:|--------------------:|\r\n| SortArray | Int32[200000] | 33,916,006,053.2 ns | 654,826,121.87 ns | 1,277,188,059.76 ns |\r\n| SortOptimizedArray | Int32[200000] | 320,074.5 ns | 6,279.92 ns | 10,663.78 ns |\r\n| SortArray | Int32[2000] | 3,122,602.4 ns | 16,882.03 ns | 15,791.46 ns |\r\n| SortOptimizedArray | Int32[2000] | 3,112.0 ns | 18.00 ns | 15.95 ns |\r\n| SortArray | Int32[200] | 34,262.8 ns | 1,023.35 ns | 2,919.67 ns |\r\n| SortOptimizedArray | Int32[200] | 315.0 ns | 3.85 ns | 3.22 ns |<\/pre>\n
<\/a>Conclusion<\/h2>\n