2. Обменная сортировка Название этой группы методов произошло от основного типа опера- ций, используемого в алгоритмах - обмен двух элементов в файле свои- ми значениями. Эта операция используется и в других группах, поэтому классификацию нельзя признать вполне строгой, но данное разделение тем не менее является традиционным. Файл, подлежащий сортировке, в общем случае состоит из элементов-записей, включающих информационную часть и ключи, по которым производится упорядочение по возрастанию. Поскольку информационная часть почти не влияет на процесс сортиров- ки, будем предполагать, что файлы, используемые в примерах, состот только из элементов-ключей, а информационная часть записи отсутству- ет. 2.1. Метод пузырька Алгоритм довольно очевиден. Рассмотрим работу алгоритма на примере файла из 16 элементов: исх. проход 1 проход 4 проход 7 файл │ проход 2 │ проход 5 │ проход 8 │ │ │ проход 3 │ │ проход 6 │ │ проход 9 │ │ │ │ │ │ │ │ │ │ 703 ┌─>908 908 908 908 908 908 908 908 908 765 │ 703 ┌>897 897 897 897 897 897 897 897 677 │ 765 │ 703 ┌>765 703 703 703 703 703 703 612 │ 677 │ 765──┘ 703 765 765 765 765 765 765 509 │ 612 │ 677 677 677 677 677 677 677 677 154 │ 509 │ 612 ┌>653 653 653 653 653 653 653 426 │ 154 │ 509 │ 612 612 612 612 612 612 612 653 │ 426 │ 154 │ 509 ┌─>512 512 512 512 512 512 275 │ 653 │ 426 │ 154 │ 509 509 509 509 509 509 897 │ 275 │ 653──┘ 426 │ 154 ┌>503 503 503 503 503 170 │ 897──┘ 275 ┌>512─┘ 426 │ 154 ┌>426 426 426 426 908─┘ 170 ┌─>512──┘ 275 ┌>503─┘ 426─┘ 154 ┌>275 275 275 61 ┌─>512─┘ 170 503──┘ 275 275 275─┘ 154 ┌>170 170 512─┘ 61 ┌─>503 170 170 170 170 170─┘ 154 154 87 ┌─>503─┘ 61 ┌>87 87 87 87 87 87 87 503─┘ 87 87 ──┘ 61 61 61 61 61 61 61 Пары стоящих рядом элементов сравниваются, и если правый элемент оказывается меньше левого, то они меняются местами. Продолжая этот процесс циклически, мы в конце концов придем к отсортированному фай- лу.Файл расположен вертикально снизу вверх, чтобы эффект всплывающе- го пузырька выглядел более наглядно. Элементы с большим значением ключа "всплывают" наверх, после последовательных сравнивнений с со- седними элементами. Алгоритм имеет следующий вид. b=N; while ( b ╪ 0 ) ┌───────────────────────────────────────────┐ │ t=0; │ │ for j=1 to b-1 do │ │┌────────────────────────────────────────┐ │ ││ ┌───────────────┐ │ │ ││ │ │ │ │ через <-> обозначена ││ if ( k[j] > k[j+1] ) │ k[j]<->k[j+1]│ │ │ операция обмена ││ │ t=j; │ │ │ значениями двух ││ └───────────────┘ │ │ переменных │└────────────────────────────────────────┘ │ │ b=t; │ └───────────────────────────────────────────┘ Время работы алгоритма t примерно оценивается формулой: t=a*N¤ + b*N где a,b - неизвестные константы, зависящие от программной реализа- ции алгоритма. 2.2.Модификация метода пузырька Модификация метода пузырька состоит в том, что файл можно прос- матривать как с начала до конца, так и с конца до начала поперемен- но. Это несколько сокращает число перемещений элементов. Схема пере- мещений элементов будет в этом случае иметь следующий вид. исх. проход 1 проход 4 проход 7 файл │ проход 2 │ проход 5 │ │ │ │ проход 3 │ │ проход 6 │ │ │ │ │ │ │ │ │ 703 ┌─>908 908 908 908 908 908 908 765 │ 703─┐ 765 ┌─>897 897 897 897 897 677 │ 765 └─>703 │ 765 765 765 765 765 612 │ 677 677 │ 703 703 703 703 703 509 │ 612 612 │ 677 677 677 677 677 154 │ 509 509 │ 612 612 ┌>653 653 653 426 │ 154─┐ 426 │ 509 509 │ 612 612 612 653 │ 426 │ 653 │ 426─┐ 653─┘ 509─┐ 512 512 275 │ 653 │ 275 │ 653 └─>426 ┌>512 └>509 509 897 │ 275 │ 897─┘ 275─┐ 512─┘ 426─┐ 503 503 170 │ 897 │ 170 ┌─>512 └─>275 ┌>503 └>426 426 908─┘ 170 │ 512─┘ 170─┐ 503─┘ 275 275 275 61 ┌─>512 └─>154 ┌─>503 └─>170 170 170 170 512─┘ 61 ─┐ 503─┘ 154 154 154 154 154 87 ┌─>503 │ 87 87 87 87 87 87 503─┘ 87 └─>61 61 61 61 61 61 Проход 1 осуществлялся с начала в конец, проход 2 - с конца в на- чало, проход 3 снова с начала в конец и т.д. . Как видно из таблицы, этот алгоритм потребовал на 2 прохода меньше, чем исходный. Время работы алгоритма t примерно оценивается формулой: t=a*N¤ + b*N где a,b - неизвестные константы, зависящие от программной реализа- ции алгоритма. 2.3. Быстрая сортировка. Основная стратегия ускорения алгоритмов сортировка - обмены между как можно более дальними элементами исходного файла - в методе быст- рой сортировки реализована за счет того, что один из ключей в исход- ном файле используется для разделения его на два подфайла так, чтобы слева от выбранного элемента находились только элементы с меньшими ключами, а справа - только с большими. Элемент, разделяющий файл, помещается между его двумя подфайлами и процедура выполняется рекур- сивно для каждой половины до тех пор, пока в очередном новом подфай- ле не окажется меньше, чем М элементов, где М - заранее выбранное число. Рассмотрим схему алгоритма. l=1;r=N; ║ ╔>═╬══════<══════════════════════════════════════════════════════════╗ ║ if(r-l < M) ┌─────────────────────────────────────────────────────┐║ ║ ║ │ Отсортировать часть файла K[l] ... K[r] простыми │║ ║ ║ │ вставками │║ ║ ║ │ if (стек пуст) Конец алгоритма. │║ ║ ║ │ ┌─────────────────────────────────┐ │║ ║ ║ │ else │взять из стека элемент (l',r') ╞>═╪╝ ║ ║ │ │l=l' ; r=r' ; │ │ ║ ║ │ └─────────────────────────────────┘ │ ║ ║ └─────────────────────╥───────────────────────────────┘ ║ ╚>═╦═<═══════════════════════════╝ ║ ┌───╨──────┬─────────┐ ║ │Выбор Х │ X=K[l]; │ ║ └──────────┴─────────┘ ║ i=l; j=r; ║ ║ ║ ╠═══════════<════╦═══<═══════\ /═>══╦════════<═══════╗ ║ if(X╝ \ / if(X>K[i]) i=i+1═>╝ ║ ┌────────────────┐ /\ ┌───────────────┐ ║ if(j>i)│K[i]=K[j];i=i+1;╞═>═/ \ if(j>i) │K[j]=K[i];j=j-1│ ║ └────────────────┘ \ └╥──────────────┘ ║ else K[i]=X ═>═╗ \══<════════════╝ ║ ║ else K[j]=X;i=j;═>╗ ║ ║ ║ ║ ┌────────╨────────────────────────────────────────────╨───┐ ║ else │ Поместить в стек большую половину файла: либо (l,i-1), │ ║ │ либо (i+1,r) и установить для оставшейся половины либо │ ║ │ l=i+1, либо r=i-1 соответственно. │ ║ └───────────────────────────────────────╥─────────────────┘ ╚═════════════════════════════════<════════════════╝ Сортировка подфайлов, содержащих меньше чем М элементов, выполня- ется каким-либо простым методом, например простыми вставками. Таким образом, реализация метода зависит от двух параметров: значения М и способа выбора элемента, который предназначен для разделения файла на две части. Блок выбора Х в простейшем случае формулируется как X=K[l], одна- ко это может привести к крайне неэффективному алгоритму. Наиболее простое лучшее решение - выбирать Х как случайный ключ из диапазона K[l] ... K[r] и обменять его с K[l]. Ниже быстрая сортировка проиллюстрирована примером файла из 16 элементов. Квадратными скобками [] выделены подфайлы, подлежащие последующей сортировке. В рамку взяты элементы, принятые на данном шаге за Х. M принято за 1 - наименьшее возможное значение, то есть в данном случае алгоритм не переходит к другому методу для коротких отрезков, меньших M. Для первого шага показаны направления пересылки в соответсвии со схемой алгоритма. Числа на линиях определяют поря- док, в котором выполняются пересылки . N │ шага│ Состояние файла ────┼───────────────────────────────────────────────────────────────── │ ┌──<─5───────┐ │ │┌─>─4───────┼──────┐ │ ┌──<─3─┼┼───────────┼──────┼┐ │ │┌─>─2─┼┼───────────┼──────┼┼───┐ │ ┌─<─1──┼┼─────┼┼───────────┼──────┼┼──┐│ │ ┌─┴─┐ ││ ││ ┌>─6┐│ ││ ││ исх.│ │503│ 87 512 61 908 170 897 275 653 426 154 509 612 677 765 703 │ └───┘ │┌ ┌───┐ ┐ ┌ ┐ 1 ││ │154│ 87 426 61 275 170│503│897 653 908 512 509 612 677 765 703│ │└ └───┘ ┘ └ ┘ │┌ ┌──┐ ┐ ┌ ┐ ┌ ┐ 2 ││ │61│ 87│154│426 275 170│503│897 653 908 512 509 612 677 765 703│ │└ └──┘ ┘ └ ┘ └ ┘ │ ┌ ┌───┐ ┐ ┌ ┐ 3 │ 61 87 154│ │426│ 275 170│503│897 653 908 512 509 612 677 765 703│ │ └ └───┘ ┘ └ ┘ │ ┌ ┌───┐ ┐ ┌ ┐ 4 │ 61 87 154│ │170│ 275│426 503│897 653 908 512 509 612 677 765 703│ │ └ └───┘ ┘ └ ┘ │ ┌ ┌───┐ ┐ 5 │ 61 87 154 170 275 426 503│ │897│ 653 908 512 509 612 677 765 703│ │ └ └───┘ ┘ │ ┌ ┌───┐ ┐ 6 │ 61 87 154 170 275 426 503│ │703│ 653 765 512 509 612 677│ 897 908 │ └ └───┘ ┘ │ ┌ ┌───┐ ┐ 7 │ 61 87 154 170 275 426 503│ │677│ 653 612 512 509 │ 703 765 897 908 │ └ └───┘ ┘ │ ┌ ┌───┐ ┐ 8 │ 61 87 154 170 275 426 503│ │509│ 653 612 512 │ 677 703 765 897 908 │ └ └───┘ ┘ │ ┌ ┌───┐ ┐ 9 │ 61 87 154 170 275 426 503 509│ │653│ 612 512 │ 677 703 765 897 908 │ └ └───┘ ┘ │ ┌ ┌───┐ ┐ 10 │ 61 87 154 170 275 426 503 509│ │512│ 612 │ 653 677 703 765 897 908 │ └ └───┘ ┘ │ 10 │ 61 87 154 170 275 426 503 509 512 612 653 677 703 765 897 908 │ Время работы алгоритма t примерно оценивается формулой: t=a*N*lgN + b*N где a,b - неизвестные константы, зависящие от программной реализа- ции алгоритма. 2.4. Обменная поразрядная сортировка Данный метод использует двоичное представление ключей. Файл сор- тируется последовательно по битам двоичного представления ключей, начиная со старшего. Ключи, имеющие значение данного бита, равное нулю, ставятся в левую половину файла, а ключи со значением бита 1 - в правую. Ниже приведена схема алгоритма поразрядной сортировки. l=1; r=N; b=1; ║ ╔══>═╬══<══════════════════════════════════════════════╗ ║ ║ ╔═══════════<═══════════════════════════╬═══════════════╗ ║ ║ ┌──╫─────────────────────────────────────┐ ║ ║ ║ ║ │ if(стек пуст) Конец; │ ║ ║ ║ if(l=r) │ ┌──────────────────────────────┐ │ ║ ║ ║ │ else │l=r+1; │ │ ║ ║ ║ │ │Взять из стека элемент (r',b')╞>═╪═╝ ║ ║ │ │r=r'; b=b'; │ │ ║ ║ │ └──────────────────────────────┘ │ ║ ║ └────────────────────────────────────────┘ ║ ║ i=l; j=r; ║ ║ ┌────────────────────────────────────────┐ ║ ║ ╔═if(b(K[i])=1)│j=j-1;══════════<═══════════╗ │ ║ ║ ║ │ ┌──────────────────╫─────────┐ │ ║ ║ ║ │if(i<=j) │ if(b(K[j+1])=1) ═╝ │ │ ║ ║ ║ │ │ ┌───────────────┐ │ │ ║ ║ ║ │ │ else │ K[i]<->K[j+1] ╞>═╗ │ │ ║ ║ ║ │ │ └───────────────┘ ║ │ │ ║ ║ ║ │else ═>╗ └─────────────────────────╫──┘ │ ║ ║ ║ └───────╫───────────────────────────╫────┘ ║ ║ ╚════<═════════════╗ ║ ║ ║ ║ ┌──────────╫───╨───────────────────────────╨────────────┐ ║ ║ else │ i=i+1; ║ │ ║ ║ │ if(i<=j)═╝ │ ║ ║ │ ┌─────────────────────────────────────────────┐ │ ║ ║ │ │ b=b+1; │ │ ║ ║ │ else │ if(b>m) ═>══════════════════════════════════╪══╪════╝ ╚════<════╪══════╪══════════════════╦═<═╦══════════════<═╗ │ │ │ │ if(j╝ ║ ║ │ │ │ │ ┌────────────── ╫────────────────╫───┐ │ │ │ │ else │if(j=l) l=l+1═>╝ ║ │ │ │ │ │ │ ┌────────────────────────┐ ║ │ │ │ │ │ │else │ Поместить в стек (r,b);╞>╝ │ │ │ │ │ │ │ r=j; │ │ │ │ │ │ │ └────────────────────────┘ │ │ │ │ │ └────────────────────────────────────┘ │ │ │ └─────────────────────────────────────────────┘ │ └───────────────────────────────────────────────────────┘ Пример использования этого алгоритма приведен ниже. Значения эле- ментов файла даны в 16-ричной системе счисления.Квадратные скобки [] использованы для обозначения подфайлов с одинаковым значением бита b (b=1 соответствует биту 10, считая справа). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 │l r b ───────────────────────────────────────────────────────────────┼─────── ┌─ ─┐│ │1F7 57 200 3D 38C AA 381 113 28D 1AA 9A 1FD 264 2A5 2FD 2BF││ 1 16 1 │ ─┐┌─ ││ │1F7 57 1FD 3D 9A AA 1AA 113││28D 381 38C 200 264 2A5 2FD 2BF││ 1 8 2 │ ─┐┌─ ││ ││ │AA 57 9A 3D││1FD 1F7 1AA 113││28D 381 38C 200 264 2A5 2FD 2BF││ 1 4 3 │ ─┐┌─ ││ ││ ││ │3D 57││9A AA││1FD 1F7 1AA 113││28D 381 38C 200 264 2A5 2FD 2BF││ 1 2 4 └─ ─┘│ ││ ││ ││ │ ││ ││ ││ 3D 57 │9A AA││1FD 1F7 1AA 113││28D 381 38C 200 264 2A5 2FD 2BF││ 3 4 4 │ ││ ││ ││ 3D 57 │9A AA││1FD 1F7 1AA 113││28D 381 38C 200 264 2A5 2FD 2BF││ 3 4 5 └─ ─┘│ ││ ││ │ ││ ││ 3D 57 9A AA│1FD 1F7 1AA 113││28D 381 38C 200 264 2A5 2FD 2BF││ 5 8 3 └─ ┌─ ││ ││ 3D 57 9A AA 113│1F7 1AA 1FD││28D 381 38C 200 264 2A5 2FD 2BF││ 6 8 4 └─ ┌─ ││ ││ 3D 57 9A AA 113 1AA│1F7 1FD││28D 381 38C 200 264 2A5 2FD 2BF││ 7 8 5 │ ││ ││ 3D 57 9A AA 113 1AA│1F7 1FD││28D 381 38C 200 264 2A5 2FD 2BF││ 7 8 6 │ ││ ││ 3D 57 9A AA 113 1AA│1F7 1FD││28D 381 38C 200 264 2A5 2FD 2BF││ 7 8 7 └─ ─┘└─ ││ ┌─ ││ 3D 57 9A AA 113 1AA 1F7 1FD │28D 381 38C 200 264 2A5 2FD 2BF││ 9 16 2 │ ─┐┌─ ││ 3D 57 9A AA 113 1AA 1F7 1FD │28D 2BF 2FD 200 264 2A5 ││2FD 381││ 9 14 3 │ ─┐┌─ ││ ││ 3D 57 9A AA 113 1AA 1F7 1FD │264 200││2FD 2BF 28D 2A5││2FD 381││ 9 10 4 └─ ─┘└─ ──┘└─ ─┘│ ┌─ ─┐┌─ ─┐│ 3D 57 9A AA 113 1AA 1F7 1FD 200 264│2A5 2BF 28D 2A5││38C 381││11 14 4 │ ││ ││ │ ─┐┌─ ││ ││ 3D 57 9A AA 113 1AA 1F7 1FD 200 264│28D 2BF 28D││2FD││38C 381││11 13 5 └─ ││ ││ ││ ┌─ ││ ││ ││ 3D 57 9A AA 113 1AA 1F7 1FD 200 264 28D│2BF 2A5││2FD││38C 381││12 13 6 └─ ─┘└─ ─┘└─ ││ ┌─ ││ 3D 57 9A AA 113 1AA 1F7 1FD 200 264 28D 2A5 2BF 2FD │38C 381││15 16 3 │ ││ 3D 57 9A AA 113 1AA 1F7 1FD 200 264 28D 2A5 2BF 2FD │38C 381││15 16 4 │ ││ 3D 57 9A AA 113 1AA 1F7 1FD 200 264 28D 2A5 2BF 2FD │38C 381││15 16 5 │ ││ 3D 57 9A AA 113 1AA 1F7 1FD 200 264 28D 2A5 2BF 2FD │38C 381││15 16 6 │ ││ 3D 57 9A AA 113 1AA 1F7 1FD 200 264 28D 2A5 2BF 2FD │38C 381││15 16 7 └─ ─┘│ 3D 57 9A AA 113 1AA 1F7 1FD 200 264 28D 2A5 2BF 2FD 38C 381 │17 - - Время работы алгоритма t примерно оценивается формулой: t=a*N*lgN + b*N где a,b - неизвестные константы, зависящие от программной реализа- ции алгоритма. 2.5. Параллельная сортировка Бэтчера Для получения алгоритма обменной сортировки, время работы которо- го меньше, чем N¤, необходимо выбирать для сравнения и обмена ключи, расположенные возможно дальше друг от друга. Эта идея уже была реа- лизована в алгоритме сортировки Шелла вставок с убывающим шагом, од- нако в данном алгоритме сравнения выполняются по-другому. ┌ ┐ Рассмотрим схему алгоритма. Здесь t= │lgN│ - наименьшее целое, равное или превышающее lgN ( N>=2). Переменная d имеет смысл шага сортировки, то есть сравниваются ключи K[i] и K[i+d]. Через <-> обо- значена операция обмена значений двух переменных. t-1 p = 2 t-1 ╔═>q = 2 ; r=0; d=p; ║ ║ ╔═══<════════════════════════════════════<══════╗ ║ for i=0 to N-d-1 таких, что i&p = r; ║ ║ ┌────────────────────────────────────────┐ ║ ║ │if(K[i+1] > K[i+d+1]) K[i+1]<->K[i+d+1] │ ║ ║ └────────────────────────────────────────┘ ║ ║ if(q=p) ║ ║ then ║ else ║ ║ ╔════<════╩════>═════════════════════════╗ ║ ║ ║ ║ ║ ║ p=p/2;(деление нацело) d=q-p; ║ ║ if(p<=0) Конец алгоритма; q=q/2; ║ ║ else═>╗ r=p; ║ ╚═══════╝ ╚═══>══╝ На схеме алгоритма через & обозначена операция поразрядного И, то есть выполнение условия i&p = r означает, что в цикле по i нужно вы- бирать только такие значения i, которые в одном разряде, изменяющем- ся в цикле по p (операция p=p/2 имеет смысл сдвига начального значе- ния 1 в разряде t-1), имеют снала значение 0 (поскольку r=0), а за- тем 1 (поскольку r=p). Проиллюстрируем работу алгоритма примером исходного файла из 16 элементов. Линиями соединены сравниваемые на данном шаге ключи. При d=1 происходит фактически слияние упорядоченных подфайлов K[1],K[3],K[5], ... и K[2],K[4],K[6], ... , то есть сортировку Бэт- чера можно назвать также обменной сортировкой со слиянием. │ p q r d │ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ───────────┼───────────────────────────────────────────────────────────── 8 8 0 8 │503 87 512 61 908 170 897 275 653 426 154 509 612 677 765 703 │ └───┼──┼───┼───┼──┼───┼───┼───┘ │ │ │ │ │ │ │ │ └──┼───┼───┼──┼───┼───┼───────┘ │ │ │ │ │ │ │ └───┼───┼──┼───┼───┼──────────┘ │ │ │ │ │ │ └───┼──┼───┼───┼───────────────┘ │ │ │ │ │ └──┼───┼───┼───────────────────┘ │ │ │ │ └───┼───┼───────────────────────┘ │ │ │ └───┼───────────────────────────┘ │ │ └───────────────────────────────┘ 4 8 0 4 │503 87 154 61 612 170 765 275 653 426 512 509 908 677 897 703 │ └───┼──┼───┼──┘ │ │ │ └───┼───┼───┼───┘ │ │ │ │ └──┼───┼──────┘ │ │ └───┼───┼───────┘ │ │ │ └───┼──────────┘ │ └───┼───────────┘ │ │ └──────────────┘ └───────────────┘ │ 4 4 4 4 │503 87 154 61 612 170 765 275 653 426 512 509 908 677 897 703 │ └───┼───┼───┼───┘ │ │ │ │ └───┼───┼───────┘ │ │ │ └───┼───────────┘ │ │ └───────────────┘ 2 8 0 2 │503 87 154 61 612 170 512 275 653 426 765 509 908 677 897 703 │ └───┼──┘ │ └───┼───┘ │ └───┼───┘ │ └───┼───┘ │ │ └──────┘ └───────┘ └───────┘ └───────┘ │ 2 4 2 6 │154 61 503 87 512 170 612 275 653 426 765 509 897 677 908 703 │ └───┼──────────┼───┼───┘ │ │ │ │ └──────────┼───┼───────┘ │ │ │ └───┼───────────────────┘ │ │ └───────────────────────┘ │ 2 2 2 2 │154 61 503 87 512 170 612 275 653 426 765 509 897 677 908 703 │ └───┼──┘ │ └───┼───┘ │ └───┼───┘ │ │ └──────┘ └───────┘ └───────┘ │ 1 8 0 1 │154 61 503 87 512 170 612 275 653 426 765 509 897 677 908 703 │ └──┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ │ 1 4 1 7 │61 154 87 503 170 512 275 612 426 653 509 765 677 897 703 908 │ └──────┼───────┼───────┼───┘ │ │ │ │ └───────┼───────┼───────────┘ │ │ │ └───────┼───────────────────┘ │ │ └───────────────────────────┘ │ 1 2 1 3 │61 154 87 503 170 512 275 612 426 653 509 765 677 897 703 908 │ └──────┼───┘ │ │ └───┼───┼───┘ │ │ │ │ └───────┼───┘ │ └───────┼───┘ │ │ └───────────┘ └───────────┘ │ 1 1 1 1 │61 154 87 275 170 426 503 509 512 653 612 703 677 897 765 908 │ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ │ │61 87 154 170 275 426 503 509 512 612 653 677 703 765 897 908 │ Время работы алгоритма t примерно оценивается формулой: t=a*N*(lgN)¤ где a,b - неизвестные константы, зависящие от программной реализа- ции алгоритма.