# Sort elements of matrix

• MHB
Gold Member
MHB
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:

Code:
int matrix
int count
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)

Last edited:

Gold Member
MHB
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:

Code:
int matrix
int count
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 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:
Code:
int matrix[n]
int count
int new_matrix[n]

The first loop will then become:
Code:
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:

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

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

You can then fill the output matrix as:

Code:
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)$.