In this article, we will learn different ways to sort a two dimensional (2D) array.
Sort all elements of a 2D Array
In this section, we discuss how to sort all the elements of the 2D array such that all the elements in a row are in increasing order and the first element of any row is greater than the last element of the previous row.
For example,
Input 4 5 8 1 6 7 5 2 1 1 0 9 9 2 2 3 Output 0 1 1 1 2 2 2 3 4 5 5 6 7 8 9 9
Let N and M be the number of rows and number of columns of the 2D array.
We sort the 2D array as if it is a 1D array of size N*M. Every 1D array can be mapped to a 2D array. Let X be the index of the 1D array in the range [0, N*M-1]. The corresponding row number and column number of the 2D array is given by
Row Number = X/M Column Number = X%M
#include<stdio.h>
// bubble sort to sort 2D array
// sort 2D array as if it is a 1D array of size n*m
void sort(int arr[][20], int n, int m) {
int i, j, temp;
for (i = 0; i < n * m - 1; ++i) {
for (j = 0; j < n * m - 1 - i; ++j) {
// row = j/m
// column = j%m
if (arr[j / m][j % m] > arr[(j + 1) / m][(j + 1) % m]) {
temp = arr[(j + 1) / m][(j + 1) % m];
arr[(j + 1) / m][(j + 1) % m] = arr[j / m][j % m];
arr[j / m][j % m] = temp;
}
}
}
}
void display(int arr[][20], int n, int m) {
int i, j;
for (i = 0; i < n; ++i) {
for (j = 0; j < m; ++j) {
printf("%d ", arr[i][j]);
}
printf("\n");
}
}
int main()
{
int n, m;
int i, j;
int arr[20][20];
printf("Enter Number of Rows: ");
scanf("%d", &n);
printf("Enter Number of Columns: ");
scanf("%d", &m);
printf("Enter Array Elements\n");
for (i = 0; i < n; ++i) {
for (j = 0; j < m; ++j) {
scanf("%d", &arr[i][j]);
}
}
sort(arr, n, m);
printf("\nArray After Sorting: ");
display(arr, n, m);
}
Time Complexity: O(N*M)
Space Complexity: O(1)
Sort 2D array column wise (by column)
In this section, we discuss how to sort all columns of a 2D array.
For Example,
Input 4 5 6 1 8 7 5 2 1 3 0 9 7 2 2 3 Output 1 2 0 1 4 3 2 2 7 5 5 3 8 7 6 9
- Traverse each column of the 2D array.
- Let K the current column number.
- Apply bubble sort on all elements of the Kth column.
#include<stdio.h>
// bubble sort to sort each column of the 2D array
void sort(int arr[][20], int n, int m) {
int i, j, k, temp;
for (int k = 0; k < m; ++k) {
// sorting kth column of 2D array
for (i = 0; i < n; ++i) {
for (j = 0; j < n - 1 - i; ++j) {
if (arr[j][k] > arr[j + 1][k]) {
temp = arr[j + 1][k];
arr[j + 1][k] = arr[j][k];
arr[j][k] = temp;
}
}
}
}
}
void display(int arr[][20], int n, int m) {
int i, j;
for (i = 0; i < n; ++i) {
for (j = 0; j < m; ++j) {
printf("%d ", arr[i][j]);
}
printf("\n");
}
}
int main()
{
int n, m;
int i, j;
int arr[20][20];
printf("Enter Number of Rows: ");
scanf("%d", &n);
printf("Enter Number of Columns: ");
scanf("%d", &m);
printf("Enter Array Elements\n");
for (i = 0; i < n; ++i) {
for (j = 0; j < m; ++j) {
scanf("%d", &arr[i][j]);
}
}
sort(arr, n, m);
printf("\nArray After Sorting Column wise: \n");
display(arr, n, m);
}
Sort 2D array row wise (by row)
In this section, we will discuss how to sort all rows of a 2D array.
For Example,
Input 4 5 6 1 8 7 5 2 1 3 0 9 7 2 2 3 Output 1 4 5 6 2 5 7 8 0 1 3 9 2 2 3 7
- Traverse each row of the 2D array.
- Let K the current row number.
- Apply bubble sort on all elements of the Kth row.
#include<stdio.h>
// bubble sort to sort each column of the 2D array
void sort(int arr[][20], int n, int m){
int i,j,k,temp;
for(int k=0;k<n;++k){
// applying bubble sort on kth row
for(i=0;i<m;++i){
for(j=0;j<m-1-i;++j){
if(arr[k][j]>arr[k][j+1]){
temp = arr[k][j+1];
arr[k][j+1] = arr[k][j];
arr[k][j] = temp;
}
}
}
}
}
void display(int arr[][20],int n,int m){
int i,j;
for(i=0;i<n;++i){
for(j=0;j<m;++j){
printf("%d ",arr[i][j]);
}
printf("\n");
}
}
int main()
{
int n,m;
int i,j;
int arr[20][20];
printf("Enter Number of Rows: ");
scanf("%d",&n);
printf("Enter Number of Columns: ");
scanf("%d",&m);
printf("Enter Array Elements\n");
for(i=0;i<n;++i){
for(j=0;j<m;++j){
scanf("%d",&arr[i][j]);
}
}
sort(arr,n,m);
printf("\nArray After Sorting Row-wise: \n");
display(arr,n,m);
}
Sort one column of a 2D array
For example,
Input 4 5 6 1 8 7 5 2 1 3 0 9 7 2 2 3 Column = 1 Output 4 2 6 1 8 3 5 2 1 5 0 9 7 7 2 3
To sort the Kth column. We fix the column number to K and use bubble sort on all the elements of the Kth column.
#include<stdio.h>
// bubble sort to sort kth column of 2D array
void sort(int arr[][20], int n, int m, int k) {
int i, j, temp;
// applying bubble sort on kth column
for (i = 0; i < n; ++i) {
for (j = 0; j < n - 1 - i; ++j) {
if (arr[j][k] > arr[j + 1][k]) {
temp = arr[j + 1][k];
arr[j + 1][k] = arr[j][k];
arr[j][k] = temp;
}
}
}
}
void display(int arr[][20], int n, int m) {
int i, j;
for (i = 0; i < n; ++i) {
for (j = 0; j < m; ++j) {
printf("%d ", arr[i][j]);
}
printf("\n");
}
}
int main()
{
int n, m;
int i, j, k;
int arr[20][20];
printf("Enter Number of Rows: ");
scanf("%d", &n);
printf("Enter Number of Columns: ");
scanf("%d", &m);
printf("Enter Array Elements\n");
for (i = 0; i < n; ++i) {
for (j = 0; j < m; ++j) {
scanf("%d", &arr[i][j]);
}
}
printf("\nInput the Column You Want to Sort: ");
scanf("%d", &k);
sort(arr, n, m, k);
printf("\nArray After Sorting %dth column : \n", k);
display(arr, n, m);
}
Sort one row of a 2D array
For example,
Input 1 9 6 4 8 7 9 3 4 2 0 5 7 3 3 2 Row = 2 Output 1 9 6 4 8 7 9 3 0 2 4 5 7 3 3 2
Suppose we want to sort Kth row. We fix the row number to K and use bubble sort on all the elements of the Kth row.
#include<stdio.h>
// bubble sort to sort kth row of 2D array
void sort(int arr[][20], int n, int m, int k) {
int i, j, temp;
// applying bubble sort on kth row
for (i = 0; i < m; ++i) {
for (j = 0; j < m - 1 - i; ++j) {
if (arr[k][j] > arr[k][j + 1]) {
temp = arr[k][j + 1];
arr[k][j + 1] = arr[k][j];
arr[k][j] = temp;
}
}
}
}
void display(int arr[][20], int n, int m) {
int i, j;
for (i = 0; i < n; ++i) {
for (j = 0; j < m; ++j) {
printf("%d ", arr[i][j]);
}
printf("\n");
}
}
int main()
{
int n, m;
int i, j, k;
int arr[20][20];
printf("Enter Number of Rows: ");
scanf("%d", &n);
printf("Enter Number of Columns: ");
scanf("%d", &m);
printf("Enter Array Elements\n");
for (i = 0; i < n; ++i) {
for (j = 0; j < m; ++j) {
scanf("%d", &arr[i][j]);
}
}
printf("\nInput the Row You Want to Sort: ");
scanf("%d", &k);
sort(arr, n, m, k);
printf("\nArray After Sorting %dth row : \n", k);
display(arr, n, m);
}
