@@ -0,0 +1,2659 @@
+/*%0ACounting sort is a linear tine sorting algorithm that sort in O(n+k) time when elements are in range from 1 to k.%0A%0AWhat if the elements are in range from 1 to n2? %0AWe can%E2%80%99t use counting sort because counting sort will take O(n2) which is worse than comparison based sorting algorithms.%0ACan we sort such an array in linear time?%0ARadix Sort is the answer. The idea of Radix Sort is to do digit by digit sort starting from least significant digit to %0Amost significant digit. Radix sort uses counting sort as a subroutine to sort.%0A*/%0A%0A/*%0AThe Radix Sort Algorithm%0A1) Do following for each digit i where i varies from least significant digit to the most significant digit.%0A%E2%80%A6%E2%80%A6%E2%80%A6%E2%80%A6.a) Sort input array using counting sort (or any stable sort) according to the i%E2%80%99th digit.%0A%0AExample:%0AOriginal, unsorted list:%0A%0A170, 45, 75, 90, 802, 24, 2, 66%0ASorting by least significant digit (1s place) gives: %5B*Notice that we keep 802 before 2, because 802 occurred before 2 %0Ain the original list, and similarly for pairs 170 & 90 and 45 & 75.%5D%0A%0A170, 90, 802, 2, 24, 45, 75, 66%0ASorting by next digit (10s place) gives: %5B*Notice that 802 again comes before 2 as 802 comes before 2 in the previous %0Alist.%5D%0A%0A802, 2, 24, 45, 66, 170, 75, 90%0ASorting by most significant digit (100s place) gives:%0A%0A2, 24, 45, 66, 75, 90, 170, 802%0A%0A*/%0A%0A%0A/*%0ALet there be d digits in input integers. Radix Sort takes O(d*(n+b)) time where b is the base for representing numbers, %0Afor example, for decimal system, b is 10. What is the value of d? If k is the maximum possible value, then d would be%0AO(logb(n)).%0A%0ASo overall time complexity is O((n+b)*%5Clog_b(k)). Which looks more than the time complexity of comparison based sorting %0Aalgorithms for a large k. Let us first limit k. Let k %3C= nc where c is a constant. In that case, the complexity becomes %0AO(n%5Clog_b(n)). But it still doesn%E2%80%99t beat comparison based sorting algorithms.%0AWhat if we make value of b larger?. What should be the value of b to make the time complexity linear? If we set b as n, %0Awe get the time complexity as O(n). In other words, we can sort an array of integers with range from 1 to nc if the %0Anumbers are represented in base n (or every digit takes %5Clog_2(n) bits).%0A%0AIs Radix Sort preferable to Comparison based sorting algorithms like Quick-Sort?%0AIf we have %5Clog_2(n) bits for every digit, the running time of Radix appears to be better than Quick Sort for a wide %0Arange of input numbers. The constant factors hidden in asymptotic notation are higher for Radix Sort and Quick-Sort uses %0Ahardware caches more effectively. Also, Radix sort uses counting sort as a subroutine and counting sort takes extra space%0Ato sort numbers.%0A%0A%0A*/%0A

Create RadixSort.java