Radix Sort in Java

Radix sort is an efficient sorting algorithm that uses the concept of divide and conquer to sort elements in linear time. It is a non-comparative sorting algorithm that takes advantage of the fact that the elements in a given list can be sorted in a given order by using the radix of the elements. Radix sort works by first breaking the list of elements into buckets, or bins, based on their radix or base. These buckets are then sorted in a linear fashion, and the elements are grouped together in the correct order.

Radix sort is an ideal sorting algorithm for large data sets with elements of the same size. It is also useful for sorting elements in ascending or descending order. Additionally, it is a stable sorting algorithm, meaning that it does not change the relative order of elements with equal values.

In this article, we will discuss how radix sort works, its time complexity and space complexity, and provide some sample Java code demonstrating how to implement radix sort. We will also provide a few coding exercises to help readers further understand the concept of radix sort.

How Radix Sort Works

Radix sort is a non-comparative sorting algorithm that works in linear time. It works by taking advantage of the fact that each element in a list can be sorted by its base or radix.

The algorithm starts by dividing the list of elements into buckets, or bins, based on their radix or base. This is done by looping through the list and placing each element into its corresponding bucket. The buckets are then sorted in a linear fashion, and the elements are grouped together in the correct order.

Once the buckets are sorted, the elements are then reassembled in the correct order. This process is repeated until all of the elements have been sorted.

Radix sort is an ideal sorting algorithm for large data sets with elements of the same size. It is also useful for sorting elements in ascending or descending order.

Time Complexity

The time complexity of radix sort is O(n * k), where n is the number of elements in the list and k is the number of digits in the largest element. This means that radix sort can sort elements in linear time, making it an efficient sorting algorithm.

The average and worst case time complexities of access, search, insertion and deletion are all O(n * k).

Space Complexity

The space complexity of radix sort is O(n + k), where n is the number of elements in the list and k is the number of digits in the largest element. This means that radix sort requires a linear amount of space to sort elements.

Java Code

Here is some sample Java code demonstrating how to implement radix sort:

public static void radixSort(int[] arr) { 
	// Find the maximum number to know number of digits 
	int max = getMax(arr); 

	// Do 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; max/exp > 0; exp *= 10) 
		countSort(arr, exp); 
} 

// A function to do counting sort of arr[] according to 
// the digit represented by exp. 
public static void countSort(int[] arr, int exp) 
{ 
	int n = arr.length; 
	int output[] = new int[n]; // output array 
	int count[] = new int[10]; 
	Arrays.fill(count,0); 

	// Store count of occurrences in count[] 
	for (int i = 0; i < n; i++) 
		count[ (arr[i]/exp)%10 ]++; 

	// Change count[i] so that count[i] now contains 
	// actual position of this digit in output[] 
	for (int i = 1; i < 10; i++) 
		count[i] += count[i - 1]; 

	// Build the output array 
	for (int i = n - 1; i >= 0; i--) 
	{ 
		output[count[ (arr[i]/exp)%10 ] - 1] = arr[i]; 
		count[ (arr[i]/exp)%10 ]--; 
	} 

	// Copy the output array to arr[], so that arr[] now 
	// contains sorted numbers according to current digit 
	for (int i = 0; i < n; i++) 
		arr[i] = output[i]; 
} 

// The main function to that sorts arr[] of size n using 
// Radix Sort 
public static void radixSort(int arr[], int n) 
{ 
	// Find the maximum number to know number of digits 
	int m = getMax(arr, n); 

	// Do 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) 
		countSort(arr, n, exp); 
} 

Conclusion

In conclusion, radix sort is an efficient sorting algorithm that works in linear time and requires a linear amount of space to sort elements. It is an ideal sorting algorithm for large data sets with elements of the same size and is useful for sorting elements in ascending or descending order.

Exercises

public static void radixSort(int[] arr) { 
	// Find the maximum number to know number of digits 
	int max = getMax(arr); 

	// Do 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; max/exp > 0; exp *= 10) 
		countSort(arr, exp); 
} 

public static void radixSortStrings(String[] arr, int stringLen) 
{ 
	final int BUCKETS = 256; 

	String[][] buckets = new String[BUCKETS][stringLen]; 

	for (int i = 0; i < stringLen; i++) { 
		// create buckets 
		for (String s : arr) { 
			int bucketIndex = (int)s.charAt(i); 
			buckets[bucketIndex][i] = s; 
		} 

		int k = 0; 
		// collect elements from buckets 
		for (int j = 0; j < BUCKETS; j++) { 
			for (int l = 0; l < stringLen; l++) { 
				if (buckets[j][l] != null) { 
					arr[k++] = buckets[j][l]; 
				} 
			} 
		} 
	} 
} 

public static void radixSort(int[] arr) { 
	// Find the maximum number to know number of digits 
	int max = getMax(arr); 

	// Do 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; max/exp > 0; exp *= 10) 
		countSort(arr, exp); 
} 

public static void radixSortStrings(String[] arr, int stringLen) 
{ 
	final int BUCKETS = 256; 

	String[][] buckets = new String[BUCKETS][stringLen]; 

	for (int i = 0; i < stringLen; i++) { 
		// create buckets 
		for (String s : arr) { 
			int bucketIndex = (int)s.charAt(i); 
			buckets[bucketIndex][i] = s; 
		} 

		int k = 0; 
		// collect elements from buckets 
		for (int j = 0; j < BUCKETS; j++) { 
			for (int l = 0; l < stringLen; l++) { 
				if (buckets[j][l] != null) { 
					arr[k++] = buckets[j][l]; 
				} 
			} 
		} 
	} 
} 

public static int getMax(int[] arr) 
{ 
	int max = arr[0]; 
	for (int i = 1; i < arr.length; i++) 
		if (arr[i] > max) 
			max = arr[i]; 
	return max; 
}