Содержание
- 2. Можно ли еще улучшить алгоритм поиска? В общем случае – нет, так что в наихудшем случае
- 3. Бинарный поиск Идея: В любой момент мы рассматриваем только подмассив, т.е. часть массива между двумя индексами
- 4. Бинарный поиск 1) В случае A[q] > x в силу упорядоченности массива все элементы, расположенные справа
- 5. Алгоритм бинарного поиска Процедура Binary-Search(A,n,x). Вход и выход: те же, что и в Linear-Search. Шаги процедуры:
- 6. Рекурсивный вариант бинарного поиска Процедура Recursive-Binary-Search(A,p,r,x). Вход и выход: входные параметры А и х те же,
- 7. Время работы бинарного поиска Ключевой факт: размер r-p+1 рассматриваемого подмассива уменьшается примерно вдвое на каждой итерации
- 8. Сортировка Рассмотрим четыре алгоритма сортировки массива: все они имеют время работы в худшем случае либо Θ(n2),
- 9. Сортировка выбором Проходим по всему массиву, находим наименьший элемент и меняем этот элемент местами с первым
- 10. Алгоритм сортировки выбором Процедура Selection-Sort(A,n). Вход: • А – сортируемый массив. • n – количество сортируемых
- 11. Поиск наименьшего элемента в подмассиве А[i..n] представляет собой вариант линейного поиска. Наличие «вложенного цикла». Доказательство корректности
- 12. Время работы сортировки выбором 1) На i-м шаге внешнего цикла внутренний цикл выполняется n-i раз. 2)
- 13. Сортировка вставкой Сортировка ведется так, что элементы в первых i позициях — это те же элементы,
- 14. Алгоритм сортировки вставкой Процедура Insertion-Sort(A,n). Вход и результат: те же, что и в Selection-Sort. Шаги процедуры:
- 15. Время работы сортировки вставкой Количество итераций внутреннего цикла зависит как от индекса i внешнего цикла, так
- 16. В среднем каждый элемент будет больше около половины предшествующих ему элементов и меньше тоже около половины
- 17. Сортировка слиянием Парадигма «разделяй и властвуй» 1) Разделение. Задача разбивается на несколько подзадач, которые представляют собой
- 18. Алгоритм сортировки слиянием Процедура Merge-Sort(A,p,r). Вход: А – массив, р, r – начальный и конечный индексы
- 19. Пример: Merge-Sort(A,1,10)
- 20. Процедура слияния Слияние не может осуществляться без привлечения дополнительной памяти. 1) Пусть n1 = q-р+1 —
- 21. Алгоритм слияния подмассивов Процедура Merge(A,p,q,r). Вход: А – массив, p, q, r – индексы в массиве
- 22. Время работы сортировки слиянием Для простоты положим, что размер массива n представляет собой степень 2, так
- 23. Сравнение алгоритмов сортировки Плюсы сортировки слиянием: -- С точки зрения времени работы сортировка слиянием [Θ(nlog2n)] однозначно
- 24. Быстрая сортировка Как и в сортировке слиянием, используется парадигма "разделяй и властвуй" (а следовательно, и рекурсия).
- 25. Выберем один элемент и назовем его опорным. Поместим все элементы, меньшие опорного, слева, а элементы, большие
- 26. Процедура быстрой сортировки Процедура Quicksort(A,p,r). Вход и результат: те же, что и у процедуры Merge-Sort. Шаги
- 27. Процедура разбиения Выбираем в подмассиве A[p..r] крайний справа элемент A[r] в качестве опорного. Затем мы проходим
- 28. Процедура Partition(A,p,r). Вход: тот же, что и для Merge-Sort. Результат: перестановка элементов A[p..r], такая, что каждый
- 29. Время работы быстрой сортировки В наихудшем случае размеры разделов являются несбалансированными. Например, если массив изначально отсортирован
- 30. Время работы быстрой сортировки Если элементы входного массива располагаются в случайном порядке, то в среднем получаем
- 31. Резюме
- 32. Можно ли превзойти время сортировки Θ(nlog2n)? НЕТ Если единственный способ определения порядка размещения элементов – это
- 33. Простая сортировка за время Θ(n) Предположим, что каждый ключ сортировки является либо единицей, либо двойкой. Пройдем
- 34. Процедура очень простой сортировки Процедура Really-Simple-Sort(A,n). Вход: А – массив, все элементы которого имеют значения 1
- 35. Сортировка подсчетом Обобщение на случай m различных возможных значений ключей сортировки, которые являются, скажем, целыми числами
- 36. 1) Вычислим, у какого количества элементов ключи сортировки равны заданному значению Процедура Count-Keys-Equal(A,n,m). Вход: • А
- 37. 2) Выясним, у какого количества элементов ключи сортировки меньше каждого возможного значения Процедура Count-Keys-Less(equal,m). Вход: •
- 38. 3) Создадим отсортированный массив путем перемещения элементов из массива А в массив В так, чтобы они
- 39. 3. Для i = 1 до n: A. Установить значение key равным A[i]. B. Установить значение
- 40. 4) Собираем все три процедуры вместе для создания окончательной процедуры сортировки подсчетом Процедура Counting-Sort(A,n,m). Bход: •
- 41. Время работы сортировки подсчетом Исходя из времени работы процедур Count-Keys-Equal (Θ(m+n)), Count-Keys-Less (Θ(m)) и Rearrange (Θ(m+n)),
- 42. Устойчивость сортировки Сортировка подсчетом имеет еще одно важное свойство. Она является устойчивой: элементы с одним и
- 43. Поразрядная сортировка Используется сортировка подсчетом и ее свойство устойчивости. Предполагается, что каждый ключ сортировки можно рассматривать
- 44. Пример поразрядной сортировки Нужно отсортировать по алфавиту и по возрастанию двухсимвольные коды . 1) Сортируем подсчетом
- 46. Скачать презентацию