# Sort elements of matrix

• MHB
• evinda
So the total complexity is $O(1)+O(n)+O(n) = O(n)$.Hope this helps!In summary, we can use the given hint to create an algorithm that sorts a matrix of size n in O(n) complexity. This involves creating a count array with 101 elements, where each index corresponds to an element in the input matrix. The count array is then used to count the number of times each element appears in the matrix. Finally, a new matrix is filled with the elements in ascending order according to the count array, resulting in a sorted matrix. The complexity is O(1) + O(n) + O(n) = O(n).

#### evinda

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

## 1. How do I sort elements of a matrix in ascending order?

To sort the elements of a matrix in ascending order, you can use the built-in sort() function in most programming languages. This function takes in the matrix as an input and returns a sorted version of the matrix.

## 2. Can I sort elements of a matrix in descending order?

Yes, you can sort elements of a matrix in descending order by using the sort() function and passing in the reverse=True argument. This will sort the elements in descending order instead of ascending order.

## 3. Is there a specific algorithm for sorting elements of a matrix?

There are various algorithms that can be used to sort elements of a matrix, such as bubble sort, selection sort, and merge sort. The choice of algorithm may depend on the size and complexity of the matrix.

## 4. How can I sort specific rows or columns of a matrix?

To sort specific rows or columns of a matrix, you can use the built-in slicing function in most programming languages. This allows you to specify the range of rows or columns you want to sort and then use the sort() function on that subset of the matrix.

## 5. Can I sort a matrix based on a specific element or condition?

Yes, you can sort a matrix based on a specific element or condition by using a custom sorting function. This function can take in the matrix as an input and use conditional statements to determine the sorting order based on the given element or condition.