Counting Sort

Review

 Name Counting Sort Complexity Θ(k + n) Stable YES In place NO Adaptive NO Difficulty Easy Method No comparison sort

Count each value to sort an array

The idea of the Counting Sort is to count how many times each value appears in the array (`A`) to sort. Hence, Counting Sort assumes that the input consists of integers in a small range (0 - k). We implement that process by using another array (`C`), in where each the cell index represents the count of the respective values in the original array. Then we cycle again through `C` and we add the previous value to each cell in order to come up with all the elements less or equal than the previous's. For instance:

A = {2, 4, 2, 5, 1, 4, 2, 1}
C = {0, 2, 3, 0, 2, 1} // x0 - 0, x2 - 1, x3 - 2, x0 - 3, x2 - 4, x1 - 5
C = {0, 2, 5, 5, 7, 8}

From here we initialize another array (`B`) in which we copy the elements of A sorted in order. We assign to B[C[A[i]]] the value of A[i] and then decrease C[A[i]] of one.

i = 7
A[7] = 1;
C[A[7]] = C[1] = 2;
B[C[A[7]]] = B[2] = A[7] = 1;
C = {0, 1, 5, 5, 7, 8}
B = {0, 1, 0, 0, 0, 0, 0, 0}

i = 6
A[6] = 2;
C[A[6]] = C[2] = 5;
B[C[A[6]]] = B[5] = A[6] = 2;
C = {0, 1, 4, 5, 7, 8}
B = {0, 1, 0, 0, 2, 0, 0, 0}

i = 5
A[5] = 4;
C[A[5]] = C[4] = 7;
B[C[A[5]]] = B[7] = A[5] = 4;
C = {0, 1, 4, 5, 6, 8}
B = {0, 1, 0, 0, 2, 0, 4, 0}

i = 4
A[4] = 1;
C[A[4]] = C[1] = 1;
B[C[A[4]]] = B[1] = A[4] = 1;
C = {0, 0, 4, 5, 6, 8}
B = {1, 1, 0, 0, 2, 0, 4, 0}

...

Programming languages implementation

C++

``````#define SIZE 12
#define MAX 6

int main() {
// 0 < k < 5
// Initialize arrays
int A[SIZE] = {2, 5, 3, 0, 2, 3, 0, 3, 4, 5, 1, 1};
int B[SIZE];
int C[MAX];

// Set C's values to 0
for (int i = 0; i < MAX; ++i) {
C[i] = 0;
}

// Count the values of A and place them in the A[j] position in C
for (int j = 0; j < SIZE; ++j) {
C[A[j]] = C[A[j]] + 1;
}

// C[m] now contains the number of elements less than or equal to m
for (int m = 1; m < MAX; ++m) {
C[m] = C[m] + C[m - 1];
}

// Add the values sorted in B
for (int n = SIZE - 1; n >= 0; --n) {
B[C[A[n]] - 1] = A[n];
C[A[n]] = C[A[n]] - 1;
}

return 0;
}
``````

Review

 Name Radix Sort Best case Θ(d(n + k)) Stable YES In place YES Adaptive YES Difficulty Easy Method Sort By Digits

Sort Digit by Digit

The Radix sort is pretty straightforward. The idea is to order the array digit by digit. We first take the first digit of all the values of the array to sort and order them with a stable algorithm (We used Insertion sort). We do that for all the digits and we end up with all the numbers sorted.

A = {324, 129, 355, 427, 641}
First digit
A = {641, 324, 355, 427, 129}

Second digit
A = {324, 427, 129, 641, 355}

Third digit
A = {129, 324, 355, 427, 641}

Programming languages implementation

C++

``````#define SIZE 7

int getMax(int A[]) {
// Set max to first value
int max = A[0];

// If we find another value greater than max, update max*s
for (int i = 1; i < SIZE; ++i) {
if (A[i] > max)
max = A[i];
}

return max;
}

// Count digits of 'max'
int getDigits(int max) {
int digits = 0;
while (max > 0) {
max = max / 10;
++digits;
}

return digits;
}

