Сортировка деревом tree sort

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

Сортировка с помощью дерева осуществляется на основе бинарного дерева поиска.

Бинарное (двоичное) дерево поиска – это бинарное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):

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

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

Для сортировки с помощью дерева исходная сортируемая последовательность представляется в виде структуры данных «дерево».

Например, исходная последовательность имеет вид:

4, 3, 5, 1, 7, 8, 6, 2

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

После того, как все элементы размещены в структуре «дерево», необходимо вывести их, используя инфиксную форму обхода.

Реализация сортировки с помощью дерева на C++

#include
using namespace std;
// Структура — узел дерева
struct tnode
int field; // поле данных
struct tnode *left; // левый потомок
struct tnode *right; // правый потомок
>;
// Вывод узлов дерева (обход в инфиксной форме)
void treeprint(tnode *tree)
if (tree != NULL ) < //Пока не встретится пустой узел
treeprint(tree->left); //Рекурсивная функция вывода левого поддерева
cout field treeprint(tree->right); //Рекурсивная функция вывода правого поддерева
>
>
// Добавление узлов в дерево
struct tnode * addnode( int x, tnode *tree) if (tree == NULL ) // Если дерева нет, то формируем корень
tree = new tnode; //память под узел
tree->field = x; //поле данных
tree->left = NULL ;
tree->right = NULL ; //ветви инициализируем пустотой
>
else // иначе
if (x < tree->field) //Если элемент x меньше корневого, уходим влево
tree->left = addnode(x, tree->left); //Рекурсивно добавляем элемент
else //иначе уходим вправо
tree->right = addnode(x, tree->right); //Рекурсивно добавляем элемент
return (tree);
>
//Освобождение памяти дерева
void freemem(tnode *tree)
if (tree != NULL ) // если дерево не пустое
freemem(tree->left); // рекурсивно удаляем левую ветку
freemem(tree->right); // рекурсивно удаляем правую ветку
delete tree; // удаляем корень
>
>
// Тестирование работы
int main()
struct tnode *root = 0; // Объявляем структуру дерева
system( «chcp 1251» ); // переходим на русский язык в консоли
system( «cls» );
int a; // текущее значение узла
// В цикле вводим 8 узлов дерева
for ( int i = 0; i < 8; i++)
cout cin >> a;
root = addnode(a, root); // размещаем введенный узел на дереве
>
treeprint(root); // выводим элементы дерева, получаем отсортированный массив
freemem(root); // удаляем выделенную память
cin.get(); cin.get();
return 0;
>

Результат выполнения

Комментариев к записи: 3

Источник

Сортировка деревом tree sort

• ShellSort
• TimSort – Data Structures and Algorithms Tutorials
• Comb Sort
• Pigeonhole Sort
• Cycle Sort
• Cocktail Sort
• Strand Sort
• Bitonic Sort
• Pancake sorting
• BogoSort or Permutation Sort
• Gnome Sort
• Sleep Sort – The King of Laziness / Sorting while Sleeping
• Stooge Sort
• Tag Sort (To get both sorted and original)
• Tree Sort
• Odd-Even Sort / Brick Sort

Comparison with other Sorting Algorithm

Easy problems on Sorting algorihtms

• Sort elements by frequency
• Sort an array of 0s, 1s and 2s | Dutch National Flag problem
• Sort numbers stored on different machines
• Sort an array in wave form
• Check if any two intervals intersects among a given set of intervals
• How to sort an array of dates in C/C++?
• Sorting Strings using Bubble Sort
• Sort an array according to count of set bits
• Sort even-placed elements in increasing and odd-placed in decreasing order
• Sort an array when two halves are sorted
• Sorting Big Integers
• Sort a linked list of 0s, 1s and 2s

Medium problems on Sorting algorithms

• Inversion count in Array using Merge Sort
• Find the Minimum length Unsorted Subarray, sorting which makes the complete array sorted
• Sort a nearly sorted (or K sorted) array
• Sort n numbers in range from 0 to n^2 – 1 in linear time
• Sort an array according to the order defined by another array
• Find the point where maximum intervals overlap
• Find a permutation that causes worst case of Merge Sort
• Sort Vector of Pairs in ascending order in C++
• Minimum swaps to make two arrays consisting unique elements identical
• Chocolate Distribution Problem
• Permute two arrays such that sum of every pair is greater or equal to K
• Bucket Sort To Sort an Array with Negative Numbers
• Sort a Matrix in all way increasing order
• Convert an Array to reduced form using Vector of pairs
• Check if it is possible to sort an array with conditional swapping of adjacent allowed

Hard problem on Sorting algorithms

Most Common Sorting Algorithms

• ShellSort
• TimSort – Data Structures and Algorithms Tutorials
• Comb Sort
• Pigeonhole Sort
• Cycle Sort
• Cocktail Sort
• Strand Sort
• Bitonic Sort
• Pancake sorting
• BogoSort or Permutation Sort
• Gnome Sort
• Sleep Sort – The King of Laziness / Sorting while Sleeping
• Stooge Sort
• Tag Sort (To get both sorted and original)
• Tree Sort
• Odd-Even Sort / Brick Sort

