{"id":25185,"date":"2017-10-15T14:47:18","date_gmt":"2017-10-15T09:17:18","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25185"},"modified":"2017-10-15T14:47:18","modified_gmt":"2017-10-15T09:17:18","slug":"radix-sort","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/radix-sort\/","title":{"rendered":"Radix Sort"},"content":{"rendered":"

The lower bound for Comparison based sorting algorithm<\/a> (Merge Sort, Heap Sort, Quick-Sort .. etc) is \u03a9(nLogn), i.e., they cannot do better than nLogn.<\/span><\/p>\n

Counting sort<\/a> is a linear time sorting algorithm that sort in O(n+k) time when elements are in range from 1 to k.<\/p>\n

What if the elements are in range from 1 to n2<\/sup>? <\/em><\/strong>
\nWe can\u2019t use counting sort because counting sort will take O(n2<\/sup>) which is worse than comparison based sorting algorithms. Can we sort such an array in linear time?
\nRadix Sort<\/a> is the answer. The idea of Radix Sort is to do digit by digit sort starting from least significant digit to most significant digit. Radix sort uses counting sort as a subroutine to sort.<\/p>\n

The Radix Sort Algorithm<\/strong><\/em>
\n1)<\/strong> Do following for each digit i where i varies from least significant digit to the most significant<\/p>\n

2)<\/b> Sort input array using counting sort (or any stable sort) according to the i\u2019th digit.<\/p>\n

Example:<\/strong>
\nOriginal, unsorted list:<\/p>\n

\n
170, 45, 75, 90, 802, 24, 2, 66<\/dd>\n<\/dl>\n

Sorting by least significant digit (1s place) gives: [*Notice that we keep 802 before 2, because 802 occurred before 2 in the original list, and similarly for pairs 170 & 90 and 45 & 75.]\n

\n
170, 90, 802,\u00a02, 24, 45, 75, 66<\/dd>\n<\/dl>\n

Sorting by next digit (10s place) gives: [*Notice that 802 again comes before 2 as 802 comes before 2 in the previous list.]\n

\n
802, 2,\u00a024,\u00a045,\u00a066, 170,\u00a075,\u00a090<\/dd>\n<\/dl>\n

Sorting by most significant digit (100s place) gives:<\/p>\n

\n
2, 24, 45, 66, 75, 90,\u00a0170,\u00a0802<\/dd>\n<\/dl>\n[ad type=”banner”]\n

What is the running time of Radix Sort?<\/strong><\/em>
\nLet there be d digits in input integers. Radix Sort takes O(d*(n+b)) time where b is the base for representing numbers, for example, for decimal system, b is 10. What is the value of d? If k is the maximum possible value, then d would be O(logb<\/sub>(k)). So overall time complexity is O((n+b) * logb<\/sub>(k)). Which looks more than the time complexity of comparison based sorting algorithms for a large k. Let us first limit k. Let k <= nc<\/sup> where c is a constant. In that case, the complexity becomes O(nLogb<\/sub>(n)). But it still doesn\u2019t beat comparison based sorting algorithms.
\nWhat 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, we get the time complexity as O(n). In other words, we can sort an array of integers with range from 1 to nc<\/sup> if the numbers are represented in base n (or every digit takes log2<\/sub>(n) bits).<\/p>\n

Is Radix Sort preferable to Comparison based sorting algorithms like Quick-Sort?<\/strong><\/em>
\nIf we have log2<\/sub>n bits for every digit, the running time of Radix appears to be better than Quick Sort for a wide range of input numbers. The constant factors hidden in asymptotic notation are higher for Radix Sort and Quick-Sort uses hardware caches more effectively. Also, Radix sort uses counting sort as a subroutine and counting sort takes extra space to sort numbers.<\/p>\n

Implementation of Radix Sort<\/strong>
\nFollowing is a simple C++ implementation of Radix Sort. For simplicity, the value of d is assumed to be 10. We recommend you to see Counting Sort<\/a> for details of countSort() function in below code.<\/p>\n

C<\/strong><\/p>\n

c<\/span> <\/div> 
\/\/ C++ implementation of Radix Sort#include<iostream>using namespace std; \/\/ A utility function to get maximum value in arr[]int getMax(int arr[], int n){    int mx = arr[0];    for (int i = 1; i < n; i++)        if (arr[i] > mx)            mx = arr[i];    return mx;} \/\/ A function to do counting sort of arr[] according to\/\/ the digit represented by exp.void countSort(int arr[], int n, int exp){    int output[n]; \/\/ output array    int i, count[10] = {0};     \/\/ Store count of occurrences in count[]    for (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 (i = 1; i < 10; i++)        count[i] += count[i - 1];     \/\/ Build the output array    for (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 (i = 0; i < n; i++)        arr[i] = output[i];} \/\/ The main function to that sorts arr[] of size n using \/\/ Radix Sortvoid 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);} \/\/ A utility function to print an arrayvoid print(int arr[], int n){    for (int i = 0; i < n; i++)        cout << arr[i] << " ";} \/\/ Driver program to test above functionsint main(){    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};    int n = sizeof(arr)\/sizeof(arr[0]);    radixsort(arr, n);    print(arr, n);    return 0;}<\/code><\/pre> <\/div>\n[ad type=”banner”]\n
JAVA<\/strong><\/p>\n
 
 java<\/span> <\/div> 
