Сортировки

1.

СОРТИРОВКИ

2.

Определение
Сортировка — это алгоритм для упорядочивания
элементов в массиве.
Цель сортировки – упорядочить информацию и
облегчить поиск требуемых данных

3.

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

4.

Определение
Сортировка данных в оперативной памяти
называется внутренней, а сортировка данных во
внешних носителях называется внешней

5.

Устойчивая и неустойчивая
сортировка
Устойчивый алгоритм сортировки
(stable sort) – если в процессе сортировки
относительный порядок элементов с
одинаковыми ключами не изменяется.
Обычно устойчивая сортировка
предпочтительнее неустойчивой.

6.

БАЗОВЫЙ АЛГОРИТМ СОРТИРОВКИ
Считаем, что нам известен алгоритм
поиска минимального элемента в
массиве.

7.

БАЗОВЫЙ АЛГОРИТМ СОРТИРОВКИ
Адаптируем алгоритм поиска минимального
элемента для целей сортировки.
Фиксируем первый элемент массива. Ищем
минимальный элемент среди оставшихся
элементов справа, выполняя обмен значений с
первым элементом.
Сдвигаемся вправо: фиксируем второй элемент,
ищем минимальный среди оставшихся справа.
Повторяем до предпоследнего элемента.

8.

СОРТИРОВКА ВЫБОРОМ
Выполним оптимизацию базового алгоритма
для сокращения количества обменов. А именно,
при поиске минимума будем запоминать
индекс минимального элемента. После поиска
минимума один раз сделаем обмен элементов
(если индексы разные).
Полученный алгоритм называется сортировка
выбором.

9.

СОРТИРОВКА ВЫБОРОМ

10.

СОРТИРОВКА ВЫБОРОМ
for (i = 0; i < n; i++)
{
ind_min = i;
for (j = i + 1; j < n-1; j++)
if (mas[ind_min] > mas[j])
ind_min = j;
temp = mas[ind_min];
mas[ind_min] = mas [i];
mas[i] = temp;
}

11.

СОРТИРОВКА ПУЗЫРЬКОМ
Первый проход: соседние элементы сравниваются
попарно. Если порядок в паре неверный,
выполняется обмен элементов. Результат – самый
больший в конце.
Повторяем проходы до предпоследнего элемента,
до пред-предпоследнего, и так далее (за
повторение проходов отвечает внешний цикл).
При каждом проходе наименьший элемент
перемещается на одну позицию к началу массива
(«всплывает» до нужной позиции, как пузырёк в
воде).

12.

СОРТИРОВКА ПУЗЫРЬКОМ

13.

СОРТИРОВКА ПУЗЫРЬКОМ
for(i = 0;i < k-1; i++)
for(j = 0; j < k-i; j++)
{
if(ms[j] > ms[j+1])
{
temp = ms[j+1];
ms[j+1] = ms[j];
ms[j] = temp;
}
}

14.

СОРТИРОВКА ВСТАВКАМИ
На любом промежуточном этапе сортировки
массив разделён на две части: в левой
элементы уже упорядочены по возрастанию, в
правой – ещё нет.
Текущий элемент – это самый левый элемент
из правой части. Запоминаем текущий элемент
и начинам искать для него место в левой части,
сдвигая элементы вправо. Стоп – если
следующий элемент слева меньше текущего,
или дошли до начала массива.

15.

СОРТИРОВКА ВСТАВКАМИ КАК
ОНЛАЙН-АЛГОРИТМ
В информатике онлайн-алгоритм – это
алгоритм, который может обрабатывать
входные данные, не имея их в полном доступе с
самого начала своей работы.
Алгоритм сортировки вставками – пример
онлайн-алгоритма. Данные для сортировки
можно дописывать в конец сортируемого
массива в процессе работы.

16.

СОРТИРОВКА ВСТАВКАМИ
СОРТИРОВКА ВСТАВКАМИ

17.

СОРТИРОВКА ВСТАВКАМИ
for(i = 1; i < n; i++)
{
value = a[i]; значение предыдущего элемента
for (j = i - 1; j >= 0 && a[j] > value; j--)
{
a[j + 1] = a[j];
} сдвиг всех элементов направо
a[j + 1] = value; запись в освободившийся или
в тот же элемент
}

18.

СОРТИРОВКА МЕТОДОМ ШЕЛЛА
Сначала
сравниваются и меняются все элементы,
отстоящие друг от друга на шаг
Затем элементы, расположенные на расстоянии шаг/2
Наконец, сортируются все соседние элементы

19.

СОРТИРОВКА МЕТОДОМ ШЕЛЛА
for(gap = k/2; gap > 0; gap /= 2)
do {
flg = 0;
for(i = 0, j = gap; j < k; i++, j++)
if(ms[i] > ms[j]) // сравниваем отстоящие на
gap
элементы
{
n = ms[j];
ms[j] = ms[i];
ms[i]= n;
flg = 1; // есть еще не рассортированные
данные
}
} while (flg); // окончание этапа сортировки

20.

СОРТИРОВКА СЛИЯНИЕМ
Рекурсивный алгоритм. Изобретен в 1945.
Если в массиве нет элементов или один
элемент, то массив считается отсортированным
и алгоритм завершается
Иначе массив разбивается на две равные(+-)
части, каждая из которых сортируется
слиянием(рекурсия!)
После пред шага к двум частям массива
применяется процедура слияния в один
отсортированный массив

21.

ПРОЦЕДУРА СЛИЯНИЯ
Даны два отсортированных массива A и B (как
вариант – это могут быть две части одного массива).
Их надо объединить в упорядоченный массив C.
Сравниваем элементы массивов A и B (начиная с
первого) и меньший из них записываем в массив C.
В массиве, из которого выбрали меньший элемент,
идём к следующему элементу и сравниваем теперь
его.
Когда один из массивов закончился, копируем в C
остаток другого массива.

22.

МЕТОД ДЕКОМПОЗИЦИИ
Сортировка слиянием – это алгоритм,
использующий метод декомпозиции (а точнее –
его вариант «разделяй и властвуй», divide and
conquer). Суть метода:
1.
Разбиваем исходную задачу на подзадачи
меньшего размера
2.
Решаем подзадачи (если «разделяй и
властвуй» – то рекурсивно).
3.
Комбинируем результаты решения подзадач
в итоговый ответ.

23.

СОРТИРОВКА СЛИЯНИЕМ

24.

БЫСТРАЯ СОРТИРОВКА
Алгоритм придуман Чарльзом Хоаром в 1960 году.
Использует стратегию «разделяй и властвуй»:
1.
Массивы длины 0 или 1 считаются
отсортированными.
2.
Массив переупорядочивается, чтобы в нём было три
части: левая – элементы меньше опорного (но они
не упорядочены), опорный элемент, правая –
элементы равные или больше опорного (тоже не
упорядочены).
3.
После шага 2 к левой и правой частям применяется
алгоритм быстрой сортировки.

25.

БЫСТРАЯ СОРТИРОВКА

26.

ВНУТРЕННЯЯ И ВНЕШНЯЯ
СОРТИРОВКА
Внутренняя сортировка (internal sort) –
алгоритм сортировки (его реализация)
работает с данными в оперативной
памяти.

27.

ВНУТРЕННЯЯ И ВНЕШНЯЯ
СОРТИРОВКА
Алгоритмы внешней сортировки (external
sort) обрабатывают данные, которые
целиком в память не помещаются.
Общая идея:
1) разбить данные на части,
2) отсортировать каждую часть
алгоритмом внутренней сортировки, 3)
сцепить части в упорядоченный набор.