// Get single digit to sort
// 0 (zero) if digits of number < index
int getSingleDigit(int number, int index) {
int digit = 10;
int i = 0;

while (i != index) {
digit = (number % 10);
number = number / 10;
++i;
}

return digit;
}

// Insertion sort (check out our article to find out more about it)
void insertionSort(int A[], int digitIndex) {
for (size_t j = 1; j < SIZE; ++j) {
// Get digit of current selected number
int key = getSingleDigit(A[j], digitIndex);
// Get original key value
int finalKey = A[j];

// while cycle from the number before the 'key'
int i = j - 1;

// Switch values if current digit value is greater than key
while (i >= 0 && getSingleDigit(A[i], digitIndex) > key) {
A[i + 1] = A[i];
--i;
}

// Reinsert the original key value in sorted order
A[i + 1] = finalKey;
}
}

int main() {
// Array to sort
int A[SIZE] = {339, 412, 657, 839, 236, 720, 355};
// Get max value of the array and count its digits
int max = getMax(A);
int digits = getDigits(max);

// Sort each digit with an Insertion Sort
for (int d = 1; d <= digits; ++d) {
insertionSort(A, d);
}

return 0;
}
``````

Bucket Sort

Review

 Name Bucket Sort Best case Θ(n) Stable YES In place YES Adaptive NO Difficulty Medium Method Sort Sublists

Create buckets and sort them

Like counting sort, bucket sort is fast because it assumes something about the input. Bucket Sort assumes that the input is generated by a random process that distributes elements uniformly and independently over the interval [0; 1). The idea is to create an auxiliary array where each cell points to a pointer to a list (Check out our article about how to implement Linked Lists). For each number, we push its value on the list in the position at the index equal to its value * 10 (0.78 x 10 = index 7). Then we cycle through the array and sort each list with the Insertion Sort. Now we just need to print all the lists in order to end up with our initial array sorted.

A = {0.76, 0.31, 0.53, 0.22, 0.38, 0.31, 0.11, 0.77, 0.72}
0 -> /
1 -> 0.11 -> /
2 -> 0.22 -> /
3 -> 0.31 -> 0.31 -> 0.38 -> /
4 -> /
5 -> 0.53 -> /
6 -> /
7 -> 0.72 -> 0.76 -> 0.77
8 -> /
9 -> /

Programming languages implementation

C++

``````#define SIZE 10

// Node of the list
struct Node {
float value;
Node* next;
};

// Insertion sort (check out our article to find out more about it)
void insertionSort(std::vector& A) {
for (size_t j = 1; j < A.size(); ++j) {
// Get value of current selected number
float key = A[j];
// while cycle from the number before the 'key'
int i = j - 1;
// Switch values if current number is greater than key
while (i >= 0 && A[i] > key) {
A[i + 1] = A[i];
--i;
}

// Reinsert the key in sorted order
A[i + 1] = key;
}
}

int main() {
// Array to sort (A) and list array (B)
float A[SIZE] = {.78, .07, .39, .26, .22, .24, .21, .12, .23, .68};
Node* B[SIZE];

// Setup B's nodes
for (int i = 0; i < SIZE; ++i) {
Node* temp = new Node;
temp->next = nullptr;

B[i] = temp;
}

// Add values in the lists of B
for (int j = 0; j < SIZE; ++j) {
Node* newNode = new Node;
newNode->next = nullptr;
newNode->value = A[j];

Node* curr = B[(int) (10 * A[j])];
while (curr->next != nullptr) {
curr = curr->next;
}

curr->next = newNode;
}

// Sort each list with the Insertion Sort above
for (int p = 0; p < SIZE; ++p) {
std::vector array;

Node* curr = B[p];
// Push back each value in a vector to sort
while (curr->next != nullptr) {
curr = curr->next;
array.push_back(curr->value);
}

insertionSort(array);
}

return 0;
}
``````

This was the last article about Sorting Algorithms. We covered all the main sorting algorithms:

If you have any question feel free to email us and do not forget to subscribe to our newsletter to be notified of future articles.