Содержание
- 2. Сортировка массивов Сортировка – это упорядочивание набора однотипных данных по возрастанию или убыванию. Ключ сортировки –
- 3. Оценка алгоритмов сортировки Существует множество различных алгоритмов сортировки. Все они имеют свои положительные и отрицательные стороны.
- 4. Оценка алгоритмов сортировки Сравнение происходит тогда, когда один элемент массива сравнивается с другим; обмен происходит тогда,
- 5. Оценка алгоритмов сортировки Поведение алгоритма сортировки. Поведение алгоритма сортировки называется естественным, если время сортировки минимально для
- 6. Оценка алгоритмов сортировки Различные сортировки массивов отличаются по быстродействию. Существуют простые методы сортировок, которые требуют порядка
- 7. Оценка алгоритмов сортировки Простые методы сортировки можно разделить на три основные категории: сортировка методом "пузырька" (простого
- 8. Сортировка методом "пузырька" (простого обмена) Алгоритм попарного сравнения элементов массива. Алгоритм состоит в повторяющихся проходах по
- 9. Сортировка методом "пузырька" (простого обмена) Проходы по массиву повторяются до тех пор, пока на очередном проходе
- 10. Сортировка методом "пузырька" (простого обмена) Рассмотрим идею метода на примере. Отсортируем по возрастанию массив из 5
- 11. Сортировка методом "пузырька" (простого обмена) Первый просмотр: рассматривается весь массив. i=1 5 4 8 2 9
- 12. Сортировка методом "пузырька" (простого обмена) Второй просмотр: рассматриваем часть массива с первого до предпоследнего элемента. i=1
- 13. Сортировка методом "пузырька" (простого обмена) Третий просмотр: рассматриваемая часть массива содержит три первых элемента. i=1 4
- 14. Сортировка методом "пузырька" (простого обмена) Четвертый просмотр: рассматриваем последнюю пару элементов. i=1 2 4 5 8
- 15. Сортировка методом "пузырька" (простого обмена) Итак, наш массив отсортирован. Этот метод также называют методом «пузырька». Название
- 16. Сортировка методом "пузырька" (простого обмена) //Описание функции сортировки методом "пузырька" void Sort_Obmen (int n, int A[])
- 17. Сортировка методом "пузырька" (простого обмена) if (A[i]>A[i+1]) { buf=A[i]; A[i]=A[i+1]; A[i+1]=buf; } }
- 18. Сортировка простым выбором Пусть исходный массив А состоит из 10 элементов: 5 13 7 9 1
- 19. Сортировка простым выбором 1-й шаг. Рассмотрим весь массив и найдем в нем максимальный элемент – 16
- 20. Сортировка простым выбором 2-й шаг. Рассмотрим часть массива – с первого до девятого элемента. Максимальный элемент
- 21. Сортировка простым выбором 3-й шаг. Уменьшим рассматриваемую часть массива на один элемент. Здесь нужно поменять местами
- 22. Сортировка простым выбором 4-й шаг. 5 4 7 9 1 8 2 10 13 16 5-й
- 23. Сортировка простым выбором 6-й шаг. 5 4 7 2 1 8 9 10 13 16 7-й
- 24. Сортировка простым выбором 8-й шаг. 2 4 1 5 7 8 9 10 13 16 9-й
- 25. Сортировка простым выбором Фрагмент программной реализации: void vibor(int A[],int n) { int i, j, k; int
- 26. Сортировка простым выбором k = i; for ( j = i+1; j { if (A[j] >=
- 27. Сортировка простым выбором item = A[k]; } } A[k] = A[i]; A[i] = item; } }
- 28. Сортировка простыми вставками Сортировка этим методом производится последовательно шаг за шагом. На i-ом шаге считается, что
- 29. Сортировка простыми вставками Затем выполняется вставка элемента A[i] на место j. На каждом шаге отсортированная часть
- 30. Сортировка простыми вставками Пусть требуется отсортировать массив из 10 элементов по возрастанию. 1-й шаг. 13 6
- 31. Сортировка простыми вставками 2-й шаг. 6 13 8 11 3 1 5 9 15 7 Возьмем
- 32. Сортировка простыми вставками 3-й шаг. 6 8 13 11 3 1 5 9 15 7 Следующий
- 33. Сортировка простыми вставками void vstavka (int A[],int n) { int i; for (i=0; i { int
- 34. Сортировка простыми вставками while((j>=0)&&(w { A[j+1]=A[j]; j--; } A[j+1]=w; } }
- 35. Быстрая сортировка Хоара Метод предложен Ч. Э. Р. Хоаром в 1962 году. Эффективность метода достаточно высокая,
- 36. Быстрая сортировка Хоара пусть это будет место k, такое, что слева от X были элементы массива,
- 37. Быстрая сортировка Хоара Дальнейшие действия состоят в независимой сортировке полученных частей по той же логике до
- 38. Быстрая сортировка Хоара Пример. Исходный массив состоит из 8 элементов: 8 12 3 7 19 11
- 39. Быстрая сортировка Хоара Продолжаем сортировку. Левая часть: (3) 4 7 (12 19 11 8 16) 3
- 40. Быстрая сортировка Хоара Правая часть: 3 4 7 (8) 11 (19 12 16) 3 4 7
- 41. Быстрая сортировка Хоара В приведенном алгоритме используется рекурсивная схема реализации, параметрами которой являются нижняя и верхняя
- 42. Быстрая сортировка Хоара Фрагмент программной реализации: void hoar_r(int A[],int m, int t) { int i=m; int
- 43. Быстрая сортировка Хоара if (A[i] else if (A[j]>x) j--; else { int z=A[i]; A[i]=A[j]; A[j]=z; i++;
- 45. Скачать презентацию