473,321 Members | 1,708 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,321 software developers and data experts.

linked list quicksort

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
6 8863
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
"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
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

"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
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
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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

9
by: Goh, Yong Kwang | last post by:
I'm currently doing a project that has a array that supposed to be determined only at runtime. Originally, the prototype I did as a proof of theory (or a quick hack) So one method is to create a...
3
by: darth | last post by:
Does anyone have heap sorting with queue(doublely linked list) in C? I have heap sort with array but with queue, it's somewhat hard.
4
by: Peter Schmitz | last post by:
Hi, in my application, I defined a linked list just as follows: typedef struct _MYLIST{ int myval; void *next; }MYLIST; MYLIST head;
6
by: Baltazar007 | last post by:
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
1
by: lg2530 | last post by:
template<class T> struct NODE { T data; NODE<T> * next; }; template<typename T> NODE<T>* QuickSortList( NODE<T>* list ) {}
51
by: Joerg Schoen | last post by:
Hi folks! Everyone knows how to sort arrays (e. g. quicksort, heapsort etc.) For linked lists, mergesort is the typical choice. While I was looking for a optimized implementation of mergesort...
6
by: Nick Valeontis | last post by:
I know how to use Icomparable. However, I can't figure out how to sort a generic linked list? (without writing the algorithm) Lets say I have something like this: class...
12
by: aparnakakkar2003 | last post by:
can any one tell me if I give the followiing string in input: ABC abc BBC then how I can get ABC abc BBC
3
by: t | last post by:
What is the most efficient way to sort a linked list? In other words, how is std::list's sort() member function usually implemented? I was thinking of two approaches: (1) make an array of...
1
by: uydf | last post by:
hey, can someone help me with this problem- if every time K pivots are chosen and every pivot gets a linked list attached to it, with the numbers that are between this pivot and the next, and we do...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.