Мне нужно отсортировать массив. Помимо уже существующих типов сортировки, мне было интересно, сработает ли подобный алгоритм и какова его сложность.
У меня есть массив, который нужно отсортировать. Я создаю двоичное дерево поиска.
Поэтому, если я вставлю все элементы массива в BST, а затем назначу их обратно в массив один за другим при обходе дерева по порядку, я получу отсортированный результат. (Хотя занимают больше места из-за узлов дерева. Не сортировка на месте.)
int i=0;
void sort_by_inorder(node *n)
{
if(n==NULL)
{
return;
}
sort_by_inorder(n->leftchild);
array[i++]=n->data;
sort_by_inorder(n->rightchild);
}
Я знаю, что BST не позволяет дублировать вставки, поэтому, возможно, мы могли бы рассмотреть возможность изменения алгоритма вставки BST в ‹= для левого поддерева или, возможно, в> = для правого поддерева.
Будет ли это хорошая реализация (работоспособная)? В чем будет сложность?
Сложность обхода в среднем O(n). А прошивка просто O(log n). Так что, на мой взгляд, это должен быть эффективный алгоритм.
Спасибо.
