Содержание
- 3. Оценка алгоритма сортировки Алгоритмы сортировки ведут себя по‑разному в различных обстоятельствах. Например, пузырьковая сортировка опережает быструю
- 4. Память – второй параметр, характеризующий эффективность алгоритма. Ряд алгоритмов требует выделения дополнительной памяти под временное хранение
- 5. Общие принципы преобразования данных при использовании алгоритмов сортировки Таблицы указателей При сортировке элементов данных программа перестраивает
- 6. Объединение и сжатие ключей Иногда можно хранить ключи списка в комбинированной или сжатой форме. Например, можно
- 7. Например, требуется закодировать строки, состоящие из заглавных латинских букв. Можно считать, что каждый символ — это
- 10. 1.а Сортировка выбором Сортировка выбором (selection sort) — простой алгоритм сортировки, относящийся к неустойчивым алгоритмам сортировки.
- 11. 1.б Сортировка выбором Вычислительная сложность алгоритма При поиске i-го наименьшего элемента, алгоритму приходится перебрать N-i элементов,
- 12. 1.в Сортировка выбором Пример упорядочения по возрастанию
- 13. 1.г Сортировка выбором
- 14. 1.д Сортировка выбором
- 15. 2.а Сортировка вставкой Сортировка вставкой (insertion sort) — алгоритм со сложностью порядка O(N^2). Особенности алгоритма прост
- 16. 2.б Сортировка вставкой Алгоритм На каждом шаге алгоритма выбираем один из элементов входных данных и вставляем
- 17. 2.в Сортировка вставкой Пример
- 18. 2.г Сортировка вставкой Полное число шагов, которые потребуется выполнить, составляет 1 + 2 + 3 +
- 19. 2.д Сортировка вставкой
- 20. 2.е Сортировка вставкой
- 21. 2.ж Сортировка вставкой Вставка в связных списках Можно использовать вариант сортировки вставкой для упорядочения элементов не
- 22. 2.ж Сортировка вставкой В наихудшем и среднем случаях вычислительная сложность алгоритма порядка O(N^2). Преимущество использования связных
- 23. 3.а Сортировка пузырьком Сортировка простыми обменами, сортировка пузырьком (bubble sort) — простой алгоритм сортировки. Для понимания
- 24. 3.б Сортировка пузырьком Пример. Сортировка пузырьком Последовательность чисел представлена вертикально: первая запись – в самом низу,
- 25. 3.в Сортировка пузырьком Примеры. Массивы расположены вертикально. Первый элемент вверху, последний – внизу. А) Проход от
- 26. 3.г Сортировка пузырьком Усовершенствование алгоритма 1.При просмотре массива сверху вниз (от конца к началу), элементы, которые
- 27. 3.д Сортировка пузырьком Усовершенствование алгоритма 2.Вместо выполнения нескольких отдельных перестановок, можно сохранить перемещаемое значение во временной
- 28. 3.е Шейкерная сортировка Сортировка перемешиванием (Шейкерная сортировка) (Cocktail sort) — разновидность пузырьковой сортировки. Анализируя метод пузырьковой
- 29. 3.ж Шейкерная сортировка Пример. Шейкерная сортировка
- 30. 3.з Шейкерная сортировка procedure TForm1.Bubblesort(list1: PlongIntarray; min, max: longint); var i,j,tmp,last_swap: longint; begin while min begin
- 31. 3.и Шейкерная сортировка begin //куда сдвинуть пузырек tmp:= list1[i-1]; j:=i; repeat list1[j-1]:=list1[j] ; //memo2.Lines.Add('погружение') ; //Btnwritememo.Click;
- 32. 3.к Шейкерная сортировка //обновление max max:= last_swap-1; //всплытие last_swap:= max+1; i:=max-1; while i>=min do begin //нахождение
- 33. 3.л Шейкерная сортировка list1[j+1]:=tmp; last_swap:=j+1; i:=j-1; end else i:=i-1; end; //конец всплытия //обновление min min:=last_swap+1; end;
- 34. 4.а Быстрая сортировка Быстрая сортировка — рекурсивный алгоритм, который использует подход «разделяй и властвуй». Если сортируемый
- 35. 4.б Быстрая сортировка Пример. Быстрая сортировка Предполагается, что первый элемент принадлежит первому подсписку. После разделения на
- 36. 4.в Быстрая сортировка Особенности версии алгоритма 1.Среднее значение для деления списка не входит ни в один
- 37. 4.г Быстрая сортировка Способы выбора разделительного элемента 1.Можно использовать элемент из середины списка. Но он может
- 38. 4.д Быстрая сортировка Особенности алгоритма быстрой сортировки Если данные имеют небольшой диапазон значений (много дубликатов нескольких
- 39. 4.е Быстрая сортировка Быстрая сортировка (quicksort), сортировка Хоара, часто называемая qsort по имени реализации в стандартной
- 40. 4.ж Быстрая сортировка
- 41. 4.з Быстрая сортировка
- 42. 4.и Быстрая сортировка
- 43. 5.а Сортировка слиянием Сортировка слиянием (merge sort) — алгоритм сортировки, который упорядочивает списки (или другие структуры
- 44. 5.б Сортировка слиянием Пример. Слияние двух упорядоченных массивов
- 45. 5.в Сортировка слиянием Пример
- 46. 5.г Сортировка слиянием Пример
- 47. 5.д Сортировка слиянием Этап слияния Подсписки сливаются во временный массив, и результат копируется в первоначальный список.
- 48. 5.е Сортировка слиянием
- 49. 5.ж Сортировка слиянием
- 51. Скачать презентацию