Sort a 2D array in C++ using built in functions(or any other method)?
Categories:
Efficiently Sort 2D Arrays in C++
Learn various methods to sort 2D arrays (matrices) in C++, leveraging built-in functions and custom comparators for flexible sorting criteria.
Sorting a 2D array, also known as a matrix, is a common task in C++ programming. Unlike 1D arrays, 2D arrays introduce additional complexity due to their row and column structure. This article explores different techniques to sort 2D arrays, focusing on both row-wise and column-wise sorting, as well as sorting based on custom criteria. We'll cover the use of standard library functions like std::sort and how to implement custom comparison functions to achieve specific sorting orders.
Understanding 2D Array Representation
Before diving into sorting, it's crucial to understand how 2D arrays are typically represented in C++. They can be declared as fixed-size arrays, arrays of std::vectors, or a single std::vector of std::vectors. The latter, std::vector<std::vector<int>>, is often preferred for its dynamic sizing capabilities and ease of use with standard algorithms.
graph TD
A[2D Array Representation] --> B{Fixed-size Array}
A --> C{Array of Pointers}
A --> D{Vector of Vectors}
B --> B1["int arr[ROWS][COLS]"]
C --> C1["int** arr"]
D --> D1["std::vector<std::vector<int>> arr"]
D1 --> D2["Most flexible for sorting"]Common 2D array representations in C++
Sorting Rows of a 2D Array
The most straightforward sorting operation for a 2D array is to sort each individual row. This can be easily achieved by iterating through each row and applying std::sort to it. When using std::vector<std::vector<int>>, each inner std::vector can be treated as a 1D array for sorting purposes.
#include <iostream>
#include <vector>
#include <algorithm>
void print2DArray(const std::vector<std::vector<int>>& arr) {
for (const auto& row : arr) {
for (int val : row) {
std::cout << val << " ";
}
std::cout << std::endl;
}
}
int main() {
std::vector<std::vector<int>> matrix = {
{3, 1, 4},
{2, 5, 0},
{7, 6, 8}
};
std::cout << "Original Matrix:\n";
print2DArray(matrix);
// Sort each row
for (auto& row : matrix) {
std::sort(row.begin(), row.end());
}
std::cout << "\nMatrix after sorting each row:\n";
print2DArray(matrix);
return 0;
}
Sorting each row of a 2D std::vector.
Sorting the Entire 2D Array Based on Rows
To sort the entire 2D array based on the values of its rows, you can use std::sort directly on the outer std::vector of std::vectors. By default, std::vectors are compared lexicographically, meaning they are compared element by element from left to right. This allows for natural sorting of rows.
#include <iostream>
#include <vector>
#include <algorithm>
void print2DArray(const std::vector<std::vector<int>>& arr) {
for (const auto& row : arr) {
for (int val : row) {
std::cout << val << " ";
}
std::cout << std::endl;
}
}
int main() {
std::vector<std::vector<int>> matrix = {
{3, 1, 4},
{2, 5, 0},
{7, 6, 8},
{2, 1, 0} // Added for better demonstration of row sorting
};
std::cout << "Original Matrix:\n";
print2DArray(matrix);
// Sort the entire matrix based on rows (lexicographical comparison)
std::sort(matrix.begin(), matrix.end());
std::cout << "\nMatrix after sorting rows lexicographically:\n";
print2DArray(matrix);
return 0;
}
Sorting a 2D array by comparing rows lexicographically.
Custom Sorting Criteria for Rows
What if you need to sort rows based on a specific column, or a custom calculation involving elements within the row? std::sort allows you to provide a custom comparison function (a lambda expression or a functor) to define your sorting logic.
#include <iostream>
#include <vector>
#include <algorithm>
void print2DArray(const std::vector<std::vector<int>>& arr) {
for (const auto& row : arr) {
for (int val : row) {
std::cout << val << " ";
}
std::cout << std::endl;
}
}
int main() {
std::vector<std::vector<int>> matrix = {
{3, 1, 4},
{2, 5, 0},
{7, 6, 8},
{1, 9, 2}
};
std::cout << "Original Matrix:\n";
print2DArray(matrix);
// Sort rows based on the second element (index 1)
std::sort(matrix.begin(), matrix.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
return a[1] < b[1]; // Sort by second column in ascending order
});
std::cout << "\nMatrix after sorting by second column:\n";
print2DArray(matrix);
// Sort rows based on the sum of elements in descending order
std::sort(matrix.begin(), matrix.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
int sum_a = 0;
for (int x : a) sum_a += x;
int sum_b = 0;
for (int x : b) sum_b += x;
return sum_a > sum_b; // Sort by sum in descending order
});
std::cout << "\nMatrix after sorting by sum of elements (descending):\n";
print2DArray(matrix);
return 0;
}
Custom sorting of rows using lambda expressions.
Sorting Columns of a 2D Array
Sorting columns directly with std::sort is not as straightforward as sorting rows because std::sort operates on contiguous ranges. A 2D array's columns are not contiguous in memory. To sort columns, you typically need to either transpose the matrix, or implement a custom sorting logic that swaps elements across rows.
#include <iostream>
#include <vector>
#include <algorithm>
void print2DArray(const std::vector<std::vector<int>>& arr) {
for (const auto& row : arr) {
for (int val : row) {
std::cout << val << " ";
}
std::cout << std::endl;
}
}
// Function to sort a specific column
void sortColumn(std::vector<std::vector<int>>& matrix, int colIndex) {
// Create a vector of pairs: {value, original_row_index}
std::vector<std::pair<int, int>> column_elements;
for (int i = 0; i < matrix.size(); ++i) {
column_elements.push_back({matrix[i][colIndex], i});
}
// Sort these pairs based on the value
std::sort(column_elements.begin(), column_elements.end());
// Create a temporary matrix to store sorted rows
std::vector<std::vector<int>> sorted_matrix(matrix.size(), std::vector<int>(matrix[0].size()));
// Reconstruct the matrix based on the sorted column order
for (int i = 0; i < column_elements.size(); ++i) {
sorted_matrix[i] = matrix[column_elements[i].second];
}
matrix = sorted_matrix;
}
int main() {
std::vector<std::vector<int>> matrix = {
{3, 1, 4},
{2, 5, 0},
{7, 6, 8}
};
std::cout << "Original Matrix:\n";
print2DArray(matrix);
// Sort the matrix based on the first column (index 0)
sortColumn(matrix, 0);
std::cout << "\nMatrix after sorting by first column:\n";
print2DArray(matrix);
return 0;
}
Sorting a 2D array by a specific column.
sortColumn function achieves this by mapping original row indices to their new positions after sorting the column values.