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

Введение
Пузырьковая сортировка/Пример
Сортировка выбором/Пример
Сортировка Шелла/Пример
Сортировка Хоора/Пример
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) занимает много времени, можно заранее просчитать "веса" элементов и функцию сравнения определить уже для них.