Содержание
- 2. Сортировка – процесс упорядочения множества объектов по заданному признаку. Обычно сортировку подразделяют на два класса: внутреннюю
- 3. Существуют различные алгоритмы сортировки. Их можно разделить на два класса: Простые и понятные, но неэффективные для
- 4. Сортировать массив можно: 1) по возрастанию – каждый следующий элемент больше предыдущего: a[1] 2) по неубыванию
- 5. Метод простых обменов МЕТОД «ПУЗЫРЬКА» («КАМНЯ»)
- 6. Производится последовательное упорядочение смежных пар элементов массива по убыванию: x[1] и x[2], x[2] и x[3], …x[N-1]
- 7. Пример. Дан массив из 5 элементов: 5 8 1 6 7. Упорядочить его по возрастанию. Первый
- 8. Второй проход по массиву:
- 9. Третий проход по массиву: Четвертый проход по массиву:
- 10. include #include using namespace std; void input(int *m, int &n) { cout cin>>n; for (int i=0;i
- 11. void sort_bubble (int *m, int n) // Сортировка пузырьком { int i, j, t; for (i=0;i
- 12. МОДИФИЦИРОВАННЫЙ «ПУЗЫРЕК»
- 13. При сортировке методом простого обмена («пузырька») возможна ситуация, когда на каком-либо из проходов не произошло ни
- 14. void modif_bubble(int *m, int n) // Модифицированный пузырек { int i=n; // Длина неотсортированной части массива
- 15. ШЕЙКЕР-СОРТИРОВКА
- 16. Пример. Упорядочить массив из 6 элементов: 5, 7, 9, 10, 12, 3 по неубыванию методом «модифицированного
- 17. void sort_sheiker (int *m, int n) // Шейкер-сортировка { int left=1; // левая граница int right=n-1;
- 18. СОРТИРОВКА ВСТАВКАМИ Метод прямого включения
- 19. Начиная со 2-го элемента, каждый текущий элемент с номером i запоминается в промежуточной переменной. Затем просматриваются
- 20. void sort_insert (int *m, int n) { int j,r; for (int i=1;i { r=m[i]; // Запоминаем
- 21. СОРТИРОВКА МЕТОДОМ ПРОСТОГО ВЫБОРА
- 22. Обычно применяется для массивов, не содержащих повторяющихся элементов. Алгоритм: 1) выбрать максимальный элемент массива; 2) поменять
- 23. void sort_vybor (int *a, int n) // Сортировка простым выбором { int k,m; for (int i=n-1;i>0;i--)
- 24. МЕТОД БИНАРНОГО ПОИСКА
- 25. const int NMAX=100; int a[NMAX]; int binSearch(int data[], int rzm_data, int search_key) { int L,H,M; L=0;
- 26. СОРТИРОВКА БИНАРНЫМИ ВСТАВКАМИ
- 27. Алгоритм сортировки простыми включениями можно легко улучшить, пользуясь тем, что готовая последовательность a[1],..., a[i-1], в которую
- 28. void sort_bin_insert (int *a, int n) // Сортировка бинарными вставками { int x,left,right,sred; for (int i=1;
- 29. СОРТИРОВКА ПОДСЧЕТОМ
- 30. Сортировка подсчётом («черпачная») — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива для подсчёта совпадающих
- 31. Пример Пусть дан массив A=(2 5 6 9 4 1 8 2 9 8 4 1
- 32. void sort_count(int *A,int n, int k) { int *C = new int[k]; for (int i =
- 33. Что делать, если диапазон значений (min и max) заранее не известен? Что делать, если минимальное значение
- 34. ЦИФРОВАЯ СОРТИРОВКА
- 35. Алгоритм цифровой сортировки существенно отличается от описанных ранее. Во-первых, он совсем не использует сравнений сортируемых элементов.
- 36. Рассмотрим пример работы алгоритма на входном массиве: Максимальное число содержит две цифры, значит, разрядность данных k=2.
- 37. Cборка: соединяем массивы один за другим Второй проход (j=2) Распределение по второй справа цифре: Cборка: соединяем
- 38. БЫСТРАЯ СОРТИРОВКА Сортировка Хоара
- 39. Рассмотрим элемент, находящийся посередине массива М (назовем его Х). Затем начнем осуществлять два встречных просмотра массива:
- 40. L R Шаг 1 L R L R R L
- 41. L R Шаг 2 R L R L L R Шаг 3 R L L R
- 42. void Qsort(int a[],int L,int R) { int i=L,j=R,w,x; x=a[(L+R)/2]; do { while (a[i] while (a[j]>x) j--;
- 43. СОРТИРОВКА СЛИЯНИЯМИ
- 44. Метод слияний – один из первых в теории алгоритмов сортировки. Он предложен Дж. фон Нейманом в
- 45. Рассмотрим суть метода слияния на примере. Первый фрагмент: 2 4 6 11 Второй фрагмент: 1 3
- 46. Исходная последовательность рекурсивно разбивается на половины, пока не получим подпоследовательности по 1 элементу. Из полученных подпоследовательностей
- 47. Каждую подпоследовательность упорядочиваем методом слияния и получаем готовую последовательность
- 48. void mergeSort(int *a, int l, int r) { if (l == r) return; // границы сомкнулись
- 49. ПИРАМИДАЛЬНАЯ СОРТИРОВКА
- 50. Метод предложен Дж. Уильямсом и Р. У. Флойдом в 1964 году. Элементы массива А образуют пирамиду,
- 51. 1 этап Построение пирамиды. Определяем правую часть дерева, начиная с n/2-1 (нижний уровень дерева). Берем элемент
- 52. Результат просеивания элемента 15 через пирамиду. Следующие просеиваемый элемент – 31.
- 53. Далее просеиваем с номером 0 - 24. Результат: наименьший элемент находится на вершине пирамиды
- 54. 2 этап Сортировка на построенной пирамиде. Берем последний элемент массива в качестве текущего. Меняем верхний (наименьший)
- 55. Повторяем операцию просеивания без учета последнего элемента (для N-1 элемента).
- 59. Несмотря на некоторую внешнюю сложность, пирамидальная сортировка является одной из самых эффективных. Алгоритм сортировки эффективен для
- 60. void heapSort(int a[], int size) { int i, temp; // строим пирамиду for (i = size
- 62. Скачать презентацию