Analogy between Binary Search Tree and Quicksort Algorithm

Binary Search Tree(BST) and Quicksort Algorithm(QA) are similar in nature in all the factors. They have same time complexities and same number of comparisons at every insertion. If one finds the quicksort logic difficult to understand and remember then he can always remember BST and memorize QA logic. We will now see how QA algorithm can be seen as simple BST by looking at both the concepts individually.

Binary Search Tree(BST)
Binary Search Tree(BST) property is that every inserted node in the BST would be inserted to the left of its parent node if its less than the parent node value and inserted to the right of its parent node if its more.

Binary Search Tree (constructed from random input array)
BST Sort

Binary Search Tree (constructed from sorted input array)
BST Sorted
Complexity of BST: Randomized input would lead to complete BST in which case the BST insertion would take O(logn) time complexity. And if the input is sorted in some order(ascending or descending) then its going to be the length of the array, i.e, O(n)
So for n inserts it would be O(nlogn) or O(n^2)

Quicksort Algorithm
Now we will look at quick sort logic
Plain Quicksort Algorithm
QAExample

Quicksort algorithm with BST embedded
QAExample1

Complexity of Quicksort Algorithm: Randomized input would lead to O(logn) time complexity as seen in above diagram. And if the input is sorted in some order then its going to be length of the array, i.e, O(n)
So for n inserts it would be O(nlogn) or O(n^2)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Mawazo

Mostly technology with occasional sprinkling of other random thoughts

amintabar

Amir Amintabar's personal page

101 Books

Reading my way through Time Magazine's 100 Greatest Novels since 1923 (plus Ulysses)

Seek, Plunnge and more...

My words, my world...

ARRM Foundation

Do not wait for leaders; do it alone, person to person - Mother Teresa

Executive Management

An unexamined life is not worth living – Socrates

Diabolical or Smart

Nitwit, Blubber, Oddment, Tweak !!

javaproffesionals

A topnotch WordPress.com site

thehandwritinganalyst

Just another WordPress.com site

coding algorithms

"An approximate answer to the right problem is worth a good deal more than an exact answer to an approximate problem." -- John Tukey