Tag Archives: Counting sort

Radix Sort Program and Complexity (Big-O)


Radixsort sorts numeric data (integers or float) by considering a string of numbers where digit by digit sort starting from least significant digit position to most significant digit position. To sort these specific positions data counting sort as a subroutine.

Counting sort is a linear time sorting algorithm that sort in O(n+k) but that will worst in case of items range from 1 to n2 that sort in O(n^2). Where K is items range from 1 to k.

Note :

  • LSD : Least Significant Digit
  • MSD : Most Significant Digit

Steps to Radixsort

  1. Check for the max length item in input values and check for length.
  2. For each digit position i where i varies from LSD to the MSD.
  3. Perform counting sort based on considering key as i position digits.
  4. Finally, you will get a sorting array for input items.

Points to Remember

  • Data Structure: Array
  • Best Time Complexity: Ω(nk)
  • Average Time Complexity: Θ(nk)
  • Worst Time Complexity: O(nk)
  • Worst Space Complexity: O(n+k)

Radix sort Example


Input Numbers:

        170, 45, 75, 90, 02, 802, 2, 66 
Step 1 : Find the max item length in input i.e 3.

Step 2: Repeat the below process for position i from LSD to MSD
        Perform count sort on numbers, after considering digits as key on 
        particular i.
        
        0 Position :
        170, 90, 02, 802, 2, 45, 75, 66
        
        1 Position :
        02, 2, 802, 45, 66, 170, 75, 90
        
        2 Position :
        02, 2, 45, 66, 75, 90, 170, 802 
        
Step 3: Final Redix Sort result

        02, 2, 45, 66, 75, 90, 170, 802    
 

Radix Sort Program

public class RadixSort {

	public static void main(String[] args) {

		// Assuming our key values are with in range 0 - 9
		int[] items = { 170, 45, 75, 90, 02, 802, 2, 66 };
		System.out.println("Before Radix Sorting :");
		printArray(items);

		// Perform counting sort sort
		radixsort(items);

		System.out.println("After Radix Sorting :");
		printArray(items);
	}

	// radix sort method to sort values of array items
	static void radixsort(int items[]) {
		// find max number to know max number of digits
		int m = getMax(items);

		// Perform counting sort for every digit. Note that instead
		// of passing digit number, exp is passed. exp is 10^i
		// where i is current digit number
		for (int exp = 1; m / exp > 0; exp *= 10)
			countingsort(items, exp);
	}

	// A utility method to get maximum value in items[]
	static int getMax(int items[]) {
		int max = items[0];
		for (int i = 1; i  max)
				max = items[i];
		return max;
	}

	private static void countingsort(int[] items, int exp) {
		// create array of size 10 that will have index value as 0-9
		// it will create array of size 10 and initialize
		// each element with value 0
		int[] counts = new int[10];
		int[] output = new int[items.length];
		for (int key : items) {
			// for each match key, index position element
			// increase count as 1
			counts[(key / exp) % 10] += 1;
		}

		// Change count[i] so that count[i] now contains
		// actual position of this digit in output[]
		for (int i = 1; i = 0; i--) {
			output[counts[(items[i] / exp) % 10] - 1] = items[i];
			counts[(items[i] / exp) % 10] -= 1;
		}

		// Copy the output array to items[] to return
		// sorted array according to index position
		for (int i = 0; i < items.length; i++)
			items[i] = output[i];

	}

	static void printArray(int items[]) {
		for (int item : items) {
			System.out.print(item + " ");
		}
		System.out.println();
	}

}

Output


Before Radix Sorting :
170 45 75 90 2 802 2 66 
After Radix Sorting :
2 2 45 66 75 90 170 802 

Counting Sort program & Complexity (Big-O)


Counting sort also called an integer sorting algorithm. Counting sort algorithm is based on keys in a specific range. It counts the number of items for distinct key value, use these keys to determine position or indexing on the array and store respective counts for each key. Finally, sort values based on keys and make sequences the repetition of key based on counts.

Counting sort is suitable where variation in keys are is not significantly greater than the number of items. Its running time is linear as numbers of items(n)+difference between max and min key values.

Points to Remember

  • Data structure: Array
  • Worst-case performance: O(n+k), where k is the range of the non-negative key values.
  • Worst-case space complexity: O(n+k)

Advantage

  • Counting sort is a stable sort, where if two items have the same key, they should have the same relative position in the sorted output as they did in the input.

Disadvantage

  • Data range should be predefined, if not then addition loops required to get min and max value to get range.
  • Not much variation on key values otherwise will occupy unnecessary space in the array.

Steps for Counting Sort


For easily understand, consider the data in the range 0 to 9 for below example:
Input data: 2, 6, 3, 2, 8, 4, 8, 1, 5, 3, 1, 4, 0
1) Create an array of size 10 (index values 0-9) and store the count of each 
   unique item.
  Index:     0  1  2  3  4  5  6  7  8  9
  Count:     1  2  2  2  2  1  1  0  2  0

2) Execute loop for each index for array and check counts are more than zero. 
   repeat the index/key value until count reach to zero. Store these values in 
   previous array and increase index position by one. Now sorted array
 
  Index:     0  1  2  3  4  5  6  7  8  9 10   11 12
  Count:     0  1  1  2  2  3  3  4  4  5  6   8  8

Counting Sort Program

public class CountingSort {

	public static void main(String[] args) {

		//Assuming our key values are with in range 0 - 9
		int[] items = { 2, 6, 3, 2, 8, 4, 8, 1, 5, 3, 1, 4, 0};
        System.out.println("Before Counting Sorting :");
        printArray(items);

        //Perform counting sort sort
        countingsort(items);

        System.out.println("After Count Sorting :");
        printArray(items);
	}

	private static void countingsort(int []items)
	{
		//create array of size 10 that will have index value as 0-9
		//it will create array of size 10 and initialize
		//each element with value 0
		int []numbers=new int[10];
		for(int key:items)
		{
			//for each match key, index position element
			//increase count as 1
			numbers[key]+=1;
		}

		//Now sort values based on keys and repeat
		//this key value as per count
		int i=0;
		for(int key=0; key0)
			{
				for(int count=1;count<=numbers[key];count++)
				{
					items[i++]=key;
				}
			}

		}
	}

	static void printArray(int items[])
	{
        for (int item:items)
        {
            System.out.print(item + " ");
        }
        System.out.println();
	}

}

Output


Before Counting Sorting :
2 6 3 2 8 4 8 1 5 3 1 4 0 
After Count Sorting :
0 1 1 2 2 3 3 4 4 5 6 8 8