Тема 8 Алгоритмы сортировки

8.1. Сортировка. Основные понятия

Пусть задан -файл, состоящий из записей . Припишем каждой записи ключ . Ключ – какое-либо отдельное поле или комбинация полей записи. Часто запись целиком составляет поле ключа. Будем считать, что на множестве ключей задано отношение линейного порядка или следования с обычными свойствами, т.е. элементы этого множества можно выстроить в порядке не убывания (не возрастания). Задача сортировки файла ставится так.

Найти такую перестановку записей -файла, чтобы в -файле для записей их ключи располагались в неубывающем порядке: .

Для получения -файла из -файла в общем случае требуется физическое перемещение записей в памяти компьютера. Однако во многих случаях реальная перестановка не требуется. Достаточно описать ее некоторым способом так, чтобы обеспечить непосредственный доступ к записям в соответствии следованию их ключей. Сделать это можно посредством адресного кодирования или адресной перестановки, в которой сортируются индексы (адреса) элементов-записей, а не сами записи. Правда в этом случае под адреса требуется дополнительная память. Часто адресное кодирование применяется в качестве первого этапа для обычной сортировки.

№	Ф. И. О.	Курс	Предмет	Тип задолженности
1 2 3 4 5 6 7	Щукина Э. Паниковский М.С. Бендер О.И. Синицкая З.В. Воробьянинов И.М Востриков Ф Изнуренков А.В.	2Д 1Б 3А 1Е 4В 1В 5Г	Алгебра Физика Физика Геометрия Алгебра Физика Алгебра	Зачет Экзамен Зачет Экзамен Экзамен Зачет Зачет

Пример 1. В таблице приведен текстовый файл из 7 записей. Запись состоит из 5 полей. Адресное кодирование файла в алфавитном порядке фамилий студентов производится посредством списка: 3, 5, 6, 7, 2, 4, 1. Этот список можно использовать для реального перемещения записей в файле задолжников.

Различают внутреннюю сортировку данных в памяти компьютера и внешнюю сортировку данных, расположенных на диске. При внутренней сортировке стремятся уменьшить число сравнений ключей и перемещений записей, а при внешней сортировке – количество обращений к диску. В дальнейшем будем ориентироваться на внутреннюю сортировку числовых и символьных одномерных массивов. Записями и ключами таких файлов-массивов будем считать значения их элементов.

Пример 2. Отсортировать числовой массив: 7,2 3 8 4 8 5,14 9 1.

О

Адресная сортировка: 7,2 3 8 4 8 5,14 9 1

5 2 6 3 7 4 8 1

бычная сортировка: 1 3 4 5,14 7,2 8 8 9.

8.2. Пузырьковая сортировка

Среди большого числа сортировок наиболее популярна пузырьковая сортировка. Ее название происходит от образной интерпретации всплывания более легких элементов (пузырьков) на поверхность.

Пусть S числовой массив . Говорят, что элементы и из S образуют инверсию, если i < j и .

А

Dim A() As Integer: Const n As Integer = 20

Sub Пузырьковая_сортировка ()

Dim i As Integer, j As Integer, m As Integer, var As String

ReDim A (1 To n): var = "Исходные:"

For i = 1 To n: A(i) = Int(Rnd(Time)*100): var = var & " " & Str(A (i)): Next i: MsgBox var

For i = 2 To n: For j = n To i Step -1

If A(j-1) > A(j) Then

m = A(j-1): A(j-1) = A(j): A(j) = m

End If

Next j: Next i

var = "Отсортированные:":For i = 1 To n: var = var & " " & Str(A (i)): Next i: MsgBox var

End Sub

лгоритм пузырьковой сортировки состоит в последовательных просмотрах снизу вверх (от конца к началу) массива S и обмене местами соседних элементов с инверсией. Трудоемкость алгоритма - O(n²), т.е. для любых S и n он решает задачу за Cn² операций сравнения и обмена, где C -константа, от n не зависящая.

Пузырьковая сортировка не требует дополнительной памяти, однако из-за плохих временных характеристик она имеет лишь исторический интерес. Практический интерес представляют две наиболее эффективных сортировки Пирамидальная и Быстрая.