Sorting is one of the most common programming problems that we have to solve. The good news is, that there are many sorting algorithms available to address such problems. However, each algorithm has its strengths and weaknesses, which may influence the choice of algorithm to use in different scenarios.<\/p>\n
In this article, we’re going to learn about bucket sort, see how it works, implement it in C# and analyze its time and space complexity.<\/p>\n
Let’s start.\u00a0<\/p>\n
Bucket\/bin sort is a sorting algorithm that works by partitioning an array into several buckets.<\/strong> The bucket sort algorithm then sorts the contents of each bucket recursively or by applying different sorting algorithms.\u00a0<\/p>\n Bucket sort uses this principle to sort a list of elements:<\/p>\n Let’s take a deep dive and learn how bucket sort works.\u00a0<\/p>\n To illustrate how the bucket sort algorithm works, let’s assume we intend to sort this array:<\/p>\n We need to divide these elements into buckets using an identifier. To make our example simple, let’s create buckets based on a range of ten values for each bucket:\u00a00 – 9,\u00a010 – 19,\u00a020 – 29, 30 – 39, and 40 – 49.<\/p>\n Next, we are going to “scatter” the elements into those buckets based on their range:\u00a0<\/p>\n Now, we sort the items in each bucket using a different algorithm such as bubble sort<\/a> (to keep our illustration simple):<\/p>\n Finally, we gather the items from each bucket in the correct order, which completes the sorting process:\u00a0<\/p>\n Let’s learn how to implement the bucket sort algorithm in C#.<\/p>\n We can implement the bucket sort algorithm in different ways. We are going to implement the algorithm in C# as we have discussed so far and try to improve its shortcomings by implementing an optimized solution.<\/p>\n First, we are going to write a function Next, we are going to define a method called Let’s understand how this method works.<\/p>\n First, we check whether Next, we are going to find the maximum and minimum elements in the array:<\/p>\n Here, we loop through the Now that we have the buckets ready, we are going to scatter the array values into the buckets we’ve created:<\/p>\n After initializing the buckets, we are going to invoke the Finally, we can verify that the The bucket sort algorithm has a few weaknesses, which were are going to discuss soon. We can improve the algorithm by initializing the buckets only when we need them, which saves us some time initializing them. Using the Let’s learn how to optimize our current implementation:\u00a0<\/p>\n The goal of this process is to store each array element in its corresponding index and move everything to the left as possible ( We can see that a new Next, we start the process of moving the elements from the bucket back into We achieve this by setting the index of the array to zero and iterating through the bucket as we add the sorted elements back into We start iterating from the head of the Next, we can verify that the As we’ve seen in the implementation<\/a> section, the bucket sort algorithm requires the creation of buckets to hold the array elements during the sorting process. Therefore, the space complexity of bucket sort is O(n + k)<\/strong>, with n being the number of elements in the array and k being the number of buckets.\u00a0<\/p>\n Bucket sort encounters the best-case time complexity scenario when we scatter elements uniformly across the buckets. The time it would take to sort the array is O(n + k) <\/strong>with n being the number of elements in the array and k being the number of buckets.<\/p>\n When bucket sort encounters random array elements it encounters an average-case time complexity scenario. It would take O(n + k) <\/strong>time to sort the array with n being the number of elements in the array and k being the number of buckets.<\/p>\n This scenario occurs when bucket sort encounters a reversed list.<\/strong> Depending on the “inner algorithm” used such as the bubble sort algorithm<\/a>, the algorithm may need to carry out N2<\/sup><\/strong> comparisons. Therefore, the bucket sort algorithm has a worst-case complexity of\u00a0 O(N2<\/sup>).<\/strong><\/p>\n Bucket sort reduces the number of comparisons we make when sorting elements as we distribute them into different buckets and sort each bucket separately.\u00a0<\/p>\n The algorithm can be fast when we scatter elements uniformly across all the buckets.\u00a0<\/strong><\/p>\n It does not sort elements in place like other algorithms such as merge sort<\/a>, as it needs O(n + k)\u00a0<\/strong>space.\u00a0<\/p>\n The algorithm has a worst-case complexity<\/a> of O(N2<\/sup>)<\/strong>.<\/p>\n Bucket sort may or may not be stable<\/strong>. A stable sorting algorithm maintains the relative order of the array elements in case it encounters two similar values, unlike quicksort<\/a>, which is unstable.<\/p>\n Let’s assess how bucket sort performs by measuring the time it takes for it to sort an array.\u00a0<\/p>\n First, let’s write a method to generate a set of random array elements:<\/p>\n The Next, we are going to define a method that generates a sequence of elements. This method simulates a scenario where we have a sorted array:<\/p>\n Next, we are going to create an object that holds different arrays that have random and sorted values:<\/p>\n Each object entry has three values: an integer array e.g. The array objects have different sizes (to simulate time complexity scenarios) and hold random numbers<\/a> that are added by the Let’s assess the sample best, average, and worst-case complexity performance results of the algorithm:<\/p>\n The <\/strong> In this article, we have learned how bucket sort works in C#. We can use it in scenarios where we have control over the range of values that we intend to sort. However, other algorithms such as merge sort<\/a> and quick sort<\/a> perform much better than bucket sort.\u00a0\u00a0<\/p>\n","protected":false},"excerpt":{"rendered":" Sorting is one of the most common programming problems that we have to solve. The good news is, that there are many sorting algorithms available to address such problems. However, each algorithm has its strengths and weaknesses, which may influence the choice of algorithm to use in different scenarios. In this article, we’re going to […]<\/p>\n","protected":false},"author":6,"featured_media":62189,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_et_pb_use_builder":"","_et_pb_old_content":"","_et_gb_content_width":"","footnotes":""},"categories":[1010,12],"tags":[1140,1275,592,1141],"class_list":["post-69957","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithm","category-csharp","tag-algorithm","tag-bucket-sort","tag-sorting","tag-sorting-algorithm","et-has-post-format-content","et_post_format-et-post-format-standard"],"yoast_head":"\n\n
<\/a>How Does Bucket Sort Algorithm Work?<\/h2>\n
int[] array = {42, 6, 16, 4, 12, 24, 46, 17};<\/code><\/p>\n\n
\n
4, 6, 12, 16, 17, 24, 42, 56<\/code><\/p>\n<\/a>How to Implement Bucket Sort in C#?<\/h2>\n
<\/a>Non-Optimized Bucket Sort Implementation in C#<\/h3>\n
int[] BubbleSort<\/code> that takes a List<int><\/code> object and sorts its values using the bubble sort algorithm<\/a>:<\/p>\npublic static int[] BubbleSort(List<int> listInput)\r\n{\r\n for (int i = 0; i < listInput.Count; i++)\r\n {\r\n for (int j = 0; j < listInput.Count; j++)\r\n {\r\n if (listInput[i] < listInput[j])\r\n {\r\n var temp = listInput[i];\r\n listInput[i] = listInput[j];\r\n listInput[j] = temp;\r\n }\r\n }\r\n }\r\n \r\n return listInput.ToArray();\r\n}<\/pre>\nSortArray()<\/code> as our entry point into the sorting algorithm. The method takes int[] array<\/code> as its sole input and returns a sorted array:<\/p>\npublic int[] SortArray(int[] array)\r\n{\r\n List<int> sortedList = new List<int>();\r\n var minValue = array[0];\r\n var maxValue = array[0];\r\n\r\n if (array == null || array.Length <= 1)\r\n {\r\n return array;\r\n }\r\n\r\n for (int i = 1; i < array.Length; i++)\r\n {\r\n if (array[i] > maxValue)\r\n maxValue = array[i];\r\n if (array[i] < minValue)\r\n minValue = array[i];\r\n }\r\n \r\n var numberOfBuckets = maxValue - minValue + 1;\r\n List<int>[] bucket = new List<int>[numberOfBuckets];\r\n\r\n for (int i = 0; i < numberOfBuckets; i++) \r\n {\r\n bucket[i] = new List<int>();\r\n }\r\n \r\n for (int i = 0; i < array.Length; i++)\r\n {\r\n var selectedBucket = (array[i] \/ numberOfBuckets);\r\n bucket[selectedBucket].Add(array[i]);\r\n }\r\n\r\n for (int i = 0; i < numberOfBuckets; i++)\r\n {\r\n int[] temp = BubbleSort(bucket[i]);\r\n sortedList.AddRange(temp);\r\n }\r\n\r\n return sortedList.ToArray();\r\n}<\/pre>\nint[] array<\/code> is null or has a single element as our base case and skips the sorting process:\u00a0<\/p>\nif (array == null || array.Length <= 1)\r\n{\r\n return array;\r\n}<\/pre>\nfor (int i = 1; i < array.Length; i++)\r\n{\r\n if (array[i] > maxValue)\r\n {\r\n maxValue = array[i];\r\n }\r\n\r\n if (array[i] < minValue)\r\n {\r\n minValue = array[i];\r\n }\r\n}<\/pre>\narray<\/code> as we find the maxValue<\/code> and minValue<\/code>, which are going to come in handy when we create the buckets, which in this case, are List<int><\/code> objects:<\/p>\nvar numberOfBuckets = maxValue - minValue + 1;\r\nList<int>[] bucket = new List<int>[numberOfBuckets];\r\n\r\nfor (int i = 0; i < numberOfBuckets; i++) \r\n{\r\n bucket[i] = new List<int>();\r\n}<\/pre>\nfor (int i = 0; i < array.Length; i++)\r\n{\r\n var selectedBucket = (array[i] \/ numberOfBuckets);\r\n bucket[selectedBucket].Add(array[i]);\r\n}\r\n<\/pre>\nBubbleSort()<\/code> method we created earlier and pass each bucket. The method returns a sorted array, which we add at the end of the sorted list:\u00a0<\/p>\nfor (int i = 0; i < numberOfBuckets; i++)\r\n{\r\n int[] temp = BubbleSort(bucket[i]);\r\n sortedList.AddRange(temp);\r\n}\r\n\r\nreturn sortedList.ToArray();<\/pre>\nSortArray()<\/code> method sorts a given unsorted array accurately:<\/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 InsertionSortMethods();\r\n\r\nvar sortedArray = sortFunction.SortArray(array, array.Length);\r\n\r\nAssert.IsNotNull(sortedArray);\r\nCollectionAssert.AreEqual(sortedArray, expected);<\/pre>\n<\/a>Optimized Bucket Sort Implementation in C#<\/h3>\n
LinkedList<T><\/code> objects instead of List<T><\/code> would come in handy when accessing sequential data, which can give us a slight performance edge.\u00a0<\/p>\npublic int[] SortArrayOptimized(int[] array)\r\n{\r\n if (array == null || array.Length <= 1)\r\n {\r\n return array;\r\n }\r\n\r\n int maxValue = array[0]; \r\n int minValue = array[0];\r\n\r\n for (int i = 1; i < array.Length; i++)\r\n {\r\n if (array[i] > maxValue)\r\n {\r\n maxValue = array[i];\r\n }\r\n\r\n if (array[i] < minValue)\r\n {\r\n minValue = array[i];\r\n }\r\n }\r\n\r\n LinkedList<int>[] bucket = new LinkedList<int>[maxValue - minValue + 1];\r\n\r\n for (int i = 0; i < array.Length; i++)\r\n {\r\n if (bucket[array[i] - minValue] == null)\r\n {\r\n bucket[array[i] - minValue] = new LinkedList<int>();\r\n }\r\n\r\n bucket[array[i] - minValue].AddLast(array[i]);\r\n }\r\n\r\n var index = 0;\r\n \r\n for (int i = 0; i < bucket.Length; i++)\r\n {\r\n if (bucket[i] != null)\r\n {\r\n LinkedListNode<int> node = bucket[i].First;\r\n\r\n while (node != null)\r\n {\r\n array[index] = node.Value;\r\n node = node.Next; \r\n index++;\r\n }\r\n }\r\n }\r\n \r\n return array;\r\n}<\/pre>\nSortArrayOptimized()<\/code> is similar to SortArray()<\/code> but has a few notable differences such as the use of\u00a0LinkedList<int><\/code> objects instead of List<int><\/code> objects:<\/p>\nLinkedList<int>[] bucket = new LinkedList<int>[maxValue - minValue + 1];<\/code><\/p>\nminValue<\/code>) during the sorting process:<\/p>\nfor (int i = 0; i < array.Length; i++)\r\n{\r\n if (bucket[array[i] - minValue] == null)\r\n {\r\n bucket[array[i] - minValue] = new LinkedList<int>();\r\n }\r\n\r\n bucket[array[i] - minValue].AddLast(array[i]);\r\n}<\/pre>\nLinkedList<int><\/code> object is created when the loop encounters minValue<\/code> in the array and adds the rest of the array elements in order at the end of the bucket when calling bucket[array[i] - minValue].AddLast(array[i])<\/code>.<\/p>\nint[] array<\/code>.<\/p>\nint[] array<\/code>:<\/p>\nvar index = 0;\r\n \r\nfor (int i = 0; i < bucket.Length; i++)\r\n{\r\n if (bucket[i] != null)\r\n {\r\n LinkedListNode<int> node = bucket[i].First;\r\n\r\n while (node != null)\r\n {\r\n array[index] = node.Value; \r\n node = node.Next; \r\n index++;\r\n }\r\n }\r\n}\r\n \r\nreturn array;<\/pre>\nLinkedList<int><\/code> as we move to the next nodes as we add the values to the int[] array<\/code> object.\u00a0The loop terminates when the next node is null and returns the sorted array.\u00a0<\/p>\nSortArray()<\/code>\u00a0 and SortArrayOptimized()<\/code> methods return the same result when sorting an array:<\/p>\npublic void GivenUnsortedArray_WhenArrayIsNotEmpty_ThenReturnSortedArray()\r\n{\r\n var array = new int[] { 73, 57, 49, 99, 133, 20, 1 };\r\n var expected = new int[] { 1, 20, 49, 57, 73, 99, 133 };\r\n var sortFunction = new BucketSortMethods();\r\n\r\n var sortOptimized = sortFunction.SortArrayOptimized(array, string.Empty);\r\n var sortNormal = sortFunction.SortArray(array, string.Empty);\r\n\r\n \u00a0 CollectionAssert.AreEqual(sortNormal, expected);\r\n CollectionAssert.AreEqual(sortOptimized, expected); \r\n}<\/pre>\n<\/a>Space and Time Complexity of Bucket Sort Algorithm<\/h2>\n
<\/a>Best-Case Time Complexity<\/h3>\n
<\/a>Average-Case Time Complexity<\/h3>\n
<\/a>Worst-Case Time Complexity<\/h3>\n
<\/a>Advantages of Bucket Sort Algorithm<\/h2>\n
<\/a>Disadvantages of Bucket Sort Algorithm<\/h2>\n
<\/a>Performance Tests<\/h2>\n
public static int[] CreateRandomArray(int size)\r\n{\r\n var array = new int[size];\r\n var rand = new Random();\r\n\r\n for (int i = 0; i < size; i++)\r\n array[i] = rand.Next(1, size);\r\n\r\n return array;\r\n}<\/pre>\nCreateRandomArray()<\/code> the method takes an integer as its sole input. Using the inbuilt Random<\/code> class, we generate integer values that we’re going to put into the array.<\/p>\npublic static int[] CreateSortedArray(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>\npublic IEnumerable<object[]> SampleArrays()\r\n{\r\n yield return new object[] { CreateRandomArray(200), \"Small Unsorted\" };\r\n yield return new object[] { CreateRandomArray(2000), \"Medium Unsorted\" };\r\n yield return new object[] { CreateRandomArray(20000), \"Large Unsorted\" };\r\n yield return new object[] { CreateSortedArray(200), \"Small Sorted\" };\r\n yield return new object[] { CreateSortedArray(2000), \"Medium Sorted\" };\r\n yield return new object[] { CreateSortedArray(20000), \"Large Sorted\" };\r\n}<\/pre>\nCreateRandomArray(200)<\/code>, its length (200), and a string object storing the name of that array (“Small Unsorted”).\u00a0<\/p>\nCreateRandomArray()<\/code> method. On the other hand, the CreateSortedArray()<\/code> method creates arrays that have values that are sorted.\u00a0<\/p>\n| Method | array | arrayName | Mean | Error | StdDev |\r\n|------------------- |------------- |---------------- |-----------------:|---------------:|----------------:|\r\n| SortArray | Int32[20000] | Large Sorted | 942,629.686 \u03bcs | 17,950.5497 \u03bcs | 21,368.8525 \u03bcs |\r\n| SortArrayOptimized | Int32[20000] | Large Sorted | 5,730.690 \u03bcs | 176.0321 \u03bcs | 519.0345 \u03bcs |\r\n| SortArray | Int32[20000] | Large Unsorted | 1,538,116.280 \u03bcs | 37,973.6267 \u03bcs | 111,966.0951 \u03bcs |\r\n| SortArrayOptimized | Int32[20000] | Large Unsorted | 5,631.236 \u03bcs | 111.7425 \u03bcs | 220.5689 \u03bcs |\r\n| SortArray | Int32[2000] | Medium Sorted | 12,017.725 \u03bcs | 170.9306 \u03bcs | 159.8886 \u03bcs |\r\n| SortArrayOptimized | Int32[2000] | Medium Sorted | 174.385 \u03bcs | 3.0591 \u03bcs | 3.5229 \u03bcs |\r\n| SortArray | Int32[2000] | Medium Unsorted | 11,875.260 \u03bcs | 215.5740 \u03bcs | 435.4702 \u03bcs |\r\n| SortArrayOptimized | Int32[2000] | Medium Unsorted | 168.497 \u03bcs | 5.7366 \u03bcs | 16.6430 \u03bcs |\r\n| SortArray | Int32[200] | Small Sorted | 106.994 \u03bcs | 2.0930 \u03bcs | 4.2281 \u03bcs |\r\n| SortArrayOptimized | Int32[200] | Small Sorted | 8.926 \u03bcs | 0.1784 \u03bcs | 0.2615 \u03bcs |\r\n| SortArray | Int32[200] | Small Unsorted | 153.492 \u03bcs | 5.2994 \u03bcs | 15.6255 \u03bcs |\r\n| SortArrayOptimized | Int32[200] | Small Unsorted | 10.968 \u03bcs | 0.3958 \u03bcs | 1.1670 \u03bcs |<\/pre>\n
SortArrayOptimized()<\/code> method performs at least ten times better than the <\/strong>SortArray()<\/code> method when sorting arrays of different sizes<\/strong>\u00a0because the latter uses an inefficient “inner algorithm.” The bubble sort algorithm we implement has to perform N2 <\/sup><\/strong>comparisons regardless of the arrays’ sizes, which explains why the non-optimized implementation is always slower than the optimized one.\u00a0<\/p>\n<\/a>Conclusion<\/h2>\n