Презентация на тему "Быстрая сортировка.quicksort"

Содержание

• 
  Слайд 1

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

  История про один из самых значимых алгоритмов 20 века

• 
  Слайд 2

  Quicksort (рекурсивен, как и Mergesort)

  Основная идея: Перетасовываем массив Разделяем его так, чтодля любой j Элемент a[j] находится направильном месте в массиве Слева от j нет большего элемента Справа от j нет меньшего элемента Сортируем каждый участок рекурсивно И т.д. – рекурсивно сортируем левые и правые части

• 
  Слайд 3

  Пример quicksort

  Повторяем до тех пор, пока указатели iи j не пересекутся. Проходим указателем iслева-направо до тех пор, покавыпусл-иеa[i] a[lo] Меняем местами a[i] и a[j]

• 
  Слайд 4
  

  Выбираем K в качестве разделителя. Двигаем указательiслева-направо, до тех пор пока не найдем элемент, больший чем разделитель K. И двигаем указатель j справа-налево, пока не найдем элемент меньший разделителя K. В данном примере: iостанавливается сразу, так как K > R и условие a[i]

• 
  Слайд 5
  

  Выбираем K в качестве разделителя. Двигаем указательiслева-направо, до тех пор пока не найдем элемент, больший чем разделитель K. И двигаем указатель j справа-налево, пока не найдем элемент меньший разделителя K. В данном примере: jостанавливается в C, так как C a[lo] не выполняется

• 
  Слайд 6
  

  Мы нашли позиции a[i] и a[j], удовлетворяющие условиям относительно a[lo]. Меняем a[i] и a[j] местами

• 
  Слайд 7
  

  Меняем стартовые позиции - i увеличиваем на 1и j уменьшаемна 1

• 
  Слайд 8
  

  Ищем a[i] и a[j], удовлетворяющие условиям. Это a[i] = Tи a[j] = I

• 
  Слайд 9
  

  Меняем их местами

• 
  Слайд 10
  

  Продолжаем по аналогии Меняем местами

• 
  Слайд 11
  

  Увеличиваем iи уменьшаем j Процесс разделения закончен, так как iи j пересеклись

• 
  Слайд 12
  

  Фаза 2 (указатели пересеклись) Меняем местами a[lo] и a[j] Теперь слева от K только меньшие элементы, в справа только большие

• 
  Слайд 13

  Quicksort реализация

  Состояние массива до, во время и после

• 
  Слайд 14
  

  А перетасовывается для того, чтобы гарантировать нормальную производительность

• 
  Слайд 15

  Quicksort пошагово

• 
  Слайд 16

  Quicksort особенности реализации

  Разделение. Использование дополнительного массива делает разделение более простым и стабильным, но требует доп памяти. Quicksort, в отличии от Mergesort, использует только 1 массив. Удаление циклов. Проверка пересечения указателей iи j, немного сложнее, чем кажется. Остаемся в границах массива. Проверка j == lo не нужна, так как там есть разделитель (a[lo]), но i == hi нужна. Сохранение случайности элементов. Перетасовка массива необходима для гарантии производительности. Одинаковые ключи. Когда есть одинаковые элементы, лучше останавливаться на элементах, равных разделителю.

• 
  Слайд 17

  Quicksort эмпирический анализ

  Оценки производительности Домашний ПК – 10^8 операций/сек Суперкомпьютер – 10^12 операций/сек

• 
  Слайд 18

  Quicksort анализ в лучшем случае

  Лучший случай. Число сравнений ~ N*lgN

• 
  Слайд 19

  Quicksort анализ в худшем случае

  Лучший случай. Число сравнений ~ ½ *N2 Если мы предварительно отсортируем массив, то такой случай маловероятен.

• 
  Слайд 20

  Quicksort. Анализ с среднестатистическом случае

  Предположение. Среднее число сравнений CNдля сортировки quicksort массива N различных элементов ~ 2*N*lnN (и число перестановок ~ 1/3*N*lnN) Док-во. CNудовлетворяет рекуррентному соотношению C0 = C1 = 0 и N>=2: Умножаем обе половины на N и раскрываем скобки: (I) Записываем (I) для N-1 и вычитаем его из (I), получаем:

• 
  Слайд 21
  

  Док-во.Переставляем слагаемые и делим всё на N*(N+1) Рекурсивно подставляем данное соотношение:

