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