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

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

Алгоритмы устойчивой сортировки

• Сортировка выбором (Selection sort) — Сложность алгоритма: O(n²); поиск наименьшего или наибольшего элемента и помещение его в начало или конец упорядоченного списка
• Сортировка пузырьком (англ. Bubble sort ) — сложность алгоритма: O(n²); для каждой пары индексов производится обмен, если элементы расположены не по порядку.
• Сортировка перемешиванием (Шейкерная, Cocktail sort, bidirectional bubble sort) — Сложность алгоритма: O(n²)
• Гномья сортировка — имеет общее с сортировкой пузырьком и сортировкой вставками. Сложность алгоритма — O(n²).
• Сортировка вставками (Insertion sort) — Сложность алгоритма: O(n²); определяем где текущий элемент должен находиться в упорядоченном списке и вставляем его туда
• Сортировка слиянием (Merge sort) — Сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти; выстраиваем первую и вторую половину списка отдельно, а затем — сливаем упорядоченные списки
• Сортировка с помощью двоичного дерева (англ. Tree sort) — Сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти
• Алгоритм сортировки Timsort (англ. Timsort) — Сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти; Комбинированный алгоритм (используется сортировка вставками и сортировка слиянием. Разработан для использования в языке Python^[4]
• Сортировка подсчётом (Counting sort) — Сложность алгоритма: O(n+k); требуется O(n+k) дополнительной памяти (рассмотрено 3 варианта)
• Блочная сортировка (Корзинная сортировка, Bucket sort) — Сложность алгоритма: O(n); требуется O(k) дополнительной памяти и знание о природе сортируемых данных, выходящее за рамки функций "переставить" и "сравнить".