Сортировка матриц

В алгоритме используются  два цикла. Внешний проходится N − 1 раз. Это гарантирует, что даже в худшем случае каждый элемент будет находиться на своем месте. В этом цикле устанавливается (смещается) граница между отсортированной и неотсортированной частями структуры данных.

Во внутреннем цикле выполняются непосредственно операции сравнения и перестановки. Перестановка элементов производится методом "трёх вёдер": содержимое первого элемента помещается в буферную переменную, на его место помещается содержимое второго элемента, на место которого помещается из буфера "старое" содержимое первого элемента. Количество проходов внутреннего цикла в каждом следующем проходе внешнего цикла уменьшается (от N−1 до 1). Считается, что в среднем число проходов внутреннего цикла равно N/2. Исходный массив d, c, a, b в процессе работы программы будет изменяться следующим образом:

d, c, a, b

a, d, c, b

a, b, d, c

a, b, c, d

Рассматриваемый вариант алгоритма  всегда выполняет (N − 1)N/2 или (N² − N)/2 операций сравнения, так как внешний цикл выполняется N − 1 раз, а внутренний N/2.

Число перестановок зависит от степени предварительной упорядоченности массива: в лучшем случае перестановки не выполняются (массив уже отсортирован в нужном направлении, поэтому число перестановок равно 0). В среднем случае выполняется (N − 1)N/4 = (N² − N)/4 перестановок (т.е. число сравнений пополам, число операций присваивания оказывается утроенным и равным 3(N − 1)N/4)). В худшем случае (массив отсортирован в обратном направлении) выполняется (N − 1)N/2 = (N² − N)/2 перестановок (или 3(N − 1)N/2 операций присваивания).

Из-за наличия в формулах компонента N² пузырьковая сортировка относится к N-квадратичным алгоритмам (рисунок 1). При работе с большими структурами данных (массивами или связными списками) пузырьковая сортировка неэффективна.

 

Рисунок 1 – Зависимость времени от количества

элементов в структуре данных

 

Считается, что пузырьковая сортировка является "учебной", но в реальности она может применяться для  упорядочения массивов очень малого размера (3 − 7 элементов) в различных  алгоритмах обработки сигналов.

 

 

 

2. Сортировка выбором

Здесь сочетаются 2 процесса − поиск  и обмен. В структуре данных (массиве или списке) ищется наименьший (или наибольший) элемент и меняется местами с первым (или с последним, в зависимости от направления упорядоченности). Затем из оставшихся N-1 элементов ищется наименьший и меняется местами со вторым. Процесс повторяется до тех пор, пока нечего будет переставлять (т.е. пока структура данных не исчерпается).

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

Фактически в этих процедурах во внешнем цикле устанавливается нижняя граница интервала анализа, и элемент с таким индексом принимается за опорный. Во внутреннем цикле каждый из оставшихся элементов сравнивается с опорным, и если условие сравнения выполняется, то найденный локальный минимум фиксируется в буфере (принимается за новый опорный). Эффективность алгоритма повышается за счёт разнесения операции обмена по разным циклам (по сравнению с пузырьковой сортировкой). Исходный массив d, c, a, b будет меняться следующим образом:

d, с, a, b

a, с, d, b

a, b, d, c

a, b, c, d

Этот алгоритм является N-квадратичным. Внешний цикл выполняется N − 1 раз, внутренний − N/2 раз, каждая полная перестановка требует трех операций присваивания. Число операций сравнения равно (N²−N)/2; число операций присваивания: N−1 - в лучшем случае; N(log₂N+y) - в среднем случае; N²/4+3(N−1) - в худшем случае (y~0,577216 − константа Эйлера). Другой, более простой, но менее эффективный вариант реализации выполняет 3(N−1) присваиваний в лучшем случае.

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

К модификациям этого алгоритма относится пирамидальная сортировка. Существует также двунаправленный вариант сортировки выбором, в котором на каждом проходе отыскиваются и устанавливаются на свои места и минимальное, и максимальное значения.

 

3. Сортировка вставками

Сортировка вставками — простой алгоритм сортировки. Хотя этот алгоритм сортировки уступает в эффективности более сложным (таким как быстрая сортировка), у него есть ряд преимуществ:

• эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;
• эффективен на наборах данных, которые уже частично отсортированы;
• это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);
• может сортировать список по мере его получения;
• использует O(1) временной памяти, включая стек.

На каждом шаге алгоритма  мы выбираем один из элементов входных       

Данных и вставляем  его на нужную позицию в уже  отсортированном списке, до      тех пор пока набор входных  данных не будет исчерпан. Выбор  очередного                            элемента, выбираемого из исходного  массива, произволен; может использоваться  

      практически  любой алгоритм выбора.

Пример:

const N=255;            type array_type=array [1..N] of integer;       procedure InsertSort(var x:array_type);       var i, j, buf:integer;          begin             for i:=2 to N do           begin            buf:=x[i];            j:=i-1;             while (j>=1) and (x[j]>buf) do         begin            x[j+1]:=x[j];            j:=j-1;              end;            x[j+1]:=buf;             end;             end;

 

 

4. Сортировка Хоара

В настоящее время этот метод сортировки считается наилучшим. Он базируется на пузырьковом методе. В его основе лежит принцип разбиения. Эту сортировку также называют быстрой сортировкой. Метод был разработан в 1962 году профессором Оксфордского университета Чарльзом Хоаром. При программировании эффективно применение рекурсии.

