MHB How to Sort Elements of a Matrix in O(n) Time Complexity?

[evinda]

Hello! (Wave)

Let a matrix with $n$ integers in the interval $[1,100]$. I want to write an algorithm that sorts the elements of the matrix in $O(n)$. [Hint: Count and use the number of times that each number appears]

I have thought the following:

We create a matrix with $100$ entries. If the matrix contains for example 1 $1$ we put 1 at the first cell. I have written this as follows:

int matrix[100]
int count[100]
int new_matrix[n]

for i=0 to 99 
     count[i]=0
end
for i=0 to 99
     if matrix[i]=i+1
        then count[i]=count[i]+1
end
j=0
for i=0 to 99
     if (count[i] not 0)
        while (count[i] not 0)
                 new_matrix[j]=matrix[i]
                 j=j+1
                 count[i]=count[i]-1
         end
end
for (i=0 to j-1)
     print(new_matrix[i])
end

The first and second for are executed $100$ times and the third $100 \cdot j=100 \cdot n$ times, right?

So the complexity is $O(100)+O(100 \cdot n)=O(n)$.

Or have I done something wrong? (Thinking)

 

[castor28]

Hello! (Wave)

Let a matrix with $n$ integers in the interval $[1,100]$. I want to write an algorithm that sorts the elements of the matrix in $O(n)$. [Hint: Count and use the number of times that each number appears]

I have thought the following:

We create a matrix with $100$ entries. If the matrix contains for example 1 $1$ we put 1 at the first cell. I have written this as follows:

int matrix[100]
int count[100]
int new_matrix[n]

for i=0 to 99 
     count[i]=0
end
for i=0 to 99
     if matrix[i]=i+1
        then count[i]=count[i]+1
end
j=0
for i=0 to 99
     if (count[i] not 0)
        while (count[i] not 0)
                 new_matrix[j]=matrix[i]
                 j=j+1
                 count[i]=count[i]-1
         end
end
for (i=0 to j-1)
     print(new_matrix[i])
end

The first and second for are executed $100$ times and the third $100 \cdot j=100 \cdot n$ times, right?

So the complexity is $O(100)+O(100 \cdot n)=O(n)$.

Or have I done something wrong? (Thinking)

Hi evinda,

I see a few errors in what you did.

I understand that 'matrix' is the given matrix; its size should be $n$, not $100$.

I would suggest to make the count array 101 elements long, and leave count[0] unused. In this way, the index of the count array corresponds directly to the value of an element in the input matrix.

The declarations are then:

int matrix[n]
int count[101]
int new_matrix[n]

The first loop will then become:

for i = 1 to 100
  count[i] = 0

The second loop (that counts the elements) is not correct. You only update a count if matrix contains i+1. In fact, each element in the matrix should update one element of the count array. A more correct implementation would be:

for i = 0 to n
    count[matrix[i]] = count[matrix[i]]+1

where I assume that you have declared count as int[101] as explained above (this is only a minor detail, but it makes things less error-prone).

You can then fill the output matrix as:

j = 0
for i = 1 to 100
  while count[i] > 0
        new_matrix[j] = i
        j = j+1
        count[i]=count[i]-1

which is almost what you did, except that the value to be stored is i, not matrix. Note also that i ranges from 1 to 100 instead of 0 to 99, as per the reamrk above.

Now, the first loop (that clears the count array) will be executed $100$ times, which is $O(1)$.

The second loop (that counts the elements) will be executed $n$ times, which is $O(n)$.

In each execution of the final loop, one element of new_matrix will be assigned. As we do not loose any element (the total count is preserved), this loop will also execute in $O(n)$.