Tim Koval
Geek; Embedded Systems Developer; Firmware, Hardware and System Software Engineer;

Sorting Algorithms – Part 2

As you could notice from the previous post about sorting algorithms, all the given have no less than O(nlogn) time complexity. It is actually a limit for sortings based on Comparison Model. It was proved mathematically that this kind of sorting algorithms cannot be faster than O(nlogn). Moreover, searching cannot be faster than O(logn) as well. The detailed information is given in the 7th lecture of 6.006 so I don’t really want to describe it here because it is not necessary.

Fortunately, we have another type of sorting algorithms based on Random Access Model which are counting all the elements given as an array to sort them.

There are two of them given in the course – Counting sort and Radix Sort.

Counting sort

Sorting by counting number of occurrences of each element in array and placing elements of the array by the sum of all previous elements numbers.

void countingSort(int *arr, int size)
{
	int counter[256] = {0};
	int output[size];
	int max = arr[0];

	for (int i = 1; i < size; i++)
		if (arr[i] > max)
			max = arr[i];

	for (int i = 0; i < size; i++)
		counter[arr[i]]++;

	for (int i = 1; i <= max; i++)
		counter[i] += counter[i - 1];

	for (int i = size - 1; i >= 0; i--) {
		output[counter[arr[i]] - 1] = arr[i];
		counter[arr[i]]--;
	}

	for (int i = 0; i < size; i++)
		arr[i] = output[i];
}

Then in main() :

	countingSort(arr, size);

This technique is bad in terms complexity for large number because it needs to count for the maximum element. Complexity = O(n+k) – number of elements + maximum element/key Extra space = O(k) – value of maximum element/key

Radix sort

This algorithm is based on the concept of sorting each level digits using Counting sort algorithm. This approach limits the maximum element to 9 to prevent the main problem of the previous algorithm.

A little bit changed countingSort() :

void countingSort(int *arr, int size, int digit)
{
	const int max = 9 ;
	int counter[max] = {0};
	int output[size];

	for (int i = 0; i < size; i++)
		counter[(arr[i] / digit) % 10]++;

	for (int i = 1; i < 10; i++)
		counter[i] += counter[i - 1];

	for (int i = size - 1; i >= 0; i--) {
		output[counter[(arr[i] / digit) % 10] - 1] = arr[i];
		counter[(arr[i] / digit) % 10]--;
	}

	for (int i = 0; i < size; i++)
		arr[i] = output[i];
}

Finding maximum by findMax() :

int findMax (int *arr, int size)
{
    int max = arr[0]; 
    for (int i = 1; i < size; i++) 
        if (arr[i] > max) 
            max = arr[i]; 
    return max; 
}

And actually radixSort() :

void radixSort(int *arr, int size)
{
	int max = findMax(arr, size);

	for (int digit = 1; max  / digit > 0; digit *= 10)
		countingSort(arr, size, digit);
}

Sorting from main(), as always :

	radixSort(arr, size);

Complexity = O(d(n+k)) where d – number of digits, n – number of elements + k – maximum element/key

I think that every of the given algorithms can be used according to the particular case. Moreover, programmers often write their own or modify existing to make it suitable for their tasks.

I hope this materials will help you to understand or at least to know the main algorithms of sorting.

Next time I will write about any other topics covered by 6.006 and I think that the following posts will be much bigger because of more complicated algorithms and data structures considered.

Share

You may also like...

Leave a Reply