Мотивация и краткое содержание¶
Цель занятия¶
- Рассмотрим "наивные" подходы к сортировке, их ассимпотическую сложность
- Понятие стабильной и нестабильной сортировки
- Разберем адаптивную сортировку (на примере сортировки вставкой)
- Сравним разные алгоритмы сортировки, выберем применимые на практике.
Основные объекты¶
- Сортировка пузырьком
- Сортировка выбором
- Сортировка вставкой
- Сортировка Шелла
Bubble sort¶
Основная информация¶
- Сортировка пузырьком.
- Простой алгоритм, но неэффективный. Его даже называют настолько плохим, что он не нужен в качестве примера алгоритма при обучении. Именно поэтому мы его разберем!
Псевдокод¶
1 BubbleSort(Array): 2 n = length(Array) 3 repeat 4 swapped = False 5 for i = 1 to> n-1 do 6 if Array[i-1] > Array[i] then 7 swap(Array[i-1], Array[i]) 8 swapped = True 9 n = n - 1 10 until not swapped
Зато красивая визуализация.
Пример работы¶
In [1]:
from bubblesort import BubbleArray, bubble_sort, bubble_sort_improved
demo_array = BubbleArray([4, 5, 8, 3, 1, 2, 6, 7, 9])
In [2]:
bubble_sort(demo_array)
In [3]:
# from bubblesort import *
demo_array = BubbleArray([4, 5, 8, 3, 1, 2, 6, 7, 9])
bubble_sort(demo_array, show_wasted=False)
In [4]:
# from bubblesort import *
demo_array = BubbleArray([4, 5, 8, 3, 1, 2, 6, 7, 9])
bubble_sort(demo_array, show_wasted=True)
In [5]:
# from bubblesort import *
demo_array = BubbleArray(range(9, 0, -1))
bubble_sort(demo_array, show_wasted=True)
In [6]:
# from bubblesort import *
demo_array = BubbleArray([4, 5, 8, 3, 1, 2, 6, 7, 9])
bubble_sort_improved(demo_array, show_wasted=True)
In [7]:
# from bubblesort import *
demo_array = BubbleArray(range(9, 0, -1))
bubble_sort_improved(demo_array, show_wasted=True)
In [8]:
# from bubblesort import *
demo_array = BubbleArray([1, 2, 3, 5, 4, 6, 7, 8, 9])
bubble_sort_improved(demo_array, show_wasted=True)
In [9]:
# from bubblesort import *
demo_array = BubbleArray([1, 2, 3, 5, 4, 6, 7, 8, 9])
bubble_sort(demo_array, show_wasted=True)
Selection sort¶
Сортировка выбором - простой принцип: находится наименьший элемент, меняется местами с первым неотсортированным.
Псевдокод¶
1 SelectionSort(Array): 2 for i in 0..n-1 3 min = i 4 for j in i+1..n-1 5 if Array[j] < Array[min] 6 min = j 7 if i != min 8 swap(Array, i, min)</font>
Анализ сложности¶
- Сколько всего сравнений выполняется в сортировке?
- Сколько шагов во внешнем цикле?
- Сколько шагов во вложенном цикле?
Количество сравнений¶
- непрозрачно
- чуть лучше
- интуитивный вариант
- без сумм
</font>
Как решать рекуррентности?¶
Вопрос подробно рассматривается в книге "Конкретная математика" Р. Грэхема и Д. Кнута.
Доказательство корректности¶
Как организовано доказательство¶
Если в алгоритме присутствует цикл (то есть почти всегда)
- Инвариант цикла
- Сохранение инварианта
- Завершение цикла
Наш случай¶
Если в алгоритме присутствует цикл (то есть почти всегда):
- Инвариант: начало списка до -го элемента отсортировано. При инициалиизации (пустой список) верно
- Сохранение инварианта: после итерации цикла ; начало списка отстортировано
- Завершение цикла: = длине списка, весь список отсортиррован
Определение отсортированного списка¶
Важно дать формальное определение, потому что оно будет имспользоваться при проверке сохранения инварианта
Такая перестановка (элементов массива), что для всех , где - индекс элемента в списке, </font>
Почему так?¶
- Пустой список отсортирован по соглашению
- На каждом следующем шаге выбираем из списка минимальный элемент
- Здесь надо бы доказать, что в списке есть минимальный элемент, и мы извлекаем его :)
- Находим минимальный элемент, вставляем в конец отсортированного списка. При этом список остается отсортированным!
- Завершение цикла: мы добираемся до конца списка. Весь список отсортирован
Картинка - инварианты¶
Примеры работы алгоритма¶
In [10]:
from selection_sort import selection_sort, SelectionArray
array = SelectionArray([9, 3, 4, 6, 5, 7, 8, 2, 0, 1])
selection_sort(array)
In [11]:
array = SelectionArray(list(range(10)))
selection_sort(array)
Insertion sort¶
Псевдокод¶
1 InsertionSort(Array): 2 for i in 0..n-1 3 x = Array[i] 4 j = i - 1 5 while j >= 0 and Array[j] > x 6 Array[j+1] = Array[j] // "сдвиг" вправо 7 j = j - 1 8 Array[j+1] = x // Вставка x в отсортированную часть 9 i = i + 1
Отличие от Selection Sort¶
- Основное отличие - достаточно вего 1го сравнения, когда k+1 элемент > k-го элемента
- selection sort будет "пробегать" все оставшиеся элементы
- selection sort записывает в память раз, а insertion sort -
Также Insertion Sort:
- Стабильный
- Online
- In-place
Пояснения в картинках¶
Online - сортировка¶
Применение¶
- Простой алгоритм, который работает быстро на небольших массивах
- Используется при сортировке небольших массивов в алгоритмах divide and conquer
- Отлично работает для частично отсортированных последоваьтельностей
Примеры работы insertion sort¶
In [12]:
from insertion_sort import insertion_sort, InsertionArray
array = InsertionArray([9, 3, 4, 6, 5, 7, 8, 2, 0, 1])
insertion_sort(array)
array
Out[12]:
In [13]:
from insertion_sort import insertion_sort, InsertionArray
array = InsertionArray([0, 1, 2, 8, 3, 4, 5, 6, 7, 9])
insertion_sort(array)
array
Out[13]:
In [14]:
from insertion_sort import insertion_sort, InsertionArray
array = InsertionArray([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
insertion_sort(array)
array
Out[14]:
Shellsort¶
Сортировка Шелла (1959г.) - "улучшение" сортировки вставками / сортировки пузырьком
Идея сортировки¶
- Разобьем список на части (каждый -й элемент)
- Отсортируем эти части insertion sort
- Повторим с другим разбиением c меньшим , если
Визуализация¶
Вопросы¶
- Почему Shell sort работает быстро?<br>
- И насколько быстро?<br>
- Какие свойства у этой сортировки?
</font>
Домашнее задание¶
- Реализуйте сортировку Шелла
- Оцените скорость работы для случайных и частично упорядоченных данны
- Попробуйте разные наборы шагов, подберите лучшие для различных типов входных данных