Файл: Алгоритмы сортировки данных.pdf

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

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

2.3 Сортировка вставками

Сортировка вставками (англ. Insertion sort) — это алгоритм, в котором элемент из входящего массива по одному перемещается в пустой массив на подходящие для него место. Сложность вычислений алгоритма - O(n²).

Если взять последовательность из n чисел a₁, a₂, …, a_n , то на выходе получится последовательность вида a^⸍₁, a^⸍₂, …, a^⸍_n, удовлетворяющая условию a^⸍₁ ≤ a^⸍₂ ≤ … ≤ a^⸍_n. Сначала отсортированная последовательность пуста.

Если использовать бинарный поиск при нахождении нужного места для элемента, то таким образом можно ускорить работу алгоритма. А используя смену указателей можно исправить проблему долго сдвига массива вправо.

2.4 Сортировка слиянием

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

Для решения задачи сортировки эти три этапа выглядят так:

1. Входной массив разбивается на подмассивы примерно одного размера. Рекурсивное разбиение массива ведётся до тех пор, пока размер массива не будет равен единице. Массив из одного элемента является упорядоченным.
2. Каждый получившийся подмассив сортируется отдельно. Использоваться может один и тот же алгоритм, а могут и разные.
3. Все отсортированные подмассивы объединяются в один. Для этого меньший из двух первых элементов подмассивов перемещается в результирующий массив. При этом счётчики номеров элементов обоих массивов увеличивается на 1. Если в одном из подмассивов остается остаток, то он целиком записывается в конец результирующего массива.

2.5 Сортировка Шелла

Сортировка Шелла (англ. Shell sort) - этот алгоритм является дополненным вариантом сортировки вставками. Его идея заключается в том, что сравниваются не только элементы, расположенные рядом, но и те, что находятся на расстоянии друг от друга. Ещё его можно назвать алгоритм сортировки вставками с предварительными проходами. Аналогичное дополнение в пузырьковой сортировке называется сортировка расчёской.

При сортировке Шелла первым делом происходит сравнение и обмен элементов, расположенных на некотором расстоянии d. Затем тоже самое происходит для меньших значений d. А в самом конце при d=1 используется уже сортировка вставками. То, что число инверсий при сортировке Шелла может быть больше по сравнению с простыми сортировками, где перестановка двух элементов уменьшает число инверсий только на 1, в некоторых случаях может говорить о его эффективности. И хотя во многих случаях скорость алгоритма ниже, чем у быстрой сортировки, он ряд преимуществ:

• нет необходимости выделять память под стек;
• нет деградации если набор данных оказывается неудачным. Быстрая сортировка легко замедляется до O(n²), что хуже по времени, чем худшее гарантированное время для сортировки Шелла.

2.6 Сортировка строк

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

Если метод сортировки строк применить к строке, состоящей из чисел, то результат будет контринтуитивным. Так «9» оказывается больше, чем «11», так как первый символ первой строки имеет бо́льшее значение, чем первый символ второй. Чтобы этого избежать алгоритм может преобразовывать символы чисел в числа и уже их сортировать.

ЗАКЛЮЧЕНИЕ

Изучение вопроса Алгоритмов сортировки выявило интересный факт, что стремление оптимизировать и автоматизировать задачу сортировки стало предпосылкой появления ЭВМ. Некоторые источники утверждают, что именно программа сортировки стала первой программой для вычислительных машин. Некоторые конструкторы ЭВМ, в частности разработчики EDVAC (Electronic Discrete Variable Automatic Computer - одна из первых электронных вычислительных машин), называли задачу сортировки данных наиболее характерной нечисловой задачей для вычислительных машин.