Лекция. Алгоритмы сортировки Под сортировкой
Простая сортировка обменами (пузырьковая)
жүктеу/скачать 0,94 Mb.
|
Алгоритмы сортировки
| Простая сортировка обменами (пузырьковая)
Классификация методов сортировки не вполне однозначна. Оба обсуждавшихся выше метода можно также рассматривать как сортировки обменами. Однако сейчас мы представим метод, в котором обмен двух элементов играет главную роль. Получающаяся простая сортировка обменами использует сравнение и обмен пар соседних элементов до тех пор, пока не будут отсортированы все элементы. Как и ранее в простой сортировке выбором, здесь выполняются повторные проходы по массиву, причем каждый раз наименьший элемент оставшегося множества просеивается в направлении левого конца массива. Если для разнообразия считать массив расположенным вертикально, а не горизонтально, и вообразить, что элементы – это пузырьки в сосуде с водой, причем их вес равен значению ключа, тогда проходы по массиву приводят к подъему пузырька на уровень, соответствующий его весу (см. табл. 2.3). Такой метод широко известен как пузырьковая сортировка. // BubbleSort; int i, j, x; for (i = 1; i<= n–1; i++) { for (j = n–1; j>= i; j--) { if (a[j–1] > a[j]) { x = a[j–1]; a[j–1] = a[j]; a[j] = x; } } } Этот алгоритм нетрудно улучшить. Пример в табл. 2.3 показывает, что последние три прохода не влияют на порядок элементов, так как они уже отсортированы. Очевидный способ улучшить алгоритм – запомнить, имел ли место хотя бы один обмен во время прохода. Тогда проход без обменов сигнализирует, что алгоритм может быть остановлен. Однако можно сделать еще одно улучшение, запоминая не только факт обмена, но и позицию (индекс) последнего обмена. Ясно, например, что все пары соседних элементов левее этого значения индекса (назовем его k) уже упорядочены. Поэтому последующие проходы могут останавливаться на этом значении индекса, вместо того чтобы продолжаться до i. Однако внимательный программист заметит любопытную асимметрию: если вначале только один пузырек стоит не на своем месте в «тяжелом» конце, то он доберется до своего места за один проход, а если такой пузырек стоит в «легком» конце, то он будет опускаться в свою правильную позицию только на один шаг за каждый проход. Например, массив 12 18 42 44 55 67 94 06 сортируется улучшенной пузырьковой сортировкой за один проход, а массив 94 06 12 18 42 44 55 67 требует семи проходов. Такая неестественная асимметрия наводит на мысль о третьем усовершенствовании: менять направление последовательных проходов. Получающийся алгоритм называют жүктеу/скачать 0,94 Mb. Достарыңызбен бөлісу:
|