Binary trees and quicksort?

Question

I have a homework assignment that reads as follows (don't flame/worry, I am not asking you to do my homework):

Write a program that sorts a set of numbers by using the Quick Sort method using a binary search tree. The recommended implementation is to use a recursive algorithm.

What does this mean? Here are my interpretations thus far, and as I explain below, I think both are flawed:

A. Get an array of numbers (integers, or whatever) from the user. Quicksort them with the normal quicksort algorithm on arrays. Then put stuff into a binary search tree, make the middle element of the array the root, et cetera, done.

B. Get numbers from the user, put them directly one by one into the tree, using standard properties of binary search trees. Tree is 'sorted', all is well--done.

Here's why I'm confused. Option 'A' does everything the assignment asks for, except it doesn't really use the binary tree so much as it throws it last minute in the end since it's a homework assignment on binary trees. This makes me think the intended exercise couldn't have been 'A', since the main topic's not quicksort, but binary trees.

But option 'B' isn't much better--it doesn't use quicksort at all! So, I'm confused.

Here are my questions:

1. if the interpretation is option 'A', just say so, I have no questions, thank you for your time, goodbye.

2. if the interpretation is option 'B', why is the sorting method used for inserting values in binary trees the same as quicksort? they don't seem inherently similar other than the fact that they both (in the forms I've learned so far) use the recursion divide-and-conquer strategy and divide their input in two.

3. if the interpretation is something else...what am I supposed to do?

Izzard

I doubt it's option A, because in this case you don't even need a tree anymore: You can just do binary searches on the sorted array. – Duntson

You should ask your teacher for clarification - you can't "sort [...] using a quick sort method using a binary search tree" - it's either one or the other, not both. (Some sorting algorithms, such as merge sort, can be applied to linked lists, but none make sense with binary trees, which are inherently sorted.) Maybe an and is missing and you're supposed to write different versions of the sorting routine? – Allanadale

@Allanadale I can't ask my teacher--there's no way of reaching him in time at this point... – Izzard

I'm pretty sure you're supposed to write your own Quicksort implementation, rather than simply using the built-in Collections.sort() or Arrays.sort() which is actually an iterative mergesort. – Nickell

@MikkelLøkke That's definitely helpful, but still doesn't point to option A, B or C... – Izzard

In that case I'd go with interpretation A. It satisfies the text of the assignment by implementing both a bona-fide quicksort and a (non-degenerate) binary tree. It is likely that that's not what the author had in mind, but given the assignment text, it's impossible to tell for certain what they did have in mind. – Allanadale

It is nonsense to create a tree from a sorted data unless you want to eliminate duplicate data (but that's like catching flies with a bazooka), is more likely to dump the data of a tree in an array and then sort by other criteria (an array is not limited to inorder traversal of the tree). I would follow these steps: create a tree, dump the data in an array using a traverse-tree function and then quicksort. – Balliol

@AlterMann That makes sense, but it doesn't have anything to do with BS trees then...-_- – Izzard

I am pretty sure the teacher want something like option 'A'. In fact, the structure of the Quick Sort algorithm is a BST structure. Maybe the teacher wants you to see how the quick sort algirithm is executed, and how the choice of the pivot matters. Wikipedia seems to explain better that I can do : en.wikipedia.org/wiki/… – Melia

Answer 1

Here's a really cool observation. Suppose you insert a series of values into a binary search tree in some order of your choosing. Some values will end up in the left subtree, and some values will end in the right subtree. Specifically, the values in the left subtree are less than the root, and the values of the right subtree are greater than the root.

Now, imagine that you were quicksorting the same elements, except that you use the value that was in the root of the BST as the pivot. You'd then put a bunch of elements into the left subarray - the ones less than the pivot - and a bunch of elements into the right subarray - the ones greater than the pivot. Notice that the elements in the left subtree and the right subtree of the BST will correspond perfectly to the elements in the left subarray and the right subarray of the first quicksort step!

When you're putting things into a BST, after you've compared the element against the root, you'd then descend into either the left or right subtree and compare against the root there. In quicksort, after you've partitioned the array into a left and right subarray, you'll pick a pivot for the left and partition it, and pick a pivot to the right and partition it. Again, there's a beautiful correspondence here - each subtree in the the overall BST corresponds to doing a pivot step in quicksort using the root of the subtree, then recursively doing the same in the left and right subtrees.

Taking this a step further, we get the following claim:

Every run of quicksort corresponds to a BST, where the root is the initial pivot and each left and right subtree corresponds to the quicksort recursive call in the appropriate subarrays.

This connection is extremely strong: every comparison made in that run of quicksort will be made when inserting the elements into the BST and vice-versa. The comparisons aren't made in the same order, but they're still made nonetheless.

So I suspect that what your instructor is asking you to do is to implement quicksort in a different way: rather than doing manipulations on arrays and pivots, instead just toss everything into a BST in whatever order you'd like, then walk the tree with an inorder traversal to get back the elements in sorted order.

A really cool consequence of this is that you can think of quicksort as essentially a space-optimized implementation of binary tree sort. The partitioning and pivoting steps correspond to building left and right subtrees and no explicit pointers are needed.

Expander