Re: Quicksort pathological behavior?
RobertMaas_at_YahooGroups.Com
Date: 04/01/04
- Next message: James Rogers: "Re: future of programming languages"
- Previous message: pete: "Re: Heapsorting doubly-linked lists in C"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Wed, 31 Mar 2004 21:41:34 -0800
> From: CBFalconer <cbfalconer@yahoo.com>
> If you want guaranteed worst case performance, try heapsort (for
> arrays) or mergesort (for lists).
Three points: First, heapsort works fine for binary trees too, in fact
it's easier to understand that way. Second, mergesort works fine with
arrays too. You merge data back and forth between segments of two
different arrays. Third, heapsort isn't stable, so if your data is
originally in an array, instead of kluging a sequence number as
secondary key to make heapsort be stable, or copying the whole array to
a linked-list to mergesort then copying back to the array at the end,
you might as well directly use the two-array version of mergesort.
(Of course if your application really needs to maintain a priority
queue, where highest-priority task is popped from the queue and new
tasks are inserted asynchronously, then a heap with secondary key for
time-enqueued is the best way to achieve stable-sort behaviour.)
It seems to me, from looking at all the sorting algorithms I've seen
(run on a Von Neumann machine, i.e. regular non-quantum
single-processor), if the data is originally in an array and you want
the sorted result in the same array, you can't simultaneously achieve
all three desiderata:
(1) Worst-case behaviour guaranteed bounded by n*log(n);
(2) Stable-sort;
(3) No need to allocate additional storage.
Has anybody proven that mathematically, or found a counterexample?
- Next message: James Rogers: "Re: future of programming languages"
- Previous message: pete: "Re: Heapsorting doubly-linked lists in C"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
|
