C++

Bucket sort C++

This is the type of sorting that divides data into more buckets to ease the process of sorting as a whole. The bucket sorting is also known as a scatter-gather approach. Let us start with a simple algorithm to demonstrate the working of bucket sort.

Algorithm / pseudocode

  • The first step is the function declaration.
  • Buckets for the array are created to store the values.
  • Each bucket at the start is initialized as NULL.
  • Assign values to each bucket.
  • The sorting process occurs in each bucket separately.
  • Combine data in each bucket in an array.

Implementation of bucket sort

For the implementation of the bucket sort, we need to provide two basic libraries; without them, we cannot easily apply any input, output, and functions of the array. Both header files are as follows:

#include <iomanip>

#include <iostream>

To move forward, first, we will define the size and capacity of arrays and buckets globally. The purpose of this global declaration is that any function will access these variables at any point in the source code. The array size is declared as 7, the buckets are 6 in number, whereas the interval or capacity for each bucket to store the same type of items is 10.

After that, a structure is created to initialize the nodes to contain data, and the next part will contain the address of the next node, when added, just like the linked list. This phenomenon is to be created because, in the end, all the buckets will be aligned.

# struct Node *next.

After that, all the functions are named here, which will be declared later in the source code. The first function, the sorting function of the bucket, is defined. The parameter of the function will contain the array passed from the main function that is to be sorted. Inside the function, we will create buckets. These buckets are just like arrays. But here, more than one bucket will be created. Each bucket is assigned with a range of numbers so that each bucket contains only specific data.

Create Node **buckets;

For the creation of buckets, we need to provide a specified size for the memory allocation.

Buckets = (struct Node **) malloc(sizeof(struct Node *) * NBUCKET);

Each bucket will be assigned a specific memory space. After the bucket creation, each bucket will be initialized with NULL at first; later on, values will be inserted. This process will be done by using a FOR loop.

The next step is to enter the data from the input array in each respective bucket.

A for loop will start and iterate towards each bucket to enter data in it. A pointer variable of node, ‘current’, will be created here to store the location/ address of the current node. An integer type variable will store the index of the array so that the data is to be entered in the specified index of the array. The data part of the current node will be given data from the input array, whereas the next part of the current node will contain the position of the bucket in which recent data has been entered. Now the next bucket is given the position of the current node. Each assignment is done inside the loop in each iteration.

Current -> data = arr[i];

Current - > next = buckets[pos];

Buckets [pos] = current;

After the data has been entered, now we will display the data in each bucket with the bucket number. A function for the print purpose is created separately. Inside the ‘for’ loop, the bucket number will be printed, as shown in the below-cited image, along with the data fetched through the index number.

printBuckets(bucket[i]);

The numbers present in each bucket will be sorted separately. This is done by another function named ‘insertion sort’. This function call will contain each data in the specified index of the bucket. When the data is sorted, it is returned in the loop to the variable. And through this variable, all the sorted elements will be displayed. When all the buckets contain the sorted data, the whole buckets will be emptied into an array. Using a loop, each data will be entered into a new index of the array in the ascending order as they have been sorted earlier.

A pointer type node variable is required, and this will be assigned the data of the specified bucket. A while loop will continue till each data is transferred to the array from the buckets.

Arr[j++] = node -> data;

Node = node - >next;

A temporary variable tmp is created to store the value for the swapping process. The node’s data is stored in the temp. And the next node’s data is added to the previous one. In the end, temp is freed. All buckets are freed outside the while loop and for the loop body.

Now here, we have used an insertion sort function. This is the main part of the source code, where all the elements in buckets will be sorted. At the start, a check using an if statement is applied that shows that if the list is empty or the next part of the list is empty, then return the list; otherwise, the sorting process needs to be started.

Two new pointer-type variables are created that will help us in the sorting process. The novelist variable will contain the list, and the address part will be stored in the k pointer. A while loop is added here to last when the k pointer is not zero. With the help of a pointer, the comparison will be done by using an if statement. If the data of one index is greater than the next one, then the data will be temporarily stored in the temp variable, and the process of swapping occurs to make the elements in ascending order.

A similar case continues with the new pointer ptr’s next part; by comparison, the data in the buckets get sorted likewise. The sorted node is returned to the function where this function call was made.

A for loop helps to display each element inside the buckets to print the buckets. With the help of a set width function, the data at each index will be displayed.

Finally, in the main program, the first step is to create an array and add numbers to it. We will display both the unsorted array, and then the function call for the bucket sort is made. After that, the sorted array will be displayed.

Compile the code, and then you will see that first, the compiler will go to the main program, an unsorted array will be displayed, and then all buckets with unsorted and the next with the sorted data are displayed.

Conclusion

The article ‘Bucket sort C++’ is a sorting process in C++ language that actual relies on the insertion sort, but the only difference is that first, the data is transferred to the number of buckets of the specified range. Then sorting on an individual basis at each bucket takes place. And at the end, an array of sorted elements is returned after gathering all buckets. An example with the detailed procedure is explained.

About the author

Aqsa Yasin

I am a self-motivated information technology professional with a passion for writing. I am a technical writer and love to write for all Linux flavors and Windows.