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;
}

 

 

 

Radix Sort

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.