Non Comparison based Sorting Algorithms

In this article, we have explored various non comparison sorting algorithms like Counting Sort, Radix Sort, Postman Sort and others along with their advantages / disadvantages.

Table of contents:

  1. What do you mean by a non-comparison sorting algorithm?
  2. Counting Sort algorithm
  3. Bucket Sort algorithm
  4. Radix Sort algorithm
  5. Postman Sort
  6. Pigeonhole Sort algorithm

What do you mean by a non-comparison sorting algorithm?

The sorting algorithms that sort the data without comparing the elements are called non-comparison sorting algorithms. The examples for non-comparison sorting algorithms are counting sort, bucket sort, radix sort, and others.

Counting Sort algorithm

The counting sort algorithm sorts the elements by counting the total no of times each unique element occurs in the array. An auxiliary array is used to store the count of the elements and perform some arithmetic operations on these count values to determine the positions of the elements.

Algorithm.

Step 1: Find the maximum value in the given array.
Step 2: Initialize an auxiliary array of size maximum value plus one.
Step 3: Store the count of each element in their respective index in the auxiliary array. For example, store the count of 5 at index 5 in the auxiliary array.
Step 4: Calculate the cumulative sum and store it in the auxiliary space.
Step 5: Temporary array is used to store the sorted elements.
Step 6: Traverse the given array from left to right.
Step 7: Store the current element at index b[current element] - 1 in the temporary array where b is the auxiliary array.
Step 8: Decrement b[current element] by 1.
Step 9: Return temporary array.

Time and Space complexity

  • The time complexity is O ( n + k) because the time taken to traverse the auxiliary array is O(k) and the time taken to traverse the given array is O(n).
  • The space complexity is also O ( n + k).

where n is the size of the array and k is the maximum value in the array.

Example

Let us assume that the given array is 4, 2, 2, 8, 3, 3, 1.
Array -> 4 2 2 8 3 3 1.

The maximum value in the given array is 8.

Initialize an auxiliary array of size 9 (8 + 1).
All the elements of this count array are 0.
Count -> 0 0 0 0 0 0 0 0 0.

0 is not present in the array.
So the value at index 0 in the count remains 0.

1 is present once in the array.
So the value at index 1 in the count is 1.

2 is present twice in the array.
So the value at index 2 in the count is 2.

3 is present twice in the array.
So the value at index 3 in the count is 2.

4 is present once in the array.
So the value at index 4 in the count is 1.

5 is not present in the array.
So the value at index 5 in the count is 0.

6 is not present in the array.
So the value at index 6 in the count is 0.

7 is not present in the array.
So the value at index 7 in the count is 0.

8 is present once in the array.
So the value at index 8 in the count is 1.

Count -> 0 1 2 2 1 0 0 0 1.

After cumulative sum the count looks like:
count -> 0 1 3 5 6 6 6 6 7

Traverse the array from left to right.
The current element is 4.
The current element is stored at index 5 ( Count[4] - 1).
decrement count[4] by 1.
count[4]=5.

The current element is 2
The current element is stored at index 2 (Count[2]- 1).
decrement Count[2] by 1.
count[2]=2.

The current element is 2
The current element is stored at index 1(Count[2]- 1).
decrement Count[2] by 1.
count[2]=1.

The current element is 8
The current element is stored at index 6 (Count[8]- 1).
decrement Count[8] by 1.
count[8]=6.

The current element is 3
The current element is stored at index 4 (Count[3]- 1).
decrement Count[3] by 1.
count[3]=4.

The current element is 3
The current element is stored at index 3 (Count[3]- 1).
decrement Count[3] by 1.
count[3]=3.

The current element is 1
The current element is stored at index 0 (Count[1]- 1).
decrement Count[1] by 1.
count[1]=0.

final output -> 1 2 2 3 3 4 8.

Implementing counting sort

  • C++

C++


#include <iostream>
using namespace std;