\/\/ Radix sort Java implementationimport java.io.*;import java.util.*; class Radix {     \/\/ A utility function to get maximum value in arr[]    static int getMax(int arr[], int n)    {        int mx = arr[0];        for (int i = 1; i < n; i++)            if (arr[i] > mx)                mx = arr[i];        return mx;    }     \/\/ A function to do counting sort of arr[] according to    \/\/ the digit represented by exp.    static void countSort(int arr[], int n, int exp)    {        int output[] = new int[n]; \/\/ output array        int i;        int count[] = new int[10];        Arrays.fill(count,0);         \/\/ Store count of occurrences in count[]        for (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 (i = 1; i < 10; i++)            count[i] += count[i - 1];         \/\/ Build the output array        for (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 curent digit        for (i = 0; i < n; i++)            arr[i] = output[i];    }     \/\/ The main function to that sorts arr[] of size n using    \/\/ Radix Sort    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);    }     \/\/ A utility function to print an array    static void print(int arr[], int n)    {        for (int i=0; i<n; i++)            System.out.print(arr[i]+" ");    }      \/*Driver function to check for above function*\/    public static void main (String[] args)    {        int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};        int n = arr.length;        radixsort(arr, n);        print(arr, n);    }}<\/code><\/pre> <\/div>\n
PYTHON<\/strong><\/p>\n
 
 PYTHON<\/span> <\/div> 
# Python program for implementation of Radix Sort # A function to do counting sort of arr[] according to# the digit represented by exp.def countingSort(arr, exp1):     n = len(arr)     # The output array elements that will have sorted arr    output = [0] * (n)     # initialize count array as 0    count = [0] * (10)     # Store count of occurrences in count[]    for i in range(0, n):        index = (arr[i]\/exp1)        count[ (index)%10 ] += 1     # Change count[i] so that count[i] now contains actual    #  position of this digit in output array    for i in range(1,10):        count[i] += count[i-1]     # Build the output array    i = n-1    while i>=0:        index = (arr[i]\/exp1)        output[ count[ (index)%10 ] - 1] = arr[i]        count[ (index)%10 ] -= 1        i -= 1     # Copying the output array to arr[],    # so that arr now contains sorted numbers    i = 0    for i in range(0,len(arr)):        arr[i] = output[i] # Method to do Radix Sortdef radixSort(arr):     # Find the maximum number to know number of digits    max1 = max(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    exp = 1    while max1\/exp > 0:        countingSort(arr,exp)        exp *= 10 # Driver code to test abovearr = [ 170, 45, 75, 90, 802, 24, 2, 66]radixSort(arr) for i in range(len(arr)):    print(arr[i]),<\/code><\/pre> <\/div>\n
Output:<\/p>\n
2 24 45 66 75 90 170 802<\/pre>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
Radix Sort – Searching and Sorting -The lower bound for Comparison based sorting algorithm (Merge Sort, Heap Sort, Quick-Sort .. etc is \u03a9(nLogn). i.e., they cannot do better than nLogn.<\/p>\n","protected":false},"author":1,"featured_media":25187,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,83503,71670],"tags":[71852,71847,71832,71840,71853,70461,71860,71855,71865,71864,71834,71850,70047,71859,71833,71868,71849,70048,71836,71838,70492,70928,70017,71839,71866,70754,71841,71262,71070,71267,71837,71266,71862,71835,71844,71863,71857,71858,71846,71856,71861,71843,71854,71845,71867,71848,71842,70016,71851],"class_list":["post-25185","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithm","category-radix-sort","category-searching-and-sorting","tag-algorithm-for-radix-sort","tag-algorithm-for-radix-sort-in-data-structure","tag-algorithm-of-bucket-sort","tag-algorithm-of-radix-sort","tag-algorithm-of-radix-sort-in-data-structure","tag-bubble-sort","tag-bucket-sort-algorithm-example","tag-bucket-sort-algorithm-with-example","tag-bucket-sort-pdf","tag-bucket-sort-ppt","tag-c-language","tag-c-program-for-radix-sort","tag-c-programming","tag-cocktail-sort","tag-comb-sort","tag-counting-sort-algorithm","tag-data-structure-tutorial","tag-data-structures","tag-dotfuscator","tag-ember-js","tag-hash-function","tag-heap-sort-algorithm","tag-insertion-sort-algorithm","tag-java-windows-7","tag-jquery-datatable","tag-kruskals-algorithm","tag-mcreator","tag-merge-sort-algorithm","tag-programming","tag-quick-sort-algorithm","tag-quicksort-","tag-radix-sort-algorithm","tag-radix-sort-algorithm-in-c","tag-radix-sort-algorithm-in-data-structure-ppt","tag-radix-sort-algorithm-in-java","tag-radix-sort-algorithm-ppt","tag-radix-sort-algorithm-pseudocode","tag-radix-sort-analysis","tag-radix-sort-applications","tag-radix-sort-c-code","tag-radix-sort-c-program","tag-radix-sort-code-java","tag-radix-sort-implementation","tag-radix-sort-in-c-program","tag-radix-sort-program-in-c","tag-radix-sort-program-in-c-with-output","tag-radix-sort-python","tag-selection-sort-algorithm","tag-thread-java"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25185","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25185"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25185\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/25187"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25185"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25185"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25185"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}