{"id":25247,"date":"2017-10-15T16:14:58","date_gmt":"2017-10-15T10:44:58","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25247"},"modified":"2017-10-15T16:14:58","modified_gmt":"2017-10-15T10:44:58","slug":"sort-n-numbers-range-0-n2-1-linear-time","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/sort-n-numbers-range-0-n2-1-linear-time\/","title":{"rendered":"Sort n numbers in range from 0 to n^2 \u2013 1 in linear time"},"content":{"rendered":"

Given an array of numbers of size n. It is also given that the array elements are in range from 0 to n2<\/sup>\u2013 1. Sort the given array in linear time.<\/span><\/p>\n

Examples:\r\nSince there are 5 elements, the elements can be from 0 to 24.\r\nInput: arr[] = {0, 23, 14, 12, 9}\r\nOutput: arr[] = {0, 9, 12, 14, 23}\r\n\r\nSince there are 3 elements, the elements can be from 0 to 8.\r\nInput: arr[] = {7, 0, 2}\r\nOutput: arr[] = {0, 2, 7}\r\n<\/pre>\n
We strongly recommend to minimize the browser and try this yourself first.<\/strong><\/em><\/p>\n
Solution:<\/strong> If we use Counting Sort<\/a>, it would take O(n^2) time as the given range is of size n^2. Using any comparison based sorting like Merge Sort<\/a>, Heap Sort<\/a>, .. etc would take O(nLogn) time.
\nNow question arises how to do this in 0(n)? Firstly, is it possible? Can we use data given in question? n numbers in range from 0 to n2<\/sup> \u2013 1?
\nThe idea is to use Radix Sort<\/a>. Following is standard Radix Sort algorithm.<\/p>\n
1) Do following for each digit i where i varies from least \r\n   significant digit to the most significant digit.\r\n\u2026\u2026\u2026\u2026..a) Sort input array using counting sort (or any stable \r\n         sort) according to the i\u2019th digit\r\n<\/pre>\n
Let 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. Since n2<\/sup>-1 is the maximum possible value, the value of d would be O(logb<\/sub>(n)). So overall time complexity is O((n+b)*O(logb<\/sub>(n)). Which looks more than the time complexity of comparison based sorting algorithms for a large k. The idea is to change base b. If we set b as n, the value of O(logb<\/sub>(n)) becomes O(1) and overall time complexity becomes O(n).<\/p>\n
arr[] = {0, 10, 13, 12, 7}\r\n\r\nLet us consider the elements in base 5. For example 13 in\r\nbase 5 is 23, and 7 in base 5 is 12.\r\narr[] = {00(0), 20(10), 23(13), 22(12), 12(7)}\r\n\r\nAfter first iteration (Sorting according to the last digit in \r\nbase 5),  we get.\r\narr[] = {00<\/u>(0), 20<\/u>(10), 12<\/u>(7), 22<\/u>(12), 23<\/u>(13)}\r\n\r\nAfter second iteration, we get\r\narr[] = {0<\/u>0(0), 1<\/u>2(7), 2<\/u>0(10), 2<\/u>2(12), 2<\/u>3(13)}\r\n<\/pre>\n
Following is C++ implementation to sort an array of size n where elements are in range from 0 to n2<\/sup> \u2013 1.<\/p>\n[ad type=”banner”]\n
C++<\/strong><\/p>\n
 
 c++<\/span> <\/div> 
#include<iostream>using namespace std; \/\/ A function to do counting sort of arr[] according to\/\/ the digit represented by exp.int countSort(int arr[], int n, int exp){     int output[n]; \/\/ output array    int i, count[n] ;    for (int i=0; i < n; i++)       count[i] = 0;     \/\/ Store count of occurrences in count[]    for (i = 0; i < n; i++)        count[ (arr[i]\/exp)%n ]++;     \/\/ Change count[i] so that count[i] now contains actual    \/\/ position of this digit in output[]    for (i = 1; i < n; i++)        count[i] += count[i - 1];     \/\/ Build the output array    for (i = n - 1; i >= 0; i--)    {        output[count[ (arr[i]\/exp)%n] - 1] = arr[i];        count[(arr[i]\/exp)%n]--;    }     \/\/ 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 Sortvoid sort(int arr[], int n){    \/\/ Do counting sort for first digit in base n. Note that    \/\/ instead of passing digit number, exp (n^0 = 0) is passed.    countSort(arr, n, 1);     \/\/ Do counting sort for second digit in base n. Note that    \/\/ instead of passing digit number, exp (n^1 = n) is passed.    countSort(arr, n, n);} \/\/ A utility function to print an arrayvoid printArr(int arr[], int n){    for (int i = 0; i < n; i++)        cout << arr[i] << " ";} \/\/ Driver program to test above functionsint main(){    \/\/ Since array size is 7, elements should be from 0 to 48    int arr[] = {40, 12, 45, 32, 33, 1, 22};    int n = sizeof(arr)\/sizeof(arr[0]);    cout << "Given array is \\n";    printArr(arr, n);     sort(arr, n);     cout << "\\nSorted array is \\n";    printArr(arr, n);    return 0;}<\/code><\/pre> <\/div>\n
JAVA<\/strong><\/p>\n
 
 JAVA<\/span> <\/div> 
\/ Java program to sort an array of size n where elements are\/\/ in range from 0 to n^2 \u2013 1.class Sort1ToN2{    \/\/ 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[] = new int[n]; \/\/ output array        int i, count[] = new int[n] ;        for (i=0; i < n; i++)           count[i] = 0;         \/\/ Store count of occurrences in count[]        for (i = 0; i < n; i++)            count[ (arr[i]\/exp)%n ]++;         \/\/ Change count[i] so that count[i] now contains actual        \/\/ position of this digit in output[]        for (i = 1; i < n; i++)            count[i] += count[i - 1];         \/\/ Build the output array        for (i = n - 1; i >= 0; i--)        {            output[count[ (arr[i]\/exp)%n] - 1] = arr[i];            count[(arr[i]\/exp)%n]--;        }         \/\/ 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    void sort(int arr[], int n)    {        \/\/ Do counting sort for first digit in base n. Note that        \/\/ instead of passing digit number, exp (n^0 = 0) is passed.        countSort(arr, n, 1);         \/\/ Do counting sort for second digit in base n. Note that        \/\/ instead of passing digit number, exp (n^1 = n) is passed.        countSort(arr, n, n);    }     \/\/ A utility function to print an array    void printArr(int arr[], int n)    {        for (int i = 0; i < n; i++)            System.out.print(arr[i]+" ");    }     \/\/ Driver program to test above functions    public static void main(String args[])    {        Sort1ToN2 ob = new Sort1ToN2();         \/\/ Since array size is 7, elements should be from 0 to 48        int arr[] = {40, 12, 45, 32, 33, 1, 22};        int n = arr.length;        System.out.println("Given array");        ob.printArr(arr, n);         ob.sort(arr, n);         System.out.println("Sorted array");        ob.printArr(arr, n);    }}<\/code><\/pre> <\/div>\n
Output:<\/strong><\/p>\n
Given array is\r\n40 12 45 32 33 1 22\r\nSorted array is\r\n1 12 22 32 33 40 45<\/pre>\n
How to sort if range is from 1 to n2<\/sup>?<\/strong>
\nIf range is from 1 to n n2<\/sup>, the above process can not be directly applied, it must be changed. Consider n = 100 and range from 1 to 10000. Since the base is 100, a digit must be from 0 to 99 and there should be 2 digits in the numbers. But the number 10000 has more than 2 digits. So to sort numbers in a range from 1 to n2<\/sup>, we can use following process.
\n1) Subtract all numbers by 1.
\n2) Since the range is now 0 to n2<\/sup>, do counting sort twice as done in the above implementation.
\n3) After the elements are sorted, add 1 to all numbers to obtain the original numbers.<\/p>\n
How to sort if range is from 0 to n^3 -1?<\/strong>
\nSince there can be 3 digits in base n, we need to call counting sort 3 times.<\/p>\n[ad type=”banner”]\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
Sort n numbers in range from 0 to n^2 \u2013 1 in linear time – Searching and sorting – If we use Counting Sort, it would take O(n^2) time as the given range is of size n^2. Using any comparison based sorting like Merge Sort, Heap Sort, .. etc would take O(nLogn) time.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,71670,83513],"tags":[],"class_list":["post-25247","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-searching-and-sorting","category-sort-n-numbers"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25247","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=25247"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25247\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25247"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25247"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25247"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}