CODEWITHSUNDEEP
sortingbig-obinary-search-tree
saketk21
saketk21

Reputation: 465

What would be the complexity of this Sorting Algorithm? What are the demerits of using the same?

The sorting algorithm can be described as follows:

1. Create Binary Search Tree from the Array data.

(For multiple occurences, increment occurence variable of the current Node)

2. Traverse BST in inorder fashion.

(Inorder traversal will return Sorted order of elements in array).

3. At each node in inorder traversal, overwrite the array element at current index(index beginning at 0) with current node value.

Here's a Java implementation for the same:

Structure of Node Class

class Node {
    Node left;
    int data;
    int occurence;
    Node right;
}

inorder function (returning type is int just for obtaining correct indices at every call, they serve no other purpose)

public int inorder(Node root,int[] arr,int index) {
    if(root == null) return index;
    index = inorder(root.left,arr,index);
    for(int i = 0; i < root.getOccurence(); i++)
        arr[index++] = root.getData();
    index = inorder(root.right,arr,index);
    return index;
}

main()

public static void main(String[] args) {
    int[] arr = new int[]{100,100,1,1,1,7,98,47,13,56};
    BinarySearchTree bst = new BinarySearchTree(new Node(arr[0]));
    for(int i = 1; i < arr.length; i++)
        bst.insert(bst.getRoot(),arr[i]);
    int dummy = bst.inorder(bst.getRoot(),arr,0);
    System.out.println(Arrays.toString(arr));
}

The space complexity is terrible, I know, but it should not be such a big issue unless the sort is used for an extremely HUGE dataset. However, as I see it, isn't Time Complexity O(n)? (Insertions and Retrieval from BST is O(log n), and each element is touched once, making it O(n)). Correct me if I am wrong as I haven't yet studied Big-O well.

Upvotes: 0

Views: 77

Answers (2)

rcgldr
rcgldr

Reputation: 28921

the goal was to implement an O(n) algorithm to sort an Array of n elements with each element in the range [1, n^2]

In that case Radix sort (counting variation) would be O(n), taking a fixed number of passes (logb(n^2)), where b is the "base" used for the field, and b a function of n, such as b == n, where it would take two passes, or b == sqrt(n), where it would take four passes, or if n is small enough, b == n^2 in where it would take one pass and counting sort could be used. b could be rounded up to the next power of 2 in order to replace division and modulo with binary shift and binary and. Radix sort needs O(n) extra space, but so do the links for a binary tree.

Upvotes: 1

meowgoesthedog
meowgoesthedog

Reputation: 15035

Assuming that the amortized (average) complexity of an insertion is O(log n), then N inserts (construction of the tree) will give O(log(1) + log(2) + ... + log(N-1) + log(N) = O(log(N!)) = O(NlogN) (Stirling's theorem). To read back the sorted array, perform an in-order depth-first traversal, which visits each node once, and is hence O(N). Combining the two you get O(NlogN).

However this requires that the tree is always balanced! This will not be the case in general for the most basic binary tree, as insertions do not check the relative depths of each child tree. There are many variants which are self-balancing - the two most famous being Red-Black trees and AVL trees. However the implementation of balancing is quite complicated and often leads to a higher constant factor in real-life performance.

Upvotes: 1

Related Questions