Сортировка – это упорядочивание имеющегося массива однотипных данных по возрастанию или убыванию. Данная операция может быть реализована различными способами. При помощи сортировки удается значительно ускорять обработку информации.
Далее предстоит познакомиться с сортировкой массива слиянием. Это один из простейших и эффективнейших алгоритмов. Также вниманию будут представлены другие подходы к упорядочиванию элементов массива. Эта информация поможет понять разницу между алгоритмами и объяснит особенности подхода «слияние».
Краткая характеристика
Алгоритм сортировки слиянием – это один из самых эффективных подходов к сортировке массивов. Он обеспечивает стабильность процесса и его быструю реализацию.
Здесь, если два элемента массива (int) обладают одинаковыми значениями, они занимают то же относительное положение в отсортированной последовательности, что и во входных данных. В отсортированном множестве сохраняется относительный порядок составляющих с одинаковыми значениями. «Слияние» – это сортировка элементов массива (int) сравнением. Алгоритм является наглядным примером принципа «разделяй и властвуй».
Алгоритм работы
Сортировка слиянием делит заданный большой исходный массив на два меньших подмассива. После этого система рекурсивно сортирует подмассивы.
Выполняется рассматриваемый подход к упорядочиванию элементов массива (int) в несколько шагов:
- Исходный массив разбивается на две части. Они должны быть примерно одного и того же размера.
- Каждая часть сортируется отдельно.
- Два получившихся подмассива половинного размера соединяются в результирующий массив.
Рекурсивное дробление заданного массива осуществляется до тех пор, пока его размер не достигнет единицы. Такое множество можно рассматривать как упорядочивание.
Слияние получающихся в ходе реализации алгоритма осуществляется до тех пор, пока все элементы обоих подмассивов не будут объединены.
Выше можно увидеть наглядный пример упорядочивания массива из целочисленных (int) элементов. Всего в заданной цепочке 7 составляющих.
Преимущества и недостатки
Рассматриваемый подход к упорядочиванию массивов имеет как преимущества, так и недостатки. Зная их, программисты смогут понять, когда сортировка методом слияния будет наиболее эффективной.
К преимуществам соответствующего подхода можно отнести:
- Стабильность. Упорядочивание элементов массива (int) при помощи данного алгоритма – это поддержка относительного порядка равных компонентов во входном массиве.
- Производительность при наихудшем раскладе. Временная сложность алгоритма сортировки слиянием равняется O (N logN). Это значит, что работает соответствующий подход хорошо даже на больших наборах исходных данных.
- Простоту реализации. Метод «разделяй и властвуй» является достаточно простым и понятным. Освоить его сможет даже начинающий разработчик.
Сортировка слиянием также имеет некоторые недостатки. К ним относят следующие моменты:
- Пространственная сложность. Реализация рассматриваемого алгоритма требует дополнительной памяти. Она выделяется для хранения объединенных подмассивов в процессе работы метода.
- «Не на месте». Рассматриваемая концепция упорядочивания элементов массива (int) не является алгоритмом сортировки «на месте». Это значит, что для хранения отсортированных данных необходимо выделять дополнительную память. Для некоторых приложений соответствующий момент может стать настоящей проблемой.
Несмотря на некоторые недочеты, изучаемый алгоритм все равно остается распространенным и активно используемым на практике.
Области применения
Рассматриваемый алгоритм слияния массивов (int) рекомендуется использовать для определенных задач. К ним относят:
- упорядочивание элементов в больших информационных наборах;
- внешнюю сортировку – когда исходный набор данных слишком велик для размещения в памяти;
- подсчет инверсий;
- нахождение медианы заданного массива.
При работе с небольшими информационными наборами рекомендуется пользоваться другими методами упорядочивания. Они будут рассмотрены позже.
Пример на Java
Сортировка слиянием может быть реализована на разных языках программирования. Первый – это Java. Он активно используется как разработчиками-новичками, так и их более опытными коллегами.
Здесь необходимо написать функцию merge sort. Она будет принимать входной массив и его длину в качестве параметров. Данная функция является рекурсивной, поэтому требуется база и рекурсивные условия.
Базовое условие для работы рассматриваемой концепции: равна ли длина заданного массива целочисленных элементов (int) единице. Оно будет просто возвращаться. В остальных случаях будет выполняться рекурсивный вызов.
Для рекурсивного случая необходимо получить средний индекс и создать два временных массива (подмассива): l[] и r[]. Теперь рекурсивно осуществляется вызов функции merge sort для обоих подмассивов:
Теперь необходимо вызвать функцию слияния, которая принимает входные данные и оба подмассива, начальный и конечный индексы для обоих подмассивов.
Merge sort сравнит элементы обоих подмассивов последовательно – один за другим, а затем наименьший элемент поместит во входной массив.
Как только система дойдет до конца одного из подмассивов, остальные элементы другого массива копируются во входной. Данный принцип позволяет сформировать окончательно отсортированный массив:
А вот так выглядит модульный тест для получившегося алгоритма:
Это – всего лишь один из примеров реализации рассматриваемой концепции упорядочивания. Данный подход может быть использован в любом языке программирования.
Примеры для C и Python
Реализация merge sort в C будет иметь следующий вид:
Для Python реализация окажется следующей:
Теперь можно изучить другие подходы к упорядочиванию элементов заданного массива.
Пузырьковый поход
Сортировка пузырьком – наиболее известный алгоритм упорядочивания массивов. Он заключается в последовательном сравнивании значений соседних элементов. Если предыдущее число (int) оказывается больше последующего, компоненты меняются местами. Данная концепция позволяет разместить элемент int с большими значениями в конце заданного массива, а с меньшими – в самом начале.
У соответствующего подхода низкая эффективность, поэтому он является учебным. Пузырьковое упорядочивание медленно работает на тестах, в которых маленькие элементы int размещаются в конце заданной цепочки данных. Именно на нем базируются многие другие методы упорядочивания.
Перемешивание
Перемешивание – концепция упорядочивания элементов множества int, базирующаяся на пузырьковом походе. Она является двунаправленной: алгоритм перемещается не только слева направо, а сначала слева направо, затем – справа налево.
«Расческа»
Метод «расческа» – это модификация пузырькового алгоритма при работе с множеством int. Ее идея заключается в том, чтобы «отсеять» компоненты с небольшими значениями и разместить их в самом конце цепочки. Этот прием значительно ускоряет работу метода.
При «расчесывании» сначала необходимо взять достаточно большое расстояние между двумя сравниваемыми значениями int, а потом – постепенно сужать его вплоть до минимального. Первоначальный разрыв выбирается не случайным образом, а при помощи фактора уменьшения. Его оптимальное значение равно 1,247. Это значит, что расстояние между двумя int в заданной цепочке будет равняться размеру массива, поделенного на фактор уменьшения. На каждом последующем шаге расстояние снова делится на 1,247. Делать так необходимо вплоть до окончания работы алгоритма.
Вставка
Сортировка двух массивов достаточно большого объема может осуществляться при помощи метода «слияние». Для цепочек int небольших размеров стоит воспользоваться простым алгоритмом. Он называется «вставка».
При реализации этой концепции цепочка int перебирается слева направо. Каждый последующий компонент размещается так, чтобы он оказался между ближайшими int с минимальным и максимальным значением.
Выбор
Еще один простой вариант упорядочивания цепочек int. При алгоритме «выбор» сначала необходимо рассмотреть подмножество заданного массива и определить в нем максимум или минимум. Далее – выбранное значение поменять местами со значением первого неотсортированного множества int. Этот шаг выполняется до тех пор, пока в цепочке не закончатся неотсортированные подмассивы.
Быстрая сортировка
Быстрая сортировка – это подход, который выполняется в три этапа:
- Сначала из заданного множества int необходимо выбрать один компонент – опорный.
- Другие составляющие множества int перераспределяются так, чтобы элементы меньше опорного располагались до него, а большие или равные – после.
- Рекурсивно применяются первые два шага в заданных подмассивах справа и слева от опорного значения.
Такой подход, как и merge sort, является эффективным. Быстрая сортировка появилась в 1960 году. Она использовалась для машинного перевода: тогда словари размещались на специальных магнитных лентах, а упорядочивание слов обрабатываемого текста давало возможность получать переводы всего за один прогон ленты.
Хотите освоить современную IT-специальность? Огромный выбор курсов по востребованным IT-направлениям есть в Otus!