Принцип работы алгоритма при упорядочении массива A из N элементов по возрастанию: значение какого-нибудь элемента, обычно центрального, записывается в переменную X, затем просматриваются элементы массива. При движении слева направо ищется элемент, который больше или равен X, а при движении справа налево ищется элемент, меньший X или равный ему. Найденные элементы меняются местами, и продолжается встречный поиск.

После этого массив окажется разделенным на две части. В первой находятся элементы, меньшие либо равные X, а справа - большие либо равные X. Для обоих подмассивов выполняется следующее: если в подмассиве более двух элементов, для него рекурсивно запускается та же процедура. Процедура разделения массива показана на рисунке 2.

 

 

 

 

  i                                    j                                             i                        j       

            исходное положение                                    положение первого обмена

                     указателей

 

 

 

 

               i           j                                                               i           j   

        положение  второго обмена                                      конец процедуры

 

Рисунок 2 – Процедура разделения массива

 

Выбор среднего значения можно  делать или случайно, или поиском некоторого среднего значения, например, стоящего посредине массива или выбрав действительно средний по значению элемент (требуется дополнительные предварительные вычисления).

Для оптимальной сортировки в качестве опорного элемента следует выбрать элемент, расположенный точно в середине диапазона значений текущего подмассива. Однако для большинства наборов данных поиск такого элемента может вылиться в самостоятельную сортировку.

Несмотря на всеобщую признательность, быстрая сортировка обладает целым рядом недостатков. Ее эффективность проявляется не для всех массивов Например, если выбираемое центральное значение оказывается совпадающим с максимальным значением, то быстрая сортировка превращается в самую медленную.[6]

 

 

5. Сортировка Шелла

        Сортировка  Шелла получила свое название  по имени ее создателя Д.Л.Шелла.  Недостаток метода сортировки "пузырьком" - работа с рядом стоящими элементами. В результате, элементы, которым надо "добраться" с одного конца массива до другого, делают это крайне долго. Метод Шелла аналогичен методу сортировки "пузырьком", однако работает с далеко отстоящими друг от друга элементами массива

программа:

  const N=10; {Количество элементов массива}

  var a: array[1..N] of integer; {массив}

      p: boolean; {флаг наличия перестановки}                                                                                    l,d,i,j: integer; {служебные переменные}

  ...........

d:=N div 2;{Расстояние между обрабатываемыми элементами массива,на каждом этапе алгоритма уменьшается в 2 раза вплоть до 0,когда происходит останов алгоритма}

while d>0 do

begin

  for j:=1 to N-d do {Перебор всех пар элементов массива,

      расстояние между которыми равно d}

  begin

    l:=j {запоминаем индекс текущего элемента}

    repeat

      p:=false; {пока элементы не переставлялись}

      if a[l]<a[l+d] then begin {если порядок нарушен, то}

        c:=a[l];a[l]:=a[l+d];a[l+d]:=c; {меняем местами элементы массива}

        l:=l-d;                                                                                                                   {перейдём к той паре, в которую входит меньший из переставленных элементов}                                                                                                                p:=true; {запомним, что была перестановка}                                                        end;                                                                                                                            until (l<=1) and p; {продолжаем, пока идут перестановки и не произошёл выход за пределы массива}                                                                                            end;                                                                                                                                       d:=d div 2;{Уменьшим расстояние между сравниваемыми элементами в 2 раза}      end;[1,7]

6. Поразрядная  сортировка

Алгоритм поразрядной  сортировки позволяет в некоторых  случаях достигать большей производительности и экономичности, чем другие алгоритмы. Особенность его в том, что  элементы не сравниваются друг с другом.

Поразрядная сортировка подразумевает  следующее: сначала элементы сортируются  по своему младшему (последнему) разряду, затем следующему (предпоследнему) и так далее до старшего разряда, первого.

На каждой своей итерации алгоритм включает 2 этапа: распределение и сборка.      Скорость работы алгоритмы определяется тем, что количество проходов по всем элементам исходного списка (например, массива) равно максимальному количеству разрядов в элементе. Если сортируются числа, то количество разрядов будет равно количеству десятичных разрядов этого числа, например: 27 - количество разрядов 2, 487 - количество разрядов 3 и т.д. В случае же сортировки текстовых строк количество разрядов будет определяться количеством букв в строке. Перед сортировкой необходимо определить 2 величины: максимальное количество разрядов в сортируемых величинах, по-другому - количество разрядов в самом длинном ключе, и количество возможных значений одного разряда ключа (сортируемого элемента). Так, для десятичных чисел оно равно 10, для шестнадцатеричных - 16, для строки это будет количество букв в алфавите.

Сам алгоритм работает следующим образом: создаются вспомогательные списки - "карманы", число которых равно количеству разрядов в самом длинном ключе, т.е. на каждое возможное значение разряда элемента - по карману. На первом проходе элементы исходной последовательности помещаются в эти карманы (списки) по их младшему разряду, т.е. по самому правому числу. Какой этот самый младший разряд у элемента, в такой карман этот элемент и помещается.

Далее происходит сборка: все карманы последовательно соединяются один за другим, в результате чего все элементы располагаются уже в порядке возрастания (или убывания) значения последнего разряда.

 Таким образом выполняется проход алгоритма, соответствующий крайнему правому разряду ключа. На следующем проходе элементы из уже обновленной последовательности распределяются по карманам в соответствии с их вторым разрядом и так далее до самого старшего, максимального разряда ключа. [8]

На рисунке 4 представлена поразрядная сортировка последовательности чисел 523, 153, 88, 554, 235 по возрастанию.

 

                 Исходная                                                          первый проход