2. Обменная сортировка
2.1. Метод пузырька
Сортировка простыми обменами, сортиро́вка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов.
Сложность алгоритма: O(n²).
Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяется сортировка вставками.
Алгоритм
Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.
После нулевого прохода по массиву "вверху" оказывается самый "легкий" элемент - отсюда аналогия с пузырьком. Следующий проход делается до второго сверху элемента, таким образом второй по величине элемент поднимается на правильную позицию...
Делаем проходы по все уменьшающейся нижней части массива до тех пор, пока в ней не останется только один элемент. На этом сортировка заканчивается, так как последовательность упорядочена по возрастанию.
Алгоритм имеет следующий вид.
2.2. Модификация метода пузырька
Рассмотрим ситуацию, когда на каком-либо из проходов не произошло ни одного обмена. Что это значит?
Это значит, что все пары расположены в правильном порядке, так что массив уже отсортирован. И продолжать процесс не имеет смысла (особенно, если массив был отсортирован с самого начала!).
Итак, первое улучшение алгоритма заключается в запоминании, производился ли на данном проходе какой-либо обмен. Если нет - алгоритм заканчивает работу.
Процесс улучшения можно продолжить, если запоминать не только сам факт обмена, но и индекс последнего обмена k. Действительно: все пары соседих элементов с индексами, меньшими k, уже расположены в нужном порядке. Дальнейшие проходы можно заканчивать на индексе k, вместо того чтобы двигаться до установленной заранее верхней границы i.
Качественно другое улучшение алгоритма можно получить из следующего наблюдения. Хотя легкий пузырек снизу поднимется наверх за один проход, тяжелые пузырьки опускаются с минимальной скоростью: один шаг за итерацию. Так что массив 2 3 4 5 6 1 будет отсортирован за 1 проход, а сортировка последовательности 6 1 2 3 4 5 потребует 5 проходов. Чтобы избежать подобного эффекта, можно менять направление следующих один за другим проходов. Получившийся алгоритм иногда называют "шейкер-сортировкой".
Сетевые ресурсы:
Визуальные представления метода можно посмотреть на следующих ресурсах:
1. http://algolist.ru/sort/bubble_sort.php
2. http://www.sorting-algorithms.com – анимационное представление.
2.3. Быстрая сортировка
Быстрая сортировка (англ. quicksort) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром в 1960 году – является одним из наиболее быстрых известных универсальных алгоритмов (в среднем O(n log n) обменов при упорядочении n элементов).
Метод основан на подходе "разделяй-и-властвуй". Общая схема алгоритма такова:
1) из массива выбирается некоторый опорный элемент;
2) запускается процедура разделения массива, которая перемещает все ключи, меньшие, либо равные опорному элементу, влево от него, а все ключи, большие, либо равные – вправо;
3) теперь массив состоит из двух подмножеств, причем левое меньше, либо равно правого;
4) для обоих подмассивов: если в подмассиве более двух элементов, рекурсивно запускаем для него ту же процедуру.
В конце получится полностью отсортированная последовательность
Рассмотрим алгоритм более детально:
Исходным является массив А с номерами элементов от First до Last. В алгоритме используются еще два индекса массива, обозначенные как Index и ContrIndex. Первый из них всегда указывает на переставляемый элемент, а второй — на элемент, который сравнивается по значению с переставляемым. В процессе вычислений применяются переменная h (равная либо 1, либо -1) - шаг движения индексов навстречу друг другу, используемая для обозначения направления движения индекса ContrIndex, и логическая переменная Condition (равная либо TRUE, либо FALSE), используемая для изменения условия сравнения на противоположное при обратном движении индекса ContrIndex.
Шаг 1. Пока Index не равно ContrIndex, делаются шаги: Шаг 2а - Шаг 2b.
Шаг 2а. Если справедливо ((A[Index]>A[ContrIndex])=Condition), то переставляются как сами элементы, на которые указывают Index и ContrIndex, (Val:=A[Index], A[Index]:=A[ContrIndex], A[ContrIndex]:=Val), так и сами вспомогательные индексы массивов (Val:=Index, Index:=ContrIndex, ContrIndex:=Val). Затем меняется направление движения (h:= -h) и условие сравнения (Condition: = not Condition). В процессе таких перестановок слева от переставляемого элемента всегда будут находиться меньшие значения, а справа - большие значения.
Шаг 2b. Сдвигается вспомогательный индекс массива ContrIndex навстречу индексу Index , т.е. ContrIndex:= ContrIndex + h.
Шаг 3. Перед выполнением этого шага индексы Index = ContrIndex и элемент A[Index] находится на нужном месте. Т.е. исходный массив разбит на три части: часть массива до этого элемента, значения в котором меньше величины A[Index], часть массива после этого элемента с значениями большими значения A[Index] и сам этот элемент A[Index]. Поэтому для дальнейшего упорядочивания массива достаточно рекурсивно обратиться к алгоритму быстрой сортировки два раза: для первой и второй частей массива. Т.к. длина сортируемых участков массива уменьшается, то в итоге алгоритм конечен и после применения алгоритма массив будет полностью отсортирован.
Рис. 1. Блок-схема быстрой сортировки
Рассмотрим работу процедуры для массива a[0]...a[6] и опорного элемента p = a[3].
Теперь массив разделен на две части: все элементы левой меньше либо равны p, все элементы правой - больше, либо равны p. Разделение завершено.
Оценка эффективности:
QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (его варианты известны как «Пузырьковая сортировка» и «Шейкерная сортировка»), известного, в том числе, своей низкой эффективностью. Принципиальное отличие состоит в том, что в первую очередь меняются местами наиболее удалённые друг от друга элементы массива. Любопытный факт: улучшение самого неэффективного прямого метода сортировки дало в результате самый эффективный улучшенный метод.
Лучший случай. Для этого алгоритма самый лучший случай — если в каждой итерации каждый из подмассивов делился бы на два равных по величине массива. В результате количество сравнений, делаемых быстрой сортировкой, было бы равно значению рекурсивного выражения CN = 2CN/2+N. Это дало бы наименьшее время сортировки.
Среднее. Даёт в среднем O(n lg n) обменов при упорядочении n элементов. В реальности именно такая ситуация обычно имеет место при случайном порядке элементов и выборе опорного элемента из середины массива либо случайно.
На практике быстрая сортировка значительно быстрее, чем другие алгоритмы с оценкой O(n lg n), по причине того, что внутренний цикл алгоритма может быть эффективно реализован почти на любой архитектуре. 2CN/2 покрывает расходы по сортировке двух полученных подмассивов; N — это стоимость обработки каждого элемента, используя один или другой указатель. Известно также, что примерное значение этого выражения равно CN = N lg N.
Худший случай. Худшим случаем, очевидно, будет такой, при котором на каждом этапе массив будет разделяться на вырожденный подмассив из одного опорного элемента и на подмассив из всех остальных элементов. Такое может произойти, если в качестве опорного на каждом этапе будет выбран элемент либо наименьший, либо наибольший из всех обрабатываемых.
Худший случай даёт O(n²) обменов, но количество обменов и, соответственно, время работы — это не самый большой его недостаток. Хуже то, что в таком случае глубина рекурсии при выполнении алгоритма достигнет n, что будет означать n-кратное сохранение адреса возврата и локальных переменных процедуры разделения массивов. Для больших значений n худший случай может привести к исчерпанию памяти во время работы алгоритма. Впрочем, на большинстве реальных данных можно найти решения, которые минимизируют вероятность того, что понадобится квадратичное время.
Наглядный пример работы алгоритма: http://upload.wikimedia.org/wikipedia/commons/6/6a/Sorting_quicksort_anim.gif
Литература:
Дональд Кнут Искусство программирования, том 3. Сортировка и поиск. 2-е изд. — М.: «Вильямс», 2007.
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; │ │ │ │
│ │ │ └────────────────────────┘ │ │ │
│ │ └────────────────────────────────────┘ │ │
│ └─────────────────────────────────────────────┘ │
└───────────────────────────────────────────────────────┘
Рассматриваемый алгоритм существенно отличается от других.
Во-первых, он совсем не использует сравнений сортируемых элементов.
Во-вторых, ключ, по которому происходит сортировка, необходимо разделить на части, разряды ключа. Например, слово можно разделить по буквам, число - по цифрам...
До сортировки необходимо знать два параметра: k и m, где
• k - количество разрядов в самом длинном ключе
• m - разрядность данных: количество возможных значений разряда ключа
При сортировке русских слов m = 33, так как буква может принимать не более 33 значений. Если в самом длинном слове 10 букв, k = 10.
Аналогично, для шестнадцатиричных чисел m=16, если в качестве разряда брать цифру, и m=256, если использовать побайтовое деление.
Эти параметры нельзя изменять в процессе работы алгоритма. В этом - еще одно отличие метода от остальных.
Список используемых источников:
1. http://algolist.manual.ru/sort/radix_sort.php
2. Роберт Седжевик – Фундаментальные Алгоритмы С++
3. http://wiki-linki.ru/Page/190151
4. http://dmtsoft.ru/bn/345/as/oneaticleshablon/
5. http://ru.wikibooks.org/wiki/Примеры_реализации_поразрядной_сортировки
2.5. Параллельная сортировка Бэтчера
Суть – происходит слияние пар отсортированных подпоследовательностей. Проблема – как формировать эти пары.
Алгоритм сортировки Бэтчера не является наиболее эффективным алгоритмом сортировки, однако он обладает одним важным компенсирующим качеством: все сравнения и/или обмены, определяемые данной итерацией алгоритма можно выполнять одновременно. С такими параллельными операциями сортировка осуществляется за 
Например, 1024 элемента можно рассортировать методом Бэтчера всего за 55 параллельных шагов. Схема сортировки Бэтчера несколько напоминает сортировку Шелла, но сравнения выполняются по-новому, а потому цепочки операций обмена записей не возникает. Поскольку в алгоритме Бэтчера, по существу, происходит слияние пар рассортированных подпоследовательностей, его можно назвать обменной сортировкой со слиянием.
Алгоритм Бэтчера (обменная сортировка со слиянием). Записи перекомпоновываются в пределах того же пространства в памяти. После завершения сортировки их ключи будут упорядочены: Предполагается, что 
1)[начальная установка  .] Установить  , где  — наименьшее целое число, такое, что  . (Шаги 2-5 будут выполняться с  .)
2)[начальная установка  .] Установить  .
3)[цикл по  .] Для всех , таких, что  и  , выполнять шаг 4) Затем перейти к шагу 5. (Здесь через обозначена операция "поразрядное логическое И" над представлениями целых чисел и ; все биты результата равны 0, кроме тех битов, для которых в соответствующих разрядах и находятся 1. Так  .
К этому моменту d — нечётное кратное p (т.е. частное от деления d на p нечётно), а p — степень двойки, так что  . Отсюда следует, что шаг 4 можно выполнять при всех нужных значениях I в любом порядке или даже одновременно.)
4)[Сравнение/обмен  .] Если  , поменять местами записи  .
5)[Цикл по q.] Если q != p , установить  и возвратиться к шагу 3.
6)[Цикл по p ] (К этому моменту перестановка  будет p -упорядочена.) Установить  . Если p>0 , возвратиться к шагу 2.
Для получения алгоритма обменной сортировки, время работы которого меньше, чем необходимо выбирать для сравнения и обмена ключи, расположенные возможно дальше друг от друга. Эта идея уже была реализована в алгоритме сортировки Шелла вставок с убывающим шагом, однако в данном алгоритме сравнения выполняются по-другому.
Рассмотрим схему алгоритма. Здесь t= [logN] - наименьшее целое, равное или превышающее logN ( N>=2). Переменная d имеет смысл шага сортировки, то есть сравниваются ключи K[i] и K[i+d]. Через <-> обозначена операция обмена значений двух переменных.
На схеме алгоритма через & обозначена операция поразрядного И, то есть выполнение условия 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], ... , то есть сортировку Бэтчера можно назвать также обменной сортировкой со слиянием.
Время работы алгоритма t примерно оценивается формулой:  где a, b - неизвестные константы, зависящие от программной реализации алгоритма.
          
Список используемых источников:
1. http://pascal.proweb.kz/index.php?page=79
2. http://waidos32.narod.ru/otvet/1_44.html
3.http://techn.sstu.ru/TFI/site_tfi/TFI/PVS/material/murashev/programming/term2/books/sort.htm#_Toc38711143
4. http://www.viva64.com/ru/a/0032/
5. http://saod.narod.ru/saod2/List012.html
|
