В мире программирования и алгоритмов, сортировка является фундаментальной операцией, позволяющей упорядочивать данные для более эффективного поиска, обработки и анализа. Сортировка двумерных массивов представляет собой интересную задачу, поскольку в таких массивах данные организованы в виде таблицы, и нам часто нужно сортировать элементы как по строкам, так и по столбцам. В этой статье мы рассмотрим программы сортировки двумерного массива.
Теория
Сортировка двумерного массива может быть выполнена различными способами в зависимости от ваших требований. Вот алгоритм сортировки двумерного массива по одному из возможных критериев: по строкам, начиная с верхнего левого угла и двигаясь вниз и вправо.
- Преобразуйте двумерный массив в одномерный массив. Это можно сделать, перебирая строки и столбцы и сохраняя элементы в одномерный массив.
- Отсортируйте одномерный массив с использованием любого известного алгоритма сортировки, такого как сортировка пузырьком, сортировка вставками, сортировка слиянием или быстрая сортировка. Выбор алгоритма зависит от ваших требований к скорости и эффективности сортировки.
- После завершения сортировки, восстановите значения в исходном двумерном массиве из отсортированного одномерного массива. Это можно сделать, перебирая строки и столбцы и извлекая элементы из одномерного массива в соответствии с их новыми позициями.
C++
Сортировка двумерного массива с левого верхнего угла до правого нижнего угла означает упорядочивание элементов массива в порядке возрастания или убывания, начиная с верхнего левого элемента и двигаясь вниз и вправо. Пример программы на C++, которая сортирует двумерный массив:
#include <iostream>
#include <algorithm>
const int rows = 3; // Количество строк массива
const int cols = 4; // Количество столбцов массива
void printArray(int arr[rows][cols]) {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
std::cout << arr[i][j] << " ";
}
std::cout << std::endl;
}
}
int main() {
int arr[rows][cols] = {
{9, 5, 1, 8},
{4, 7, 2, 6},
{3, 2, 1, 5}
};
std::cout << "Исходный массив:" << std::endl;
printArray(arr);
// Преобразуем двумерный массив в одномерный для сортировки
int tempArray[rows * cols];
int index = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
tempArray[index] = arr[i][j];
index++;
}
}
// Сортировка одномерного массива
std::sort(tempArray, tempArray + rows * cols);
// Восстанавливаем отсортированные значения в двумерном массиве
index = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
arr[i][j] = tempArray[index];
index++;
}
}
std::cout << "Массив после сортировки:" << std::endl;
printArray(arr);
return 0;
}
В этой программе сначала определяется двумерный массив arr, а затем он преобразуется в одномерный массив tempArray, который сортируется с использованием std::sort(). После сортировки отсортированные значения восстанавливаются в исходном двумерном массиве arr.
C#
using System;
class Program
{
static void Main()
{
int rows = 3;
int cols = 4;
int[,] arr = {
{9, 5, 1, 8},
{4, 7, 2, 6},
{3, 2, 1, 5}
};
Console.WriteLine("Исходный массив:");
PrintArray(arr);
// Преобразуем двумерный массив в одномерный для сортировки
int[] tempArray = new int[rows * cols];
int index = 0;
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
tempArray[index] = arr[i, j];
index++;
}
}
// Сортировка одномерного массива
Array.Sort(tempArray);
// Восстанавливаем отсортированные значения в двумерном массиве
index = 0;
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
arr[i, j] = tempArray[index];
index++;
}
}
Console.WriteLine("Массив после сортировки:");
PrintArray(arr);
}
static void PrintArray(int[,] arr)
{
int rows = arr.GetLength(0);
int cols = arr.GetLength(1);
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
Console.Write(arr[i, j] + " ");
}
Console.WriteLine();
}
}
}
Этот код начинается с определения двумерного массива arr, который содержит исходные данные. Затем массив преобразуется в одномерный массив tempArray, сортируется, и отсортированные значения восстанавливаются в исходном двумерном массиве arr.
Python
def print_array(arr):
for row in arr:
for element in row:
print(element, end=" ")
print()
def sort_2d_array(arr):
flat_array = [element for row in arr for element in row]
flat_array.sort()
rows = len(arr)
cols = len(arr[0])
for i in range(rows):
for j in range(cols):
arr[i][j] = flat_array.pop(0)
if __name__ == "__main__":
rows = 3
cols = 4
arr = [
[9, 5, 1, 8],
[4, 7, 2, 6],
[3, 2, 1, 5]
]
print("Исходный массив:")
print_array(arr)
sort_2d_array(arr)
print("Массив после сортировки:")
print_array(arr)
Этот код сначала определяет функцию print_array(), которая выводит двумерный массив, и функцию sort_2d_array(), которая сначала преобразует двумерный массив в одномерный, сортирует его, а затем восстанавливает отсортированные значения в исходном двумерном массиве.
Затем, в блоке if __name__ == «__main__», определяются исходные данные, массив сортируется, и отсортированный результат выводится на экран.
Java
public class TwoDArraySorting {
public static void main(String[] args) {
int rows = 3;
int cols = 4;
int[][] arr = {
{9, 5, 1, 8},
{4, 7, 2, 6},
{3, 2, 1, 5}
};
System.out.println("Исходный массив:");
printArray(arr);
sort2DArray(arr);
System.out.println("Массив после сортировки:");
printArray(arr);
}
public static void printArray(int[][] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[0].length; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
}
public static void sort2DArray(int[][] arr) {
int rows = arr.length;
int cols = arr[0].length;
// Преобразуем двумерный массив в одномерный для сортировки
int[] tempArray = new int[rows * cols];
int index = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
tempArray[index] = arr[i][j];
index++;
}
}
// Сортируем одномерный массив
java.util.Arrays.sort(tempArray);
// Восстанавливаем отсортированные значения в двумерном массиве
index = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
arr[i][j] = tempArray[index];
index++;
}
}
}
}
Этот код определяет функцию printArray(), которая выводит двумерный массив, и функцию sort2DArray(), которая сначала преобразует двумерный массив в одномерный, сортирует его, а затем восстанавливает отсортированные значения в исходном двумерном массиве.
Pascal
program TwoDArraySorting;
const
Rows = 3;
Cols = 4;
type
T2DArray = array[1..Rows, 1..Cols] of Integer;
var
arr: T2DArray;
procedure PrintArray(var arr: T2DArray);
var
i, j: Integer;
begin
for i := 1 to Rows do
begin
for j := 1 to Cols do
begin
Write(arr[i, j], ' ');
end;
Writeln;
end;
end;
procedure Sort2DArray(var arr: T2DArray);
var
tempArray: array[1..Rows * Cols] of Integer;
i, j, k: Integer;
begin
k := 1;
for i := 1 to Rows do
begin
for j := 1 to Cols do
begin
tempArray[k] := arr[i, j];
Inc(k);
end;
end;
// Сортировка одномерного массива
for i := 1 to Rows * Cols - 1 do
begin
for j := i + 1 to Rows * Cols do
begin
if tempArray[i] > tempArray[j] then
begin
// Обмен значений
k := tempArray[i];
tempArray[i] := tempArray[j];
tempArray[j] := k;
end;
end;
end;
// Восстанавливаем отсортированные значения в двумерном массиве
k := 1;
for i := 1 to Rows do
begin
for j := 1 to Cols do
begin
arr[i, j] := tempArray[k];
Inc(k);
end;
end;
end;
begin
// Исходный двумерный массив
arr[1, 1] := 9;
arr[1, 2] := 5;
arr[1, 3] := 1;
arr[1, 4] := 8;
arr[2, 1] := 4;
arr[2, 2] := 7;
arr[2, 3] := 2;
arr[2, 4] := 6;
arr[3, 1] := 3;
arr[3, 2] := 2;
arr[3, 3] := 1;
arr[3, 4] := 5;
Writeln('Исходный массив:');
PrintArray(arr);
Sort2DArray(arr);
Writeln('Массив после сортировки:');
PrintArray(arr);
end.
Этот код определяет двумерный массив arr и две процедуры: PrintArray, которая выводит двумерный массив, и Sort2DArray, которая сначала преобразует двумерный массив в одномерный, сортирует его, а затем восстанавливает отсортированные значения в исходном двумерном массиве.
JavaScript
function printArray(arr) {
for (let i = 0; i < arr.length; i++) {
console.log(arr[i].join(' '));
}
}
function sort2DArray(arr) {
const flatArray = arr.flat(); // Преобразуем двумерный массив в одномерный
flatArray.sort((a, b) => a - b); // Сортировка в порядке возрастания
let index = 0;
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr[i].length; j++) {
arr[i][j] = flatArray[index];
index++;
}
}
}
const rows = 3;
const cols = 4;
const arr = [
[9, 5, 1, 8],
[4, 7, 2, 6],
[3, 2, 1, 5]
];
console.log('Исходный массив:');
printArray(arr);
sort2DArray(arr);
console.log('Массив после сортировки:');
printArray(arr);
Этот код определяет две функции: printArray(), которая выводит двумерный массив, и sort2DArray(), которая сначала преобразует двумерный массив в одномерный, сортирует его в порядке возрастания и затем восстанавливает отсортированные значения в исходном двумерном массиве.
Затем, определяются исходные данные, массив сортируется, и отсортированный результат выводится на экран.
PHP
<?php
function printArray($arr) {
foreach ($arr as $row) {
echo implode(' ', $row) . "\n";
}
}
function sort2DArray(&$arr) {
$flatArray = array_merge(...$arr); // Преобразуем двумерный массив в одномерный
sort($flatArray); // Сортировка в порядке возрастания
$index = 0;
foreach ($arr as &$row) {
foreach ($row as &$value) {
$value = $flatArray[$index];
$index++;
}
}
}
$rows = 3;
$cols = 4;
$arr = array(
array(9, 5, 1, 8),
array(4, 7, 2, 6),
array(3, 2, 1, 5)
);
echo "Исходный массив:\n";
printArray($arr);
sort2DArray($arr);
echo "Массив после сортировки:\n";
printArray($arr);
?>
Этот код определяет две функции: printArray(), которая выводит двумерный массив, и sort2DArray(), которая сначала преобразует двумерный массив в одномерный, сортирует его в порядке возрастания, а затем восстанавливает отсортированные значения в исходном двумерном массиве.
(Пока оценок нет)
Загрузка...