Файл: Алгоритмы сортировки данных.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.5 Сортировка Шелла

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

СПИСОК ЛИТЕРАТУРЫ:

Кнут Д. Э. Искусство программирования. Том 3. Сортировка и поиск /The Art of Computer Programming. Volume 3. Sorting and Searching / под ред. В. Т. Тертышного (гл. 5) и И. В. Красикова (гл. 6). — 2-е изд. — Москва: Вильямс, 2007.
Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ / INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006.
Роберт Седжвик. Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск = Algorithms in C. Fundamentals/Data Structures/Sorting/Searching. — СПб.: ДиаСофтЮП, 2003.
Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. 2.1. Сортировка вставкой // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 3-е изд. — М.: Вильямс, 2013.
Левитин А. В. Глава 4. Метод декомпозиции: Сортировка слиянием // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006.
Левитин А. В. Глава 3. Метод грубой силы: Пузырьковая сортировка // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006.
Алгоритм сортировки – Википедия. http://ru.wikipedia.org/wiki/

Финансовый словарь. dic.academic.ru ↑
Экономический словарь. dic.academic.ru ↑
Попов В.Б. Turbo Pascal для школьников: Учебное пособие, 3-е доп. изд. – М.: Финансы и статистика, 2003 ↑
Роберт Седжвик. Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск = Algorithms in C. Fundamentals/Data Structures/Sorting/Searching. — СПб.: ДиаСофтЮП, 2003. — С. 251. ↑
Роберт Седжвик. Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск = Algorithms in C. Fundamentals/Data Structures/Sorting/Searching. — СПб.: ДиаСофтЮП, 2003. — 251 с. ↑