0
$\begingroup$

I need to write a sorting algorithm which will sort an array $A[1..n]$, $1 \le i \le n$ such that $A[i] \in \{1,2,..,n^5 \}$, all numbers are positive integers in $\Theta (n)$ time.

The solution must use some combination of radix/counting/bucket sort and possibly select algorithm, it can't use any advanced concepts or structures.

I thought of the following:

0) Convert the numbers into base $n$.

1) Count how many digits each number of the array $A$ contains. We know that the number with max amount of digits will be $n^5$. It'll have $\lfloor{\log_b n^5} \rfloor +1= \lfloor 5\log_b n \rfloor+1$ digits, where $b$ is the base.Because we changed the base to $n$, there will be $\lfloor 5\log_n n \rfloor+1 =6$ unique digit lengths. Create an array countArray which will contain how many occurrences of tens, hundreds etc are.

2) Create subArrays which will contain numbers of the same amount of digits and run radix sort on each such subarray. Radix-Sort runs in $\Theta(d(n+b))$ in general and in our case it will become $\Theta(6(n+n)=\Theta(6n)=\Theta(n)$.

3) In the last step we copy the sorted subarrays into the output array.

Below is the pseudocode but I'm interested if my idea is correct and if the time complexity of my algorithm is $\Theta(n)$:

1 MySort(A, n)                    //A is the array, n is array length
2    uniqueDigitsNum <- 5log_n(n) + 1=6
3    init countArray             // the array of length uniqueDigitsNum
4    for i <- 0 to n             //O(n)
5        //B is a helper array which will store how many digits are in a given number
6        countDigits(A[i], B[i])
7        countArray[B[i]]++      //update the count of how many times we see x digits in CountArray
8    // init a 2d array which will contain uniqueDigitsNum subarrays
9    init subArrays of length uniqueDigitsNum  
10    for k <- 0 to uniqueDigitsNum  //O(6)
11        init subArrays[k] of length countArray[k]
12    for k <- 0 to uniqueDigitsNum  //O(6n)
13        Radix-Sort(subArrays[k])   //O(countArray[k])
14    //we'll need 'j' to know at which index to start copying the next subarray in the big output array
15    j <- 0                      
16    for k <- 0 to uniqueDigitsNum  //O(n)
17        for j to countArray[j]     //O(countArray[j])
18            outputArray[j] <- subArrays[k][j]
Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ What is the context where you encountered this question? Did it come from a textbook? Can you give a full citation? How do you know the problem is solvable? $\endgroup$
    – D.W. ♦
    Commented May 24, 2017 at 20:01
  • $\begingroup$ It's an exercise given in our algorithms class. It is solvable because otherwise they wouldn't give it to us and this is the full citation $\endgroup$
    – Yos
    Commented May 24, 2017 at 20:03
  • 2
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W. ♦
    Commented May 25, 2017 at 17:03
  • 1
    $\begingroup$ " I think it'd be appropriate for someone to post an answer which offers the correct solution or correction of my mistakes" -- It'd be helpful to you, but nobody else. Whether it's appropriate (or even legal) depends a lot on your ethics and the rules of your school. $\endgroup$
    – Raphael
    Commented Aug 23, 2017 at 11:29
  • 1
    $\begingroup$ For instance, TM vs RAM. If RAM, uniform or logarithmic cost model? Your task may be impossible in one and trivial in the other. You may want to peruse our reference questions. $\endgroup$
    – Raphael
    Commented Aug 23, 2017 at 11:34

1 Answer 1

Reset to default
1
$\begingroup$

  1. Radix sort for integers of arbitrary length has $\mathcal{O}(mn)$ time complexity, where m is the length of number.

  2. Count digits takes $\mathcal{O}(\log(n))$ time, so, your cycle will take at least (in worst case though) $\mathcal{O}(n \log(n))$ time which is the best possible for general case of sorting problem. Because to find complexity of 2-level cycle, you need to find complexity of subcycle and multiply them.

Of course, there exists an algorithm that can sort any array of numbers in $\mathcal{O}(n \log(n))$ time and $O(\log(n))$ space.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Actually I found a trick that we can convert the numbers to base $n$ which will allow us to achieve linear time complexity if my calculations are correct $\endgroup$
    – Yos
    Commented May 25, 2017 at 7:34
  • $\begingroup$ You have cycles where you show complexities O(n) and O(count digits) inside it. If you multiply them, it won't be linear. $\endgroup$
    – rus9384
    Commented May 25, 2017 at 12:23
  • $\begingroup$ Which line are you referring to? $\endgroup$
    – Yos
    Commented May 25, 2017 at 13:24
  • 1
    $\begingroup$ Line 6, you call that function $n$ times and itself it takes $O(log(n))$ time. $\endgroup$
    – rus9384
    Commented May 25, 2017 at 13:33
  • 1
    $\begingroup$ Why do you think that it's constant? If you'll take $n = 10^6$ you will receive a maximum number $n^5 = 10^{30}$ and it's length is 31 decimal digits (103 bits). If you'll convert that number into base $n$ it'll be represented as 5 24-bit strings. $\endgroup$
    – rus9384
    Commented May 25, 2017 at 14:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.