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[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)

Last edited:

Answers and Replies

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

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