{"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":"<p>Given an array of numbers of size n. It is also given that the array elements are in range from 0 to n<sup>2<\/sup>\u2013 1. Sort the given array in linear time.<span id=\"more-127333\"><\/span><\/p>\n<pre>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<p><em><strong>We strongly recommend to minimize the browser and try this yourself first.<\/strong><\/em><\/p>\n<p><strong>Solution:<\/strong> If we use <a href=\"http:\/\/www.geeksforgeeks.org\/counting-sort\/\" target=\"_blank\" rel=\"noopener noreferrer\">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<a href=\"http:\/\/geeksquiz.com\/merge-sort\/\" target=\"_blank\" rel=\"noopener noreferrer\"> Merge Sort<\/a>, <a href=\"http:\/\/geeksquiz.com\/heap-sort\/\" target=\"_blank\" rel=\"noopener noreferrer\">Heap Sort<\/a>, .. etc would take O(nLogn) time.<br \/>\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 n<sup>2<\/sup> \u2013 1?<br \/>\nThe idea is to use <a href=\"http:\/\/www.geeksforgeeks.org\/radix-sort\/\" target=\"_blank\" rel=\"noopener noreferrer\">Radix Sort<\/a>. Following is standard Radix Sort algorithm.<\/p>\n<pre>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<p>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 n<sup>2<\/sup>-1 is the maximum possible value, the value of d would be O(log<sub>b<\/sub>(n)). So overall time complexity is O((n+b)*O(log<sub>b<\/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(log<sub>b<\/sub>(n)) becomes O(1) and overall time complexity becomes O(n).<\/p>\n<pre>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[] = {0<u>0<\/u>(0), 2<u>0<\/u>(10), 1<u>2<\/u>(7), 2<u>2<\/u>(12), 2<u>3<\/u>(13)}\r\n\r\nAfter second iteration, we get\r\narr[] = {<u>0<\/u>0(0), <u>1<\/u>2(7), <u>2<\/u>0(10), <u>2<\/u>2(12), <u>2<\/u>3(13)}\r\n<\/pre>\n<p>Following is C++ implementation to sort an array of size n where elements are in range from 0 to n<sup>2<\/sup> \u2013 1.<\/p>\n[ad type=\u201dbanner\u201d]\n<p><strong>C++<\/strong><\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%23include%3Ciostream%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20A%20function%20to%20do%20counting%20sort%20of%20arr%5B%5D%20according%20to%0A%2F%2F%20the%20digit%20represented%20by%20exp.%0Aint%20countSort(int%20arr%5B%5D%2C%20int%20n%2C%20int%20exp)%0A%7B%0A%20%0A%20%20%20%20int%20output%5Bn%5D%3B%20%2F%2F%20output%20array%0A%20%20%20%20int%20i%2C%20count%5Bn%5D%20%3B%0A%20%20%20%20for%20(int%20i%3D0%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20count%5Bi%5D%20%3D%200%3B%0A%20%0A%20%20%20%20%2F%2F%20Store%20count%20of%20occurrences%20in%20count%5B%5D%0A%20%20%20%20for%20(i%20%3D%200%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20count%5B%20(arr%5Bi%5D%2Fexp)%25n%20%5D%2B%2B%3B%0A%20%0A%20%20%20%20%2F%2F%20Change%20count%5Bi%5D%20so%20that%20count%5Bi%5D%20now%20contains%20actual%0A%20%20%20%20%2F%2F%20position%20of%20this%20digit%20in%20output%5B%5D%0A%20%20%20%20for%20(i%20%3D%201%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20count%5Bi%5D%20%2B%3D%20count%5Bi%20-%201%5D%3B%0A%20%0A%20%20%20%20%2F%2F%20Build%20the%20output%20array%0A%20%20%20%20for%20(i%20%3D%20n%20-%201%3B%20i%20%3E%3D%200%3B%20i\u2013)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20output%5Bcount%5B%20(arr%5Bi%5D%2Fexp)%25n%5D%20-%201%5D%20%3D%20arr%5Bi%5D%3B%0A%20%20%20%20%20%20%20%20count%5B(arr%5Bi%5D%2Fexp)%25n%5D\u2013%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Copy%20the%20output%20array%20to%20arr%5B%5D%2C%20so%20that%20arr%5B%5D%20now%0A%20%20%20%20%2F%2F%20contains%20sorted%20numbers%20according%20to%20curent%20digit%0A%20%20%20%20for%20(i%20%3D%200%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20arr%5Bi%5D%20%3D%20output%5Bi%5D%3B%0A%7D%0A%20%0A%20%0A%2F%2F%20The%20main%20function%20to%20that%20sorts%20arr%5B%5D%20of%20size%20n%20using%20Radix%20Sort%0Avoid%20sort(int%20arr%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20%20%2F%2F%20Do%20counting%20sort%20for%20first%20digit%20in%20base%20n.%20Note%20that%0A%20%20%20%20%2F%2F%20instead%20of%20passing%20digit%20number%2C%20exp%20(n%5E0%20%3D%200)%20is%20passed.%0A%20%20%20%20countSort(arr%2C%20n%2C%201)%3B%0A%20%0A%20%20%20%20%2F%2F%20Do%20counting%20sort%20for%20second%20digit%20in%20base%20n.%20Note%20that%0A%20%20%20%20%2F%2F%20instead%20of%20passing%20digit%20number%2C%20exp%20(n%5E1%20%3D%20n)%20is%20passed.%0A%20%20%20%20countSort(arr%2C%20n%2C%20n)%3B%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20to%20print%20an%20array%0Avoid%20printArr(int%20arr%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20cout%20%3C%3C%20arr%5Bi%5D%20%3C%3C%20%22%20%22%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20%2F%2F%20Since%20array%20size%20is%207%2C%20elements%20should%20be%20from%200%20to%2048%0A%20%20%20%20int%20arr%5B%5D%20%3D%20%7B40%2C%2012%2C%2045%2C%2032%2C%2033%2C%201%2C%2022%7D%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%3B%0A%20%20%20%20cout%20%3C%3C%20%22Given%20array%20is%20%5Cn%22%3B%0A%20%20%20%20printArr(arr%2C%20n)%3B%0A%20%0A%20%20%20%20sort(arr%2C%20n)%3B%0A%20%0A%20%20%20%20cout%20%3C%3C%20%22%5CnSorted%20array%20is%20%5Cn%22%3B%0A%20%20%20%20printArr(arr%2C%20n)%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dc++\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>JAVA<\/strong><\/p>\n[pastacode lang=\u201djava\u201d manual=\u201d%2F%20Java%20program%20to%20sort%20an%20array%20of%20size%20n%20where%20elements%20are%0A%2F%2F%20in%20range%20from%200%20to%20n%5E2%20%E2%80%93%201.%0Aclass%20Sort1ToN2%0A%7B%0A%20%20%20%20%2F%2F%20A%20function%20to%20do%20counting%20sort%20of%20arr%5B%5D%20according%20to%0A%20%20%20%20%2F%2F%20the%20digit%20represented%20by%20exp.%0A%20%20%20%20void%20countSort(int%20arr%5B%5D%2C%20int%20n%2C%20int%20exp)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20output%5B%5D%20%3D%20new%20int%5Bn%5D%3B%20%2F%2F%20output%20array%0A%20%20%20%20%20%20%20%20int%20i%2C%20count%5B%5D%20%3D%20new%20int%5Bn%5D%20%3B%0A%20%20%20%20%20%20%20%20for%20(i%3D0%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20count%5Bi%5D%20%3D%200%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Store%20count%20of%20occurrences%20in%20count%5B%5D%0A%20%20%20%20%20%20%20%20for%20(i%20%3D%200%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20count%5B%20(arr%5Bi%5D%2Fexp)%25n%20%5D%2B%2B%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Change%20count%5Bi%5D%20so%20that%20count%5Bi%5D%20now%20contains%20actual%0A%20%20%20%20%20%20%20%20%2F%2F%20position%20of%20this%20digit%20in%20output%5B%5D%0A%20%20%20%20%20%20%20%20for%20(i%20%3D%201%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20count%5Bi%5D%20%2B%3D%20count%5Bi%20-%201%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Build%20the%20output%20array%0A%20%20%20%20%20%20%20%20for%20(i%20%3D%20n%20-%201%3B%20i%20%3E%3D%200%3B%20i\u2013)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20output%5Bcount%5B%20(arr%5Bi%5D%2Fexp)%25n%5D%20-%201%5D%20%3D%20arr%5Bi%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20count%5B(arr%5Bi%5D%2Fexp)%25n%5D\u2013%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Copy%20the%20output%20array%20to%20arr%5B%5D%2C%20so%20that%20arr%5B%5D%20now%0A%20%20%20%20%20%20%20%20%2F%2F%20contains%20sorted%20numbers%20according%20to%20curent%20digit%0A%20%20%20%20%20%20%20%20for%20(i%20%3D%200%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20arr%5Bi%5D%20%3D%20output%5Bi%5D%3B%0A%20%20%20%20%7D%0A%20%0A%20%0A%20%20%20%20%2F%2F%20The%20main%20function%20to%20that%20sorts%20arr%5B%5D%20of%20size%20n%20using%20Radix%20Sort%0A%20%20%20%20void%20sort(int%20arr%5B%5D%2C%20int%20n)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Do%20counting%20sort%20for%20first%20digit%20in%20base%20n.%20Note%20that%0A%20%20%20%20%20%20%20%20%2F%2F%20instead%20of%20passing%20digit%20number%2C%20exp%20(n%5E0%20%3D%200)%20is%20passed.%0A%20%20%20%20%20%20%20%20countSort(arr%2C%20n%2C%201)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Do%20counting%20sort%20for%20second%20digit%20in%20base%20n.%20Note%20that%0A%20%20%20%20%20%20%20%20%2F%2F%20instead%20of%20passing%20digit%20number%2C%20exp%20(n%5E1%20%3D%20n)%20is%20passed.%0A%20%20%20%20%20%20%20%20countSort(arr%2C%20n%2C%20n)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20A%20utility%20function%20to%20print%20an%20array%0A%20%20%20%20void%20printArr(int%20arr%5B%5D%2C%20int%20n)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.print(arr%5Bi%5D%2B%22%20%22)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Driver%20program%20to%20test%20above%20functions%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20Sort1ToN2%20ob%20%3D%20new%20Sort1ToN2()%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Since%20array%20size%20is%207%2C%20elements%20should%20be%20from%200%20to%2048%0A%20%20%20%20%20%20%20%20int%20arr%5B%5D%20%3D%20%7B40%2C%2012%2C%2045%2C%2032%2C%2033%2C%201%2C%2022%7D%3B%0A%20%20%20%20%20%20%20%20int%20n%20%3D%20arr.length%3B%0A%20%20%20%20%20%20%20%20System.out.println(%22Given%20array%22)%3B%0A%20%20%20%20%20%20%20%20ob.printArr(arr%2C%20n)%3B%0A%20%0A%20%20%20%20%20%20%20%20ob.sort(arr%2C%20n)%3B%0A%20%0A%20%20%20%20%20%20%20%20System.out.println(%22Sorted%20array%22)%3B%0A%20%20%20%20%20%20%20%20ob.printArr(arr%2C%20n)%3B%0A%20%20%20%20%7D%0A%7D\u201d message=\u201dJAVA\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Output:<\/strong><\/p>\n<pre>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<p><strong>How to sort if range is from 1 to n<sup>2<\/sup>?<\/strong><br \/>\nIf range is from 1 to n n<sup>2<\/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 n<sup>2<\/sup>, we can use following process.<br \/>\n1) Subtract all numbers by 1.<br \/>\n2) Since the range is now 0 to n<sup>2<\/sup>, do counting sort twice as done in the above implementation.<br \/>\n3) After the elements are sorted, add 1 to all numbers to obtain the original numbers.<\/p>\n<p><strong>How to sort if range is from 0 to n^3 -1?<\/strong><br \/>\nSince there can be 3 digits in base n, we need to call counting sort 3 times.<\/p>\n[ad type=\u201dbanner\u201d]\n<p>\u00a0<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Sort n numbers in range from 0 to n^2 \u2013 1 in linear time &#8211; Searching and sorting &#8211; 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}]}}