Лекция для первого курса ИТМО про сортировки

• Квадратичные
  • insertion
  • selection
  • bubble
• Теорема про нижнюю оценку
  • доказываем "не может отсортировать все входы"
  • доказываем "не может отсортировать 1/100 перестановок"
  • упр. для самостоятельного решения: доказать, что не может сортировать 1/2ⁿ входов
• MergeSort
  • рекурсивный
  • оцениваем время работы
  • нерекурсивный и без копирования памяти

• Стабильность, сравнение HeapSort, MergeSort

• C++: merge, sort, stable_sort

• Реклама:
  • nloglogC Kirkpatirck'84
  • nsqrt(loglogn) Han,Thorup'95
  • CountSort, RadixSort, BucketSort (с временами работы)
• Теорема о времени работы
  • в форме T(n) = ∑_iT(n ⋅ a_i) + n (C = ∑_ia_i, варианты : C < 1, C = 1, C > 1)

• Кончилось время

• Теорема о времени работы
  • в форме T(n) = ∑_ib_i ⋅ T(n ⋅ a_i) + f(n)
• Что можно делать с сортировками?
  • хранение упорядоченные множеств (пример: пересечение, дз: объединение, разность)
  • бинпоиск и задача "сколько чисел от l до r"
  • C++: set_intersection, set_union, set_difference, lower_bound, upper_bound

• Упр: докажите, что бинпоиск не может работать быстрее logn