By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,364 Members | 1,518 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,364 IT Pros & Developers. It's quick & easy.

linked list quicksort

P: n/a
Does anyone know how to make quicksort for single linked list without
using array?
I know that mergesort is maybe better but I need quicksort!!

thnx
Nov 11 '06 #1
Share this Question
Share on Google+
6 Replies


P: n/a
Baltazar007 wrote:
>
Does anyone know how to make quicksort for single linked list
without using array?

I know that mergesort is maybe better but I need quicksort!!
Why? Mergesort handles the list in place. Quicksort requires an
array, and you don't have one unless you create an auxiliary
array. Total waste.

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>

Nov 11 '06 #2

P: n/a
"Baltazar007" <OB*******************@gmail.comwrote in message
news:ej**********@news2.carnet.hr...
: Does anyone know how to make quicksort for single linked list without
: using array?
:
: I know that mergesort is maybe better but I need quicksort!!

MergeSort is not maybe better, it is guaranteed to be (as good)
or better than QuickSort when sorting a linked list.

QuickSort requires random access to the elements that are to
be sorted, which make it very unsuitable for a linked list.

What makes you say that you "need" QuickSort ?
Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form

Nov 11 '06 #3

P: n/a
Ivan Vecerina wrote:
"Baltazar007" <OB*******************@gmail.comwrote in message
news:ej**********@news2.carnet.hr...
: Does anyone know how to make quicksort for single linked list without
: using array?
:
: I know that mergesort is maybe better but I need quicksort!!

MergeSort is not maybe better, it is guaranteed to be (as good)
or better than QuickSort when sorting a linked list.

QuickSort requires random access to the elements that are to
be sorted, which make it very unsuitable for a linked list.
Quicksort does not "require" random access. Pluck the first
node from the list and call it the partitioning element, walk
sequentially through the list reassigning its nodes to two new
lists depending on how they compare to the partitioning node (if
desired, make a third list for nodes that compare equal), sort
the two lists recursively, and concatenate.

Unfortunately, it seems difficult to avoid degeneracy in a
way that's both effective and cheap. Choosing the first node as
the partioning element is cheap, but runs a substantial risk of
degeneracy: for example, if the list is already in order or in
reverse order, each partitioning pass accomplishes almost nothing.
You could choose a "random" node from a list of known length at the
cost of generating one random number and traversing (on the average)
half the list before each partitioning pass, or you could make the
choice while building the list at the cost of generating a random
number for each node added. Neither of these strategies seems cheap.
What makes you say that you "need" QuickSort ?
His teacher, I bet.

--
Eric Sosman
es*****@acm-dot-org.invalid
Nov 11 '06 #4

P: n/a

"Baltazar007" <OB*******************@gmail.comwrote in message
news:ej**********@news2.carnet.hr...
Does anyone know how to make quicksort for single linked list without
using array?
I know that mergesort is maybe better but I need quicksort!!

thnx
Quicksort on double linked list is possible

Quicksort on single linked list ? I dont know, maybe it's possible.

Dirtysort would be a better name.

Unlucky pivot = crash and burn ;)

Bye,
Skybuck.

Nov 11 '06 #5

P: n/a
Ivan Vecerina wrote:
"Baltazar007" <OB*******************@gmail.comwrote in message
news:ej**********@news2.carnet.hr...
: Does anyone know how to make quicksort for single linked list without
: using array?
:
: I know that mergesort is maybe better but I need quicksort!!

MergeSort is not maybe better, it is guaranteed to be (as good)
or better than QuickSort when sorting a linked list.

QuickSort requires random access to the elements that are to
be sorted, which make it very unsuitable for a linked list.

What makes you say that you "need" QuickSort ?
Ivan

I need it for homework
Nov 11 '06 #6

P: n/a
Baltazar007 wrote:

<snip>
I need it for homework
In that case don't you think it would be a good idea to at least make
some kind of attempt?

I would also point out that the best solution in C often is not good C++
and the best solution in C++ often is not C, so cross-posting between
comp.lang.c and comp.lang.c++ is rarely a good idea. I'll also bet your
teacher specified which language to use and you won't get very good
marks if you use the wrong one.
--
Flash Gordon
Nov 11 '06 #7

This discussion thread is closed

Replies have been disabled for this discussion.