From: mrsmond@hotmail.com (Mond)
Subject: A little help with Quicksort
Date: 1 Jan 2002 14:25:22 -0800
Date: 2002-01-01T22:25:23+00:00 [thread overview]
Message-ID: <1408ce1d.0201011425.29c12c97@posting.google.com> (raw)
Hi,
i'm having a little trouble implementing Quicksort with a doubley
linked list and was hoping someone could put me in the right direction
;)
I have a quicksort procedure for arrays as follows:
procedure QSort(m, n : in Integer) is
x, t, j, k : Integer;
begin
-- Quicksort only if there are more than 2 elements to sort
if (n - m) > 2 then
-- Assign the pivot to the first element in the list
x := List(m);
-- Set up the markers (cursors) that scan the list
j := m + 1;
k := n;
-- Continue sorting while the markers don't meet
while j /= k loop
if List(j) < x then
j := j + 1; -- increment marker1 that moves from
left to right
elsif List(k - 1) >= x then
k := k - 1; -- decrement marker2 that moves from
right to left
elsif List(j) >= x and List(k - 1) < x then
-- Swap j and (k-1)
t := List(j);
List(j) := List(k - 1);
List(k - 1) := t;
-- Increment markers
j := j + 1;
k := k - 1;
end if;
end loop;
-- Update pivot value -- ****
List(m) := List(j - 1); -- ****
List(j - 1) := x; -- ****
-- Sort next partitions
QSort(m, (j - 1));
QSort(j, n);
end if;
end QSort;
This works with arrays but converting it into working with a linked
list is a bit harder.
The part marked with stars above is a wee bit confusing.
Why does it swap the pivot value? Is it so that when QSort is called
again the pivot value remains on the left hand side?
Below is as far as i have got with implementing the double linked list
version:
procedure QSort(L : in out List_Type;
Last : out List_Type) is
Marker1, Marker2, -- points to the limits of the sorted part of
the list
Pivot : List_Type;
t : Integer;
begin
-- If the list is not empty or has more than 1 node then
continue
if (Is_Empty(L) = False) and then (L.all.Next /= null) then
-- Assign the pivot value to be the first element
Pivot := L;
Marker1 := L.all.Next;
Marker2 := Last;
-- While L is not sorted
while Marker1 /= Marker2 loop
if Marker1.all.Val < Pivot.all.Val then
Marker1 := Marker1.all.Next; -- increment Marker1
elsif Marker2.all.Prev.all.Val >= Pivot.all.Val then
Marker2 := Marker2.all.Prev; -- decrement Marker2
elsif (Marker1.all.Val >= Pivot.all.Val)
and(Marker2.all.Prev.all.Val < Pivot.all.Val) then
-- Swap the values of Marker1 and (Marker2 - 1)
t := Marker1.all.Val;
Marker1.all.Val := Marker2.all.Prev.all.Val;
Marker2.all.Prev.all.Val := t;
-- Update Marker1 and Marker2
Marker1 := Marker1.all.Next;
Marker2 := Marker2.all.Prev;
end if;
end loop;
-- Update pivot value
-- **** ??
-- **** ??
-- Sort next partitions
QSort(L, Marker1.all.Prev);
QSort(Marker1, Last);
end if;
I think if i can understand the array part (denoted with stars) i
(hopefully) will be able to do it for the linked list.
If anyone could provide some help or pointers (sorry ;) ) i would be
most grateful.
Thanks in advance,
Mond
PS Sorry for all the .all etc stuff - it makes it clear to me that it
is pointers ;)
next reply other threads:[~2002-01-01 22:25 UTC|newest]
Thread overview: 7+ messages / expand[flat|nested] mbox.gz Atom feed top
2002-01-01 22:25 Mond [this message]
2002-01-02 0:53 ` A little help with Quicksort chris.danx
2002-01-02 13:11 ` Ted Dennison
2002-01-02 22:22 ` Mond
2002-01-03 14:54 ` chris.danx
2002-01-03 15:42 ` Ted Dennison
2002-01-24 23:14 ` Craig Carey
replies disabled
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox