Sort Two Dimensional (2D) array

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);
}
sort all elements of the 2D array

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
  1. 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 by row

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
  1. 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);
}
sorting 2D array by column

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 given column of the 2D array

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);
}
sorting given row of the 2D array

Leave a Comment

Your email address will not be published. Required fields are marked *