Как отсортировать двумерный массив

4. Сортировка двумерных массивов

Пусть a [ M ][ N ] – некоторая матрица. На множестве строк данной матрицы ( a [0], a [1],…, a [ M -1]) определим числовую функцию F . Например, функция F может возвращать значение первого элемента строки ( F ( a [ i ]) = a [ i ][0]), сумму элементов строки ( F ( a [ i ]) = a [ i ][0] + a [ i ][1] + … + a [ i ][ N -1]) и т.д. Задача состоит в том, чтобы упорядочить строки матрицы таким образом, чтобы последовательность F ( b [0]), F ( b [1]),…, F ( b [ M -1]) была неубывающей, где символом b обозначена новая матрица, полученная из матрицы a путем перестановки строк.

Для решения данной задачи имеется несколько подходов. Вопервых, можно действительно переставлять строки матрицы a , но для матриц с большим значением числа N (число столбцов) это неэффективно. Во-вторых, можно завести массив индексов int ind[M] = <0, 1,…, M-1>и переставлять в нем элементы таким образом, что-

бы последовательность F ( a [ind[0]]), F ( a [ind[1]]),…, F ( a [ind[ M -1]])

удовлетворяла условию задачи. При этом матрица a останется без изменений, а обращение к “новой” матрице b будет происходить следующим образом:

a [ind[ i ]][ j ], 0 ≤ i < M , 0 ≤ j < N .

Такой подход для одномерных массивов мы уже рассматривали выше. Поэтому (для разнообразия) остановимся на третьем подхо-

де (сопряженным со вторым), который заключается в рассмотрении дополнительного массива указателей int * pa [ M ], где pa [ i ] содержит адрес i -ой строки матрицы a , i = 0,…, M -1.

Изначально массив pa инициализируется следующим обра-

for(i = 0; i < M; i++) pa[i] = a[i];

Затем с помощью алгоритма быстрой сортировки происходит преобразование массива указателей pa так, чтобы последовательность F ( pa [0]), F ( pa [1]),…, F ( pa [ M -1]) удовлетворяла начальному условию. В алгоритме ниже в качестве функции F выступает функция, которая возвращает первый элемент строки. Поэтому вместо записи F ( pa [ i ]) будем использовать запись * pa [ i ].

#define M 5 /* Число строк матрицы */ #define N 10 /* Число столбцов матрицы */

/* вывод матрицы на экран через массив индексов pa */ void Print(int *pa[], int m, int n)

for (i = 0; i < m; i++)

for (j = 0; j < n; j++) printf(«%5d», pa[i][j]);

/* сортировка массива pa по первым элементам массива a: */ void QuickSort (int *pa[], int left, int right)

Сортировка пузырьком

И дея алгоритма очень простая. Идём по массиву чисел и проверяем порядок (следующее число должно быть больше и равно предыдущему), как только наткнулись на нарушение порядка, тут же обмениваем местами элементы, доходим до конца массива, после чего начинаем сначала.

Отсортируем массив <1, 5, 2, 7, 6, 3>
Идём по массиву, проверяем первое число и второе, они идут в порядке возрастания. Далее идёт нарушение порядка, меняем местами эти элементы
1, 2, 5, 7, 6, 3
Продолжаем идти по массиву, 7 больше 5, а вот 6 меньше, так что обмениваем из местами
1, 2, 5, 6, 7, 3
3 нарушает порядок, меняем местами с 7
1, 2, 5, 6, 3, 7
Возвращаемся к началу массива и проделываем то же самое

1, 2, 5, 3, 6, 7
1, 2, 3, 5, 6, 7

Говорят, что это похоже на «всплытие» более «лёгких» элементов, как пузырьков, отчего алгоритм и получил такое название.

Этот алгоритм всегда будет делать (n-1) 2 шагов, независимо от входных данных. Даже если массив отсортирован, всё равно он будет пройден (n-1) 2 раз. Более того, будут в очередной раз проверены уже отсортированные данные.

Пусть нужно отсортировать массив 1, 2, 4, 3

1 2 4 3
1 2 4 3
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4

После того, как были поменяны местами элемента a[2] и a[3] нет больше необходимости проходить этот участок массива. Примем это во внимание и переделаем алгоритм

Ещё одна реализация

В данном случае будет уже вполовину меньше шагов, но всё равно остаётся проблема сортировки уже отсортированного массива: нужно сделать так, чтобы отсортированный массив функция просматривала один раз. Для этого введём переменную-флаг: он будет опущен (flag = 0), если массив отсортирован. Как только мы наткнёмся на нарушение порядка, то флаг будет поднят (flag = 1) и мы начнём сортировать массив как обычно.

В этом случае сложность также порядка n 2 , но в случае отсортированного массива будет всего один проход.

Теперь усовершенствуем алгоритм. Напишем функцию общего вида, чтобы она сортировала массив типа void. Так как тип переменной не известен, то нужно будет дополнительно передавать размер одного элемента массива и функцию сравнения.

Функция выглядит некрасиво – часто вычисляется адрес текущего и предыдущего элемента. Выделим отдельные переменные для этого.

Теперь с помощью этих функций можно сортировать массивы любого типа, например

Сортировка многомерного массива

С ортировка статического многомерного массива по существу не отличается от сортировки одномерного. Можно воспользоваться тем свойством, что статический одномерный и многомерный массивы имеют одинаковое представление в памяти.

Сортировка динамически созданного двумерного массива может быть произведена двумя способами. Во-первых, можно по определённому алгоритму находить индекс i-го и j-го элемента по порядковому номеру k от 0 до n * m.

Во-вторых, можно сначала переместить массив в одномерный, отсортировать одномерный массив, после чего переместить его обратно в двумерный.