void countSort(int array[], int size) { int temp[size];//temporary array. int max = array[0];
// Find the largest element of the array for (int i = 1; i < size; i++) { if (array[i] > max) max = array[i]; }
int count[max+1];/*auxiliary array that stores count of each element*/
// Initialize count array with all zeros. for (int i = 0; i <= max; ++i) { count[i] = 0; }
// Store the count of each element for (int i = 0; i < size; i++) { count[array[i]]++; }
// Store the cummulative count of each array for (int i = 1; i <= max; i++) { count[i] += count[i - 1]; }
//Sort and store elements in temporary array for (int i = size - 1; i >= 0; i--) { temp[count[array[i]] - 1] = array[i]; count[array[i]]--; }
// Copy the sorted elements into original array for (int i = 0; i < size; i++) { array[i] = temp[i]; } }
// Function to print an array void print(int array[], int size) { for (int i = 0; i < size; i++) cout << array[i] << " "; cout << endl; }
int main() { int array[] = {4, 2, 2, 8, 3, 3, 1}; int n = sizeof(array) / sizeof(array[0]); countSort(array, n); print(array, n); }

Output

1 2 2 3 3 4 8 

Advantages of counting sort

  • It is faster than merge sort. The time complexity of merge sort is O(n*log(n)) whereas the time complexity of counting sort is O(n+k) where k is the maximum value in the array.
  • It is a stable sort.

Disadvantages of counting sort

  • It is not suitable for large data values.
  • It uses more space.
  • It is not suitable for sorting strings.

Bucket Sort algorithm

The bucket sort algorithm sorts the elements by grouping them into groups called buckets. The buckets are sorted using a suitable sorting algorithm and finally, the buckets are joined to obtain the sorted array.

Algorithm

Step 1: Create n empty buckets.
Step 2: Insert elements into their respective buckets using formula (size*arr[i]).
Step 3: Sort each of these buckets.
Step 4: Group them back to the array to obtain the sorted array.

Time and Space Complexity

  • The worst-case time complexity is O(n*n) because the worst-case scenario occurs when all the elements are placed in a single bucket and the time taken to sort this bucket is O(n*n).
  • The average-case time complexity is O(n) because when it is uniformly distributed on average each bucket will contain exactly one element and there is no need for sorting.
  • The best-case time complexity is O(n).
  • The space complexity is O(n+k)

where n is the size of the array and k is the number of buckets.

Example

Let us assume that the given array is 0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434.

Array -> 0.897 0.565 0.656 0.1234 0.665 0.3434.
The size of the array is 6.

Insert 0.897 in bucket int(6*0.897)
Insert 0.897 in bucket int(5.382)
Insert 0.897 in bucket 5.

Insert 0.565 in bucket int(6*0.565)
Insert 0.565 in bucket int(3.39)
Insert 0.565 in bucket 3.

Insert 0.656 in bucket int(6*0.656)
Insert 0.656 in bucket int(3.936)
Insert 0.656 in bucket 3.

Insert 0.1234 in bucket int(6*0.1234)
Insert 0.1234 in bucket int(0.7404)
Insert 0.1234 in bucket 0.

Insert 0.665 in bucket int(6*0.665)
Insert 0.665 in bucket int(3.99)
Insert 0.665 in bucket 3.

Insert 0.3434 in bucket int(6*0.3434)
Insert 0.3434 in bucket int(2.0604)
Insert 0.3434 in bucket 2.

The element present in bucket 0 is 0.1234
Since there is only one element no need for sorting.

There is no element present in bucket 1.

The element present in bucket 2 is 0.3434
Since there is only one element no need for sorting.

The elements present in bucket 3 are 0.665 0.656 0.565
After sorting the bucket looks like
0.565 0.656 0.665

There is no element present in bucket 4.

The element present in bucket 5 is 0.897
Since there is only one element no need for sorting.

After grouping these buckets the final output is
0.1234 0.3434 0.565 0.656 0.665 0.897.

Implementing Bucket Sort

  • C++

C++

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//Print the array. void print(float array[], int size) { for(int i = 0; i<size; i++) cout<<array[i]<<" "; cout << endl; }
//Function implementing bucket sort. void bucketSort(float array[], int size) { vector<float> bucket[size];// for(int i = 0; i<size; i++) {/*put elements into different buckets*/ bucket[int(size*array[i])].push_back(array[i]); }
for(int i = 0; i<size; i++) { sort(bucket[i].begin(), bucket[i].end());/*sort individual vectors*/ }
int index = 0;
//Group them together. for(int i = 0; i<size; i++) { while(!bucket[i].empty()) { array[index++] = *(bucket[i].begin()); bucket[i].erase(bucket[i].begin()); } } } int main() { float array[] = { 0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434 }; int n = sizeof(array) / sizeof(array[0]); bucketSort(array, n); print(array, n); }

Output

0.1234 0.3434 0.565 0.656 0.665 0.897

Advantages of bucket sort

  • It is a stable sort.
  • It is faster when data is distributed uniformly.

Disadvantages of bucket sort

  • It takes more space.
  • It is slower when data is not distributed uniformly.
  • You need a good bucketing scheme.

Radix Sort algorithm

The radix sort algorithm sorts the elements by comparing significant digits from least significant digit to most significant digit.

Algorithm

Step 1: Find the maximum value in the given array.
Step 2: Calculate no of digits present in the maximum value.
Step 3: Traverse each significant place starting from the least significant to the most significant place.
Step 4: Sort the elements based on the digit present at the current significant place using counting sort.
Step 5: Return the sorted array.

Time and Space complexity

  • The time complexity is O( d * (n+k)) because the outer loop runs for d times and the inner loop time complexity is O(n+k).
  • The space complexity is O(n+k).

where d is the no of digits present in maximum value, n is the size of the given array and k is no of buckets.

Example

Let us assume that the given array is 121, 432, 564, 23, 1, 45, 788.

Array -> 121 432 564 23 1 45 788.

Sort the elements based on the digit present at one's place(least significant place)
The one's place of the array is
1 2 4 3 1 5 8.
After sorting
1 1 2 3 4 5 8.
The array after sorting.
Array -> 121 1 432 23 564 45 788.

Sort the elements based on the digit present at ten's place.
The ten's place of the array is
2 0 3 2 6 4 8.
After sorting
0 2 2 3 4 6 8.
The array after sorting.
Array -> 1 121 23 432 45 564 788.

Sort the elements based on the digit present at hundred's place.
The hundred's place of the array is
0 1 0 4 0 5 7.
After sorting
0 0 0 1 4 5 7.
The array after sorting.
Array -> 1 23 45 121 432 564 788.

The final output is 1 23 45 121 432 564 788.

Implementing Radix Sort

  • C++

C++


#include <iostream>
using namespace std;

int Max(int array[], int n) { int max = array[0]; for (int i = 1; i < n; i++) if (array[i] > max) max = array[i]; return max; }
void countSort(int array[], int size, int pos) { int temp[size];//temporary array.
int count[10];/*auxiliary array that stores count of each element*/
// Initialize count array with all zeros. for (int i = 0; i <10; ++i) { count[i] = 0; }
// Store the count of each element for (int i = 0; i < size; i++) { count[((array[i] / pos) % 10)]++; }
// Store the cummulative count of each array for (int i = 1; i < 10 ; i++) { count[i] += count[i - 1]; }
//Sort and store elements in temporary array for (int i = size - 1; i >= 0; i--) { temp[count[((array[i] / pos) % 10)] - 1]= array[i]; count[((array[i] / pos) % 10)]--; }
// Copy the sorted elements into original array for (int i = 0; i < size; i++) { array[i] = temp[i]; } }
//Function implementing radix sort void radixsort(int array[], int size) { // Get maximum element int max =Max(array, size);
// Apply counting sort to sort elements based on place value. for (int place = 1; max / place > 0; place *= 10) countSort(array, size, place); }
// Function to print an array void print(int array[], int size) { for (int i = 0; i < size; i++) cout << array[i] << " "; cout << endl; }
int main() { int array[] = {121, 432, 564, 23, 1, 45, 788}; int n = sizeof(array) / sizeof(array[0]); radixsort(array, n); print(array, n); }

Output


1 23 45 121 432 564 788

Advantages of radix sort

  • It is faster than comparison sort when the range of array elements is less.
  • It is a stable sort.
  • It is used in Manber's algorithm and DC3 algorithm.

Disadvantages of radix sort

  • It takes more space.
  • It is less flexible than other sorts.

Postman Sort

The postman sort algorithm sorts the elements based on significant digits. It is a highly engineered variant of top-down radix sort where attributes of the key are described so the Sorting algorithm can allocate buckets and distribute efficiently. All the elements are divided by a particular base in this algorithm and sort the digits present at the particular position starting from the most significant position to the least significant position.

Algorithm

Step 1: Find the maximum value in the given array.
Step 2: Calculate no of digits present in the maximum value.
Step 3: Base is set according to the significant digits.
Step 4: Divide all elements by that particular base.
Step 5: Compare the elements based on the most significant digit and if the order is not correct swap them.
Step 6: Similarly next most significant digit is compared and the base is reset.

Time and Space complexity

  • The time complexity is O( d * (n+k)) because the time complexity of radix sort is O(d*(n+k)).
  • The space complexity is O(n+k).

where d is the no of digits present in maximum value, n is the size of the given array and k is no of buckets.

Example

Let us assume that the given array is 121, 432, 564, 23, 1, 45, 788.

Array -> 121 432 564 23 1 45 788.
The maximum value is 788 and no of digits is 3.
The base value is 100.

Sort the elements based on the digit present at hundred's place(most significant place)
The hundred's place of the array is
1 4 5 0 0 0 7.
After sorting
0 0 0 1 4 5 7.
The array after sorting.
Array -> 23 1 45 121 432 564 788.

Sort the elements based on the digit present at ten's place.
The base value is 10.
The array after sorting.
Array -> 1 23 45 121 432 564 788.

Sort the elements based on the digit present at hundred's place.
The base value is 1.
The array after sorting.
Array -> 1 23 45 121 432 564 788.

The final output is 1 23 45 121 432 564 788.

Advantages of postman sort

  • It is used by letter-sorting machines in post office.
  • It is faster than comparision sort.

Disadvantages of postman sort

  • It takes more space.

Pigeonhole Sort algorithm

The pigeonhole sort algorithm is similar to counting sort algorithm but it moves data to buckets before moving it to the final destination. It is suitable for sorting elements where no of elements is almost equal to the length of the range of possible key values.

Algorithm

Step 1: Find the maximum and minimum values in the array.
Step 2: Find the range using formula (maximum - minimum + 1)
Step 3: Initialize an array of size range
Step 4: Traverse the given array and insert the elements into the new array at index (arr[current element] - minimum)
Step 5: Traverse the new array and put its elements into the original array in increasing order.

Time and Space complexity

  • The time complexity is O(n+k) because the time taken to traverse the new array and put its element into original array takes O(n+k) time and all other steps take O(n).
  • The space complexity isO(n+k) because the space taken by new array is O(n+k).

where n is the no of elements in the given array and k is the size of new array (range).

Example

Let the given array be 4, 7, 3, 9, 8, 3, 5.
Array -> 4 7 3 9 8 3 5.
The maximum element is 9 and the minimum element is 3.
Range is 7 ( 9 - 3 + 1)

After inserting all the elements into the new array the new array looks like:
0 -> [ 3, 3]
1 -> [4]
2 -> [5]
3 -> []
4 -> [7]
5 -> [8]
6 -> [9]

After moving elements from the new array to the original array the original array looks like:
Array -> 3 3 4 5 7 8 9

Advantages of pigeonhole

  • It is faster when no of elements is almost equal to the length of the range of possible key values.
  • It is a stable sorting algorithm

Disadvantages of pigeonhole

  • It takes more space.
  • It cannot sort non-integers.
Sorting Algorithm Time complexity Space complexity Ideal condition
Counting sort O(n + k) O(n + k) It is efficient if the range of input data is not significantly greater than the number of elements.
Bucket sort O (n) O(n + k) It is efficient when elements are distributed uniformly
Radix sort O ( d * n) O(n + k) It is efficient when the no of significant digits in the maximum element of the array is less
Postman sort O( d * n) O(n + k) It is a variation of bucket sort specific for post service needs
Pigeonhole sort O(n + k) O(n + k) It is efficient when no of elements and no of possible key values are same