Comparison with other Sorting Algorithm

Easy problems on Sorting algorihtms

• Sort elements by frequency
• Sort an array of 0s, 1s and 2s | Dutch National Flag problem
• Sort numbers stored on different machines
• Sort an array in wave form
• Check if any two intervals intersects among a given set of intervals
• How to sort an array of dates in C/C++?
• Sorting Strings using Bubble Sort
• Sort an array according to count of set bits
• Sort even-placed elements in increasing and odd-placed in decreasing order
• Sort an array when two halves are sorted
• Sorting Big Integers
• Sort a linked list of 0s, 1s and 2s

Medium problems on Sorting algorithms

• Inversion count in Array using Merge Sort
• Find the Minimum length Unsorted Subarray, sorting which makes the complete array sorted
• Sort a nearly sorted (or K sorted) array
• Sort n numbers in range from 0 to n^2 – 1 in linear time
• Sort an array according to the order defined by another array
• Find the point where maximum intervals overlap
• Find a permutation that causes worst case of Merge Sort
• Sort Vector of Pairs in ascending order in C++
• Minimum swaps to make two arrays consisting unique elements identical
• Chocolate Distribution Problem
• Permute two arrays such that sum of every pair is greater or equal to K
• Bucket Sort To Sort an Array with Negative Numbers
• Sort a Matrix in all way increasing order
• Convert an Array to reduced form using Vector of pairs
• Check if it is possible to sort an array with conditional swapping of adjacent allowed

Hard problem on Sorting algorithms

Источник

Tree Sort

1. Tree Sort Algorithm
2. Tree Sort Example
3. Tree Sort Algorithm Implementation
4. Tree Sort Algorithm Complexity

Tree sort is an online sorting algorithm. It uses the binary search tree data structure to store the elements. The elements can be retrieved in sorted order by doing an in-order traversal of the binary search tree. Since it is an online sorting algorithm, the elements inserted are always maintained in sorted order.

Tree Sort Algorithm

Let us assume that we have an unsorted array A[] containing n elements.

TreeSort()

Build the Binary search Tree by inserting elements from the array in Binary Search Tree.

Perform in-order traversal on the tree to get the elements back in sorted order.

Insert()

Create a BST node with a value equal to the array element A[i] .

Insert(node,key)

If root ==null, return the newly formed node.

If root->data < key , root->right = insert(root->right,key)

If root->data > key , root->left = insert(root->left,key)

return the pointer to the original root.

Inorder()

Traverse the left subtree.

Visit the root.

Traverse the right subtree.

Tree Sort Example

Suppose we have the array: (5, 3, 4, 2, 1, 6) . We will sort it using the insertion sort algorithm.

First, we initialize BST by creating the root node 5 .

3 is smaller than 5 , so it gets inserted into the left of 5 .

4 is smaller than 5 but large than 3 , so it gets inserted into the right of 3 but left of 4 .

2 is the smallest element in the current tree, so it gets inserted at the leftmost position.

1 is the smallest element in the current tree, so it gets inserted at the leftmost position.

6 is the largest element in the current tree, so it gets inserted at the rightmost position.

After the BST has been built, we perform in-order traversal on the tree to get the final sorted array (1, 2, 3 ,4, 5, 6) .

Tree Sort Algorithm Implementation

#include  using namespace std;  class Node  public:  int key;  Node *left, *right; >;  Node* newNode(int item)   Node *temp = new Node;  temp->key = item;  temp->left = temp->right = NULL;  return temp; >  void inorder(Node *root, int arr[], int &i)   if (root != NULL)    inorder(root->left, arr, i);  arr[i++] = root->key;  inorder(root->right, arr, i);  > >  Node* insertintoBST(Node* node, int key)   if (node == NULL) return newNode(key);  if (key  node->key)  node->left = insertintoBST(node->left, key);  else if (key > node->key)  node->right = insertintoBST(node->right, key);  return node; >  void treeSort(int arr[], int n)   Node *root = NULL;  root = insertintoBST(root, arr[0]);  for (int i = 1; i  n; i++)  root = insertintoBST(root, arr[i]);  int i = 0;  inorder(root, arr, i); >  int main()    int n = 6;  int arr[6] = 5, 3, 4, 2, 1, 6>;  cout  <"Input array: ";  for (int i = 0; i  n; i++)   cout   <" ";  >  cout  <"\n";  treeSort(arr, n); // Sort elements in ascending order  cout  <"Output array: ";  for (int i = 0; i  n; i++)   cout   <" ";  >  cout  <"\n"; > 

Tree Sort Algorithm Complexity

Time Complexity

The worst-case occurs when the array is sorted, and an unbalanced binary search tree having a maximum height of O(n) is formed. It requires O(n) time for traversal and O(n 2 ) for insertion as compared to the O(logn) time for traversal in case of a regular BST of height logn . The worst-case time complexity is [Big O]: O(n 2 ).

The best-case occurs when the binary search tree formed is balanced. The best-case time complexity is [Big Omega]: O(nlogn) . It is the same as average-case time complexity.

Space Complexity

Space Complexity for this algorithm is O(n) because n nodes have to be created for each element inside the binary search tree.

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

Источник