# АЛГОРИТМЫ СОРТИРОВКИ

Введение
Пузырьковая сортировка/Пример
Сортировка выбором/Пример
Сортировка Шелла/Пример
Сортировка Хоора/Пример
QuickSort/Пример
Сортировка с помощью двоичного дерева/Пример
Сортировка с помощью массива индексов/Пример
Какую сортировку выбрать

## Введение

Этот текст призван стать кратким обзором нескольких алгоритмов сортировки.

Солидная часть статьи взята из одноименного текста С.Курковского, что-то дописано, что-то поскипано, преобразовано в html, добавлены пара алгоритмов с картинкой, примеры отлажены до рабочего состояния.

Итак, каждый алгоритм сортировки состоит из трех основных частей:

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

    #define less(x,y)  (x < y)              // функция сравнения элементов
    #define swap(x,y)  {int t=x; x=y; y=t;} // процедура перестановки элементов

## Пузырьковая сортировка

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

    void sort_bubble(int a[], int max)      // пузырьковая сортировка
      {
        for (int i=0; i<max; i++)
        for (int j=max-1; j>i; j--)
          if (less(a[j], a[j-1]))
            swap(a[j], a[j-1]);
      }

## Сортировка выбором

Во время i-го прохода по массиву выявляется наименьший элемент, который затем меняется местами с i-м.
Все остальное аналогично пузырьковой сортировке.

    void sort_choose(int a[], int max)      // сортировка выбором
      {
        for (int i=0; i<max; i++)
          {
            int k=i;
            for (int j=i+1; j<max; j++)
              if (less(a[j], a[k]))
                k=j;
            if (i!=k)
              swap(a[i], a[k]);
          }
      }

## Сортировка Шелла

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

    void sort_shell(int a[], int max)               // сортировка Шелла
      {
        for (int gap = max/2; gap>0; gap/=2)        // выбор интервала
          for (int i=gap; i<max; i++)               // проход массива
    // сравнение пар, отстоящих на gap друг от друга
            for (int j=i-gap; j>=0 && less(a[j+gap],a[j]); j-=gap)
              swap(a[j], a[j+gap]);
      }

## Сортировка Хоора

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

Для массива из 10 чисел установим два индекса: на первый (i) и на последний (j) элементы.

            10 7 28 49 31 25 17 3 14 43
            i                      <--j
                               step==-1

На каждом шаге будем изменять значение индекса j на значение step (вначале оно равно -1, индекс уменьшается), т.е. двигать j влево. Мы будем делать так в том случае, если j-й элемент больше, чем i-й элемент. Если это условие не выполнено - поменяем местами i-й и j-й элементы массива и сами индексы i и j, а также изменим знак у значения step -- оно станет равным +1:

            3 7 28 49 31 25 17 10 14 43
            j-->               i
            step==+1

Продолжим процесс: теперь j движется вправо, и изменится условие - сейчас для продолжения процесса необходимо, чтобы j-й элемент был меньше i-го.

Будем продолжать вышеописанный процесс до тех пор, пока индексы i и j не станут одинаковыми.

В этот момент можно утверждать, что i-й (он же и j-й) элемент разделил исходное множество на два подмножества: все элементы, находящиеся слева от делящего элемента, меньше его, и все элементы, находящиеся справа, не меньше делящего (i-го) элемента. Получилось, что i-й элемент стоит на своем месте:

            3 7 10 49 31 25 17 28 14 43
                ij

Таким образом, мы описали процедуру нахождения расположения одного элемента. Иными словами, мы "отсортировали" один элемент множества. Такая же процедура применима к элементам "левого" и "правого" подмножеств, которые на данный момент еще не отсортированы.

Условие завершения нашей рекурсивной процедуры - совпадение границ, которое эквивалентно тому, что в множестве остался один элемент.

    void sort_hoor(int a[], int l, int r)   // сортировка Хоора
      {
        int i=l, j=r, step=-1, condition=1;
        if (l>=r) return;                   // сортировать нечего

        do {                         // сортируем с левой границы до правой
          if (condition == less(a[j],a[i]))
            {
              swap(a[i], a[j]);             // перестановка чисел
              swap(i, j);                   // обмен местами индексов
              step = -step;                 // теперь - в другую сторону
              condition = !condition;       // обмен условия на противоположное
            }
          j += step;                        // передвинем индекс
        } while (j!=i);                     // пока индексы не сойдутся
        sort_hoor(a, l, i-1);               // левое подмножество
        sort_hoor(a, i+1, r);               // правое
      }

## QuickSort

По существу является разновидностью сортировки Хоора, но программная реализация немного красивее и быстрее.

Основное отличие - за делящий элемент всегда выбирается середина массива.

    void sort_quick(int a[], int l, int r) // QuickSort
      {
        int i=l, j=r, x=a[(l+r)/2];
        do {
          while (less(a[i],x)) i++;
          while (less(x,a[j])) j--;
          if (i<=j) {
            swap(a[i], a[j]);
            i++;
            j--;
          };
        } while (i<j);
        if (l<j) sort_quick(a,l,j);
        if (i<r) sort_quick(a,i,r);
      }

