Binary Search Tree Vs Quick Sort

J

j1mb0jay

I have started to implement my own version of a binary search tree, i use
this data structure to sort my own version of a doubly linked link list.
It seems to work rather well but i would like to try and speed it up.

Is using a Binary Search Tree as good as Quick Sort?

From what i remember from the lectures I attended they are both O ( n log
n ). I understand that both of these sorts run best when the pivot/root
item is the half value from the list. If the list is already in order
they both become O(n^2) to do nothing at all.

What is the best way of selecting Pseudo Random items from the list and
calculating which what the best pivot/root?

Regards j1mb0jay
 
J

j1mb0jay

A question like this is probably better suited to a general
programming forum like comp.programming than to a discussion group
concerned with one programming language.

Ok will try posting there as well !!
My answer to your question is "No." For further elaboration,
discussion, and to learn why the answer might equally well be "Yes" or
"Maybe" or "42," consult a programming forum.


It appears you've remembered perhaps half of the lecture
material. As in another thread you started, there's reason to suspect
you might not quite understand what big-Oh is and isn't. Also, you're
speaking of two rather different things as if they were the same:
Quicksort is an algorithm, while a tree is a data structure. A tree
just sits there inertly, doing "nothing at all" on its own initiative.
Quicksort performs a sort, and even in the degenerate O(n^2) case it
does considerably more than "nothing at all." You are confusing the
vehicle with the journey.

I understand one is a data structure and the other not, my question was
if i had a set of data and wanted to get it into order, would it faster
to put the information into a binary search tree and then iterate it
accordingly or use quick sort.
 
M

Mark Space

j1mb0jay said:
I understand one is a data structure and the other not, my question was
if i had a set of data and wanted to get it into order, would it faster
to put the information into a binary search tree and then iterate it
accordingly or use quick sort.

<http://en.wikipedia.org/wiki/Sorting_algorithm>

I.e., until you find your lecture notes, Wikipedia has a pretty good
summary.

But hashing is faster than sorting. Are you sure you need to sort? Or
just look up?
 
J

j1mb0jay

j1mb0jay wrote:



<http://en.wikipedia.org/wiki/Sorting_algorithm>

I.e., until you find your lecture notes, Wikipedia has a pretty good
summary.

But hashing is faster than sorting. Are you sure you need to sort? Or
just look up?

I don't really need to do anything, just figuring out which would be
faster, but it seems that it completely depends on what you are using it
for. I have implemented a binary search tree since i started this post
and am now attempting the quick sort, wish me look.
 
J

j1mb0jay

Remember to test both with worst-case data. A binary tree will have to
explicitly balance itself to avoid bad performance with input that's
already sorted. With a quick sort, you can pick a pivot randomly and
that will (on average) automatically deal with problems related to the
original ordering of the data, with only the very small added cost of
using a random number generator.

Pete

You mean an AVL tree ??

j1mb0jay
 
T

Tom Anderson

Remember to test both with worst-case data. A binary tree will have to
explicitly balance itself to avoid bad performance with input that's
already sorted. With a quick sort, you can pick a pivot randomly and
that will (on average) automatically deal with problems related to the
original ordering of the data, with only the very small added cost of
using a random number generator.

Another option is to look at three potential pivots (randomly chosen, or
middle and quartiles, say), and pick the one with the median value. I
think this makes it a 'samplesort', and there is something clever you can
do about picking all the pivots upfront if you like.

There are also ways you can modify a sort to recognise and deal with
problematic inputs. A great example of this is the 'timsort', from the
python standard library:

http://svn.python.org/projects/python/trunk/Objects/listsort.txt

tom
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,900
Latest member
Nell636132

Latest Threads

Top