Лекция 11. Сортировка (1107986), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Сортировка методом «пузырька» (обменная).11.3.7.1. Алгоритм. Просматриваем массив int a[n], сравнивая каждый a[i - 1]с a[i] и меняя их местами, если a[i - 1] > a[i] («более легкие элементывсплывают: чем легче, тем выше»).11.3.7.2. Си-функция:/*Пузырьковая сортировка*/void bubble_sort(int *a, int n) {int i, j;int tmp;/*Основной цикл*/for(j = 1; j < n; ++j)for(i = n - 1; i >= j; --i) {if(a[i - 1] > a[i]){tmp = a[i - 1];a[i - 1] = a[i];a[i] = tmp;}}}11.3.7.3.

Общее количество сравнений (действий): n(n - 1)/2, так как внешний циклвыполняется (n - 1) раз, а внутренний – в среднем n/2 раза.11.3.7.4. Пузырьковая сортировка – алгоритм порядка n2: время ее работыпропорционально квадрату количества сортируемых элементов. Алгоритмсортировки с помощью максимумов тоже имеет порядок n2.11.3.8. Сортировка вставками./*Сортировка вставками */void insert_sort(int *a, int n) {int i, j;int tmp;/*Основной цикл*/for(j = 1; j < n; ++j) {tmp = a[j];for(i = j - 1; (i >= 0)&&(tmp < a[i]; i--) {a[i + 1] = a[i];a[i + 1] = a[i];}}Количество сравнений зависит от степени перемешанности массива a. Если массив aуже отсортирован, количество сравнений равно n - 1.

Если массив a отсортирован вобратном порядке (наихудший случай), количество сравнений имеет порядок n2.11.3.9. Сортировка методом Шелла (слияние с обменом).11.3.9.1. Метод. Сначала массив сортируется с шагом gap (достаточно большим),потом – с шагом gap /2 и т.д. и наконец с шагом 1. Примерпоследовательности шагов: 9, 5, 3, 2, 1. Впоследствии (где-нибудь на третьемкурсе) будет доказано, что метод Шелла не только сортирует, но сортируетбыстро – порядок этого алгоритма n1.2.(с) Кафедра системного программирования ф-та ВМК МГУ, 20104Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год.11.3.9.2.

Последовательности шагов, являющихся степенями двойки уменьшаютэффективность сортировки Шелла, так как увеличивается вероятностьмногократного сравнения одних и тех же пар. Но даже в этом случае алгоритмШелла сходится!11.3.9.3. Текст Си-программы сортировки Шелла (для последовательности шагов: 9, 5,3, 2, 1)./*Сортировка Шелла*/void Shell_sort(int *a, int n) {int i, j, k, gap;int x, g[5];g[0] = 9; g[1] = 5; g[2] = 3; g[3] = 2; g[4] = 1;/*Основной цикл*/for(k = 0; k < 5; k++) {gap = g[k];for(i = gap; i < n; ++i) {x = a[i];for(j = i - gap; (x < a[j])&&(j >= 0; j -= gap) {a[j + gap] = a[j];a[j] = x;}}}(с) Кафедра системного программирования ф-та ВМК МГУ, 20105.

Характеристики

Список файлов лекций