## Сортировка с помощью двоичного дерева

Двоичным деревом назовем упорядоченную структуру данных, в которой каждому элементу -- предшественнику или корню (под)дерева -- поставлены в соответствие по крайней мере два других элемента (преемника). Причем для каждого предшественника выполнено следующее правило: левый преемник всегда меньше, а правый преемник всегда больше или равен предшественнику. Если мы составим такое дерево из букв слова "СОРТИР", сравнивая ASCII коды букв, то получим следующую структуру:

                                       С
                                     /   \
                                    О     Т
                                  /   \
                                 И     Р

Как видно, узел "С" имеет два преемника: левый "О" и правый "Т". Если составить бинарное дерево из элементов неупорядоченного массива, то в общем случае дерево получится достаточно хорошо заполненным (а если массив уже был рассортирован, то дерево выродится в линейный список). Если мы будем обходить дерево по правилу "ЛЕВЫЙ преемник - КОРЕНЬ - ПРАВЫЙ преемник", то, записывая все встречающиеся элементы в массив, мы получим упорядоченное в порядке возрастания множество. На этом и основана идея сортировки деревом.

Использование такой сортировки удобно тогда, когда удобно представлять данные в виде дерева.

Недостаток метода - требуется много памяти. В приведеном примере - дополнительный мегабайт данных на каждые 256k элементов.

    /*********** сортировка с помощью двоичного дерева *************/

    typedef struct tree
      {
        int a;              // данные
        struct tree *left;  // левый  преемник
        struct tree *right; // правый преемник
      } TREE;

    TREE *add_to_tree(TREE *root, int new_value)
    {
       if (root==NULL)  // если дошли до корня - создаем новый элемент
         {
            root = (TREE*)malloc(sizeof(TREE));
            root->a = new_value;
            root->left = root->right = 0;
            return root;
         }
       if less(root->a, new_value)          // добавлем ветвь
         root->right = add_to_tree(root->right, new_value);
       else
         root->left  = add_to_tree(root->left,  new_value);
       return root;
    }

    void tree_to_array(TREE *root, int a[]) // процедура заполнения массива
      {
        static max2=0;                      // счетчик элементов нового массива
        if (root==NULL) return;             // условие окончания - найден корень
        tree_to_array(root->left, a);       // обход левого поддерева
        a[max2++] = root->a;
        tree_to_array(root->right, a);      // обход правого поддерева
        free(root);
      }

    void sort_tree(int a[], int max)        // собственно сортировка
    {
       TREE *root = 0;
       for (int i=0; i<max; i++)            // проход массива и заполнение дерева
          root = add_to_tree(root, a[i]);
       tree_to_array(root, a);              // заполнение массива
    }

## Сортировка с помощью массива индексов

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

Идея заключается в том, что параллельно с основным массивом данных существует так называемый массив индексов, через который осуществляется перестановка индексов основного массива данных.

    struct XPEH a[10000]; // основной массив
    int index[10000];     // массив индексов {0,1,2,...,9999}

Перед сортировкой массив индексов инициализируется соответствующими порядковыми номерами.

Доступ к массиву данных ведется не как a[i], а как a[index[i]], и функция сравнения теперь выглядит иначе:

    #define less(i,j)  (a[index[i]].XPEH_member < a[index[j]].XPEH_member)

В результате фактически сортируется массив с индексами, а не с данными.

    void sort_quick_index(XPEH a[], int index[], int l, int r)
      {
        int i=l, j=r, x=(l+r)/2;            // теперь x не элемент а его индекс
        do {
          while (less(i,x)) i++;
          while (less(x,j)) j--;
          if (i<=j)
            {
              if (x==i) x==j; else if (x==j) x==i;
              swap(index[i], index[j]);     // сортируем индексы
              i++;
              j--;
            };
        } while (i<j);
        if (l<j) sort_quick_index(a,index,l,j);
        if (i<r) sort_quick_index(a,index,i,r);
      }

А теперь сравните по скорости тысячу операций swap(x,y), где в первом случае x и y - это большие структуры данных, а во втором - числа по 2-4 байта.

## Какую сортировку выбрать

Ниже приведена зависимость скорости сортировки от числа элементов массива. Эксперимент проводился на весьма торозном компьютере, так что верна лишь пропорциональность скоростей. Массив заполнялся случайными числами от 0 до N, где N - число элементов массива.

Как видно, QuickSort показывает лучший результат по времени, да и по реализации процедура сортировки весьма проста.

Таким образом лучшее решение - ассемблерный аналог QuickSortа, с использованием массива индексов если структуры данных достаточно большие.

Примечание: не следует исходники сортировок понимать буквально, ибо они далеки от совершенства. В частности, в рекурсивных функциях сортируемый массив как параметр вовсе не передается, и именно так было при построении графика.

И еще: в случае, если функция сравнения less(XPEH a,XPEH b) занимает много времени, можно заранее просчитать "веса" элементов и функцию сравнения определить уже для них.