Сортировки

Сортировки

Оглавление

Общие сортировки:

• Сортировка выбором
• Сортировка вставкой
• Сортировка слиянием
• Быстрая сортировка

Частные случаи:

• Сортировка подсчетом

Cводная таблица

Сортировка	Худший случай	Средний случай	Лучший случай	Доп память
Сортировка выбором	О(n2)	О(n2)	О(n2)	Нет
Сортировка вставкой	О(n2)	О(n)	О(n2)	Нет
Сортировка слиянием	О(nlog(n))	О(nlog(n))	О(nlog(n))	Да
Быстрая сортировка	О(n2)	О(nlog(n))	О(nlog(n))	Нет

Теория

Сортировка выбором

Алгоритм:

1. Организуем цикл по массиву range(n)
2. На каждой итерации находим индекс самого маленького элемента в срезе от [i:n]
3. Меняем элемент i с найденным местами

Сортировка	Худший случай	Средний случай	Лучший случай	Доп память
Сортировка выбором	О(n2)	О(n2)	О(n2)	Нет

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

Алгоритм

1. Организуем цикл по массиву range(1,n)

2. На каждой итерации идем в обратном порядке к началу массива и ищем элемент который меньше чем a[i] и меняем значение a[j+1]=a[j], чтобы сделать смещение элементов при вставке нового.

3. Когда нашелся такой элемент или мы дошли до конца массива делаем a[j+1] = a[i]

Сортировка	Худший случай	Средний случай	Лучший случай	Доп память
Сортировка вставкой	О(n2)	О(n)	О(n2)	Нет

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

Алгоритм

Суть алгоритма заключается в реализации двух функций: merge_sort(a,p,r) и merge(a,p,q,r), где p- левая граница сортируемого массива q - середина сортируемого отрезка, а r- правая граница. Все границы включительно.

Алгоритм merge_sort: 0) Пишем условие выхода if p >= r: return (Если левая граница >= правой то длина массива меньше 1)

1. Находим середину сортируемого отрезка q = (p+r) // 2
2. Вызываем функции merge_sort(a,p,q) и merge_sort(a, q+1,r)
3. Вызываем функцию merge(a,p,q,r)
4. Возвращаем отсортированный массив

Алгоритм merge:

1. Создаем два массива b = a[p:q+1] и c = a[q+1:r+1] - левая и правая часть отрезков

2. Закидываем им в конец бесконечности (нужно для удобства реализации) b.append(float('inf')) и c.append(float('inf'))

3. Заводим два индекса i и j. Они будут служить указателями на позиции в наших массивах. А далее итерируемся по массиву a (range(p, r+1)) и сравниваем элементы b[i] и c[j]. Если b[i] > c[j] тогда к a[k] присваиваем b[i] и увеличиваем i на единицу. Аналогично для c[j] и j в иной ситуации.

Сортировка	Худший случай	Средний случай	Лучший случай	Доп память
Сортировка слиянием	О(nlog(n))	О(nlog(n))	О(nlog(n))	Да

Быстрая сортировка

Алгоритм

Алгоритм заключается в реализации двух функций: quick_sort(a,p,r) и partition(a,p,r), где a - сортируемый список p - левая граница, r - правая граница.

Алгоритм quick_sort(a,p,r)

1. Находим опорный элемент при помощи функции partition. Этот элемент обладает некоторыми свойствами:

   • Он считается полностью отсортированным, то есть уже стоит на верной позиции
   • Элементы справа от него больше, элементы слева - меньше. То есть при нахождении опорного элемента удается разбить массив на 2 части.

2. Рекурсивно вызываем функции сортировки левого quick_sort(a,p,q-1) и правого quick_sort(a,q+1,r) отрезков.

3. Возвращаем отсортированный массив

Алгоритм partition(a,p,r):

1. Приравниваем q = p.

2. Итерируемся от начала до конца отрезка и ищем элементы которые меньше опорного и закидываем их в левую часть массива.

3. После завершения цикла меняем опорный элемент с элементом, стоящим после младших

Сортировка	Худший случай	Средний случай	Лучший случай	Доп память
Быстрая сортировка	О(n2)	О(nlog(n))	О(nlog(n))	Нет

Сортировка подсчетом

Алгоритм

Алгоритм сортировки подсчетом сводится к реализации трех функций:

1. count_keys_equal(a, n, m) - функция для подсчета количества различных цифр в списке.
2. count_less_keys(equal, m) - функция для расчета промежуточной суммы, где каждый элемент less[j] является суммой предыдущих элементов.
3. rearrange(a, less, n) - функция пересоздания массива с уже отсортированными значениями.