Если вас смущает эта функция, то воспользуйтесь типизированной. Вызов, из предыдущего примера

Всё ещё не понятно? – пиши вопросы на ящик

Алгоритмы сортировки на Java с примерами

В одной из предыдущих статей мы разобрались, где применяются алгоритмы сортировки, а теперь поговорим об их реализации на Java. Помните, что разные алгоритмы оптимальны для разных наборов и типов данных. В нашей статье мы рассмотрим наиболее «ходовые».

Алгоритм сортировки пузырьком на Java

Сортировка пузырьком (Bubble Sort) — это один из наиболее известных алгоритмов, суть которого состоит в последовательном сравнении двух соседних элементов. В том случае, если предыдущий элемент больше последующего, они меняются местами.

Так выглядит сортировка пузырьком на Java:

Объяснение

Как видим из кода, метод bubbleSort() принимает массив в качестве входных данных для сортировки — sortArr . Далее мы создаём внешний цикл for , который перебирает каждый элемент массива, тогда как внутренний цикл for начинается с первого элемента массива до предпоследнего индекса: sortArr.length — i — 1 . С помощью условия if мы проверяем, больше ли элемент слева элемента справа или нет. Если элемент слева действительно больше, он меняется местами с правым элементом.

Примечание Внешний цикл for будет перебирать все элементы массива, даже если массив уже полностью отсортирован.

Массив, который принимает метод bubbleSort() , может быть любым. В нашем примере мы передаём значения 12, 6, 4, 1, 15, 10 .

Сложность алгоритма: О(n2)

А ниже представлен алгоритм сортировки двумерного массива Java пузырьком:

Алгоритм быстрой сортировки на Java

Быстрая сортировка, также известная как Quick Sort или сортировка Хоара, является одним их самых эффективных алгоритмов. Она включает в себя три этапа:

Из массива выбирается опорный элемент, чаще всего посередине массива.
Другие элементы массива распределяются таким образом, чтобы меньшие размещались до него, а большие — после.
Далее первые шаги рекурсивно применяются к подмассивам, которые разделились опорным элементом на две части — слева и справа от него.

Пример быстрой сортировки на языке Java:

Сложность алгоритма: O(n log n)

Алгоритм сортировки слиянием на Java

Данный алгоритм разбивает список на две части, каждую из них он разбивает ещё на две и так далее, пока не останутся единичные элементы. Массив из одного элемента считается упорядоченным. Соседние элементы сравниваются и соединяются вместе. Так происходит до тех пор, пока все элементы не будут отсортированы.

Примечание По возможности используйте готовые алгоритмы для коллекций и методы из java.util.Arrays .

Реализовать алгоритм сортировки слиянием на Java можно так:

Объяснение

Сортировка осуществляется путём сравнения наименьших элементов каждого подмассива. Первые элементы каждого подмассива сравниваются первыми. Наименьший элемент перемещается в результирующий массив. Счётчики результирующего массива и подмассива, откуда был взят элемент, увеличиваются на один.

Сложность алгоритма: O(n log n)

Алгоритм сортировки вставками на Java

Это простая сортировка, при которой массив постепенно перебирается слева направо. При этом элемент сравнивается со всеми предыдущими элементами и размещается так, чтобы оказаться в подходящем месте среди ранее упорядоченных элементов. Так происходит до тех пор, пока набор входных данных не будет исчерпан.

Так выглядит сортировка вставками на Java:

Объяснение

Предполагается, что первый элемент списка отсортирован. Переходим к следующему элементу, обозначим его i . Если х больше первого, оставляем его на своём месте. Если он меньше, копируем его на вторую позицию, а i устанавливаем в качестве первого элемента.

Переходя к другим элементам несортированного сегмента, перемещаем более крупные элементы в отсортированном сегменте вверх по списку, пока не встретим элемент меньше i или не дойдём до конца списка. В первом случае i помещается на правильную позицию.

Сложность алгоритма: О(n2) для сравнений и перестановок.

Алгоритм сортировки выбором на Java

Разбиваем массив на отсортированную и неотсортированную части.
Находим в неотсортированной части минимальный элемент.
Меняем его местами с тем элементом, который находится на нулевой позиции —
в конец отсортированного массива.
Далее находим следующий по величине элемент и меняем его с элементом на первой позиции, etc., пока не закончатся неотсортированные значения.

Реализация сортировки выбором на языке программирования Java:

Сложность алгоритма: О(n2)

Алгоритм пирамидальной сортировки на Java

Чтобы реализовать алгоритм пирамидальной сортировки (Heapsort) на Java, нужно сперва понять принцип. Алгоритм сегментирует массив на отсортированный и неотсортированный. Неотсортированный сегмент преобразовывается в кучу (heap), что позволяет эффективно эффективно определить самый большой элемент.

Пирамидальная сортировка на Java с использованием класса java.util.Arrays :

Сложность алгоритма: O(n log n)

Объяснение алгоритмов сортировки с примерами на Python

Встроенные функции сортировки Java

Рассмотрим метод sort() классов Collections и Arrays , а также структуры данных вроде TreeMap и TreeSet .

Как использовать метод sort() в Java?

Метод Collections.sort() для сортировки коллекций:

И метод Arrays.sort() для сортировки массивов:

Метод sort() удобно использовать в том случае, если массив или коллекция заблаговременно заполнены значениями.

Структуры данных

TreeMap и TreeSet

Для сортировки списков List и множеств Set следует использовать структуру TreeSet :

Если же речь идёт о коллекции пар ключ/значение Map , для сортировки подойдёт структура TreeMap , которая сортируется по ключу:

Самосортируемые структуры данных имеют эффективность O(log(n)) , а значит при удвоении количества данных в коллекции время поиска не удваивается, а увеличивается на постоянную величину.