• 
  Слайд 22
  

  Док-во.Переставляем слагаемые и делим всё на N*(N+1) Рекурсивно подставляем данное соотношение:

• 
  Слайд 23
  

  Док-во.Вычисляем сумму с помощью интеграла Получаем желаемый результат:

• 
  Слайд 24

  Quicksort. Выводы по производительности.

  Худший случай. Число сравнений квадратично 1 Такой случай маловероятен, из-за предварительной случайной перетасовки Среднестатистический случай. Число сравнений ~ 1.39*N*lgN На 39% больше сравнений чем в Mergesort Но быстрее Mergesortиз-за меньшей работы с памятью Случайная сортировка. Случайность спасает от худшего случая Основа для мат модели, которая может быть оценена с помощью экспериментов. Стоит учитывать что! Многие книжные реализации работают квадратично, если: Массив отсортирован (по убыванию или возрастанию) Имеет много повторяющихся элементов (даже если случайно перетасован)

• 
  Слайд 25

  Quicksort. Свойства

  Предположение. Quicksort сортирует «на месте», т.е. не использует доп массивов. Док-во. 1) Разделение. Требует фиксированной доп памяти 2) Глубина рекурсии. Логарифмическая доп память (с высокой вероятностью) Предположение. Quicksort нестабилен. Док-во.

• 
  Слайд 26
  

  Предположение. Quicksort сортирует «на месте», т.е. не использует доп массивов. Док-во. 1) Разделение. Требует фиксированной доп памяти 2) Глубина рекурсии. Логарифмическая доп память (с высокой вероятностью) Предположение. Quicksort нестабилен. Док-во. Разделение совершает Перестановки на большие расстояния

• 
  Слайд 27

  Quicksort. Возможные улучшения

  Сортировка со вставкой для маленьких подмассивов Quicksort жрет слишком много памяти для маленьких массивов Предел для использования Quicksort – от 10 элементов Java-code. For C# change Comparable[] to IComparable[]

• 
  Слайд 28
  

  Медиана Предполагаем, что разделитель находится примерно в середине. Берем несколько элементов и определяем их медиану Медиана 3 (случайных) элементов, немного снижает число сравнений, но увеличивает число перестановок

• 
  Слайд 29

  ПРОСЫПЕМСЯ!

  Предполагаемое время работы алгоритма quicksort с случайной перетасовкой на уже отсортированном массиве: Линейно N*lgN Квадратично Экспоненциально

• 
  Слайд 30

  Выборка

  Дан массив N элементов, найти k-ый наибольший элемент Прим. Минимум (k=0), максимум (k=N-1), медиана (k = N/2) Приложения: Статистика Найти наибольшие k элементов Теоретические знания для реализации алгоритмва: N*logNверхняя граница – сортируем массив, макс элт – последний, мин - первый N верхняя граница для k=1,2,3 – если k мало, то время работы проп-но N N нижняя граница – достаточно просмотреть весь массив Из всего этого можно сделать вывод – нужен линейный алгоритм. Существует ли линейный алгоритм или выборка так же сложна как сортировка.

• 
  Слайд 31

  Quick-select. Быстрая выборка

  Разделяем массив, так что: a[j] находится на месте Слева от j нет больших элементов Справа от j нет меньших элементов Повторяем в одном подмассиве, в зависимости от j; заканчиваем когда j равно k

• 
  Слайд 32

  Quick-select. Математический анализ

  Предположение. Quick-select в среднем работает линейное время. Док-во. На каждом шаге разделения массив делится примерно пополам: N + N/2 + N/4 + … + 1 ~ 2N сравнений. Формальный анализ, подобный тому, что был в quicksort: P.S. Quick-select использует ~ ½ N2сравнений в худшем случае, но (как с quicksort)случайная перетасовка дает некую защиту от этого.

• 
  Слайд 33

  ПРОСЫПАЕМСЯ!!!

  Каково ожидаемое время работы для поиска медианы используя quick-select со случайной перетасовкой? Постоянно Логарифмично Линейно N*lgN

• 
  Слайд 34

  Повторяющиеся ключи (элементы)

  Часто, задачей сортировки является группировка записей с одинаковыми ключами Сортировка по возрасту Удаление одинаковых писем из ящика Прибытий автобусов на остановки Типичные свойства подобных приложений: Большие массивы данных Маленькое число ключей

• 
  Слайд 35

  Повторяющиеся ключи

  Mergesortдля повторяющихся ключей. Число сравнений между ½*N*lgNи N*lgN Quicksort для повторяющихся ключей: Алгоритм квадратичен, но не в случае когда разделение останавливается на одинаковых ключах!

• 
  Слайд 36

  Повторяющиеся ключи. Проблема

  Ошибка. Все элементы, равные разделителю, размещаются с одной стороны Последствие. ~ ½ N2сравнений, если все ключи одинаковы. Рекомендуется. Останавливать поиск на элементах равных разделителю. Последствие. ~N*lgNсравнений когда все ключи одинаковы. Чего хотим. Размещать все элементы, равные разделителю, в одном месте.

• 
  Слайд 37

  Разделение в 3 направлениях

  Цель. Разделять массив на 3 части таким образом, что: Элементы между ltи gtравны разделителю v Слева от ltнет больших элементов Справа от gtнет меньших элементов

• 
  Слайд 38

  Разделение в 3 направлениях. пример

  Пусть v разделитель a[lo] Сканируем i cлева-направо. (a[i] v): меняем местами a[gt] и a[i];уменьшаем gt (a[i] == v): увеличиваем i

• 
  Слайд 39
  

  Указатель iнаходится слева от неизвестной (не просмотренной области). Слева от ltвсё меньшее v, между ltи i –равное v,между iи gt–неизвестное, больше gt– большее v

• 
  Слайд 40
  

  Увеличиваем i. А меньше чем P, поэтому переносим её за lt. При этом увеличиваем ltи i

• 
  Слайд 41
  

  Теперь iуказывает на B, B тоже меньше чем P, переносим элемент. Увеличиваем ltи i

• 
  Слайд 42
  

  X больше чем P, меняем его местами с gt, уменьшаем gt.

• 
  Слайд 43
  

  Та же ситуация, меняем местами с gt, при этом уменьшаем gtна 1

• 
  Слайд 44
  

  То же самое

• 
  Слайд 45
  

  С

• 
  Слайд 46
  

  P > W, меняем местами с gt.

• 
  Слайд 47
  

  Теперь iуказывает на элемент, равный разделителю. Просто увеличиваем i

• 
  Слайд 48
  

  Снова P = P, делаем всё аналогично, пока не получим более-менее отсортированный массив.

• 
  Слайд 49
  
• 
  Слайд 50

  Разделение в 3 направлениях. Пошагово

• 
  Слайд 51

  Разделение в 3 направлениях. реализация

• 
  Слайд 52

  Повторяющиеся ключи. Нижняя граница

  Вывод – Quicksort со случайным перетасовыванием и разделением в 3 направлениях становитсялинейным алгоритмом, а не N*lgN

• 
  Слайд 53

  ПРОСЫПАЕМСЯ!

  Использование разделения в 3 направлениях с Quicksort наиболее эффективно в случаях кгода входные данные имеют следующее свойство Все элементы различны Есть несколько различных элементов Элементы расположены в порядке возрастания Элементы расположены в порядке убывания

• 
  Слайд 54

  Сортировки в повседневной жизни

  Алгоритмы сортировки распространены в огромном количестве приложений: Сортировка имен Библиотеке песен Выдаче google RSS-ленте, для сортировки новостей Поиск медианы Бинарный поиск в БД Поиск повторяющихся email’ов Сжатие данных Компьютерная графика Вычислительная биология

• 
  Слайд 55

  Какой алгоритм использовать?

  Алгоритмов больше, чем мы рассмотрели: Внутренняя сортировка: Со вставкой, с выбором, пузырёк, shaker sort Quicksort, mergesort, heapsort, samplesort, сортировка Шелла. Solitaire sort, red-black sort, splaysort, Yaroslavskiy sort, psort,… Внешнаяя сортировка. Poly-phase mergesort, cascade-merge, oscillating sort. Строчные сортировки. Distribution, MSD, LSD, 3-way string quicksort. Параллельные сортировки. Bitonic sort, batcher even-odd sort. Smooth sort, cube sort, column sort. GPUsort

• 
  Слайд 56
  

  Приложения имеют множество параметров/особенностей Стабильность Параллельность Определенность Различие ключей Различие типов ключей Массив или ссылочный список Случайность расположения элементов И т.д. Можно использовать одну сортировку или комбинацию. НО – учесть все параметры и особенности практически невозможно Вывод – нет единого «правильного» метода сортировки!

• 
  Слайд 57

  Вывод по сортировкам