Quicksorting - Descending

[Derek]

Hi there. I want to sort the items in my TComboBox. To sort them in ascending order, i use the following code:



procedure TMyCombo.SortItemsAscending(Start, Stop : Integer);
Var
Left : Integer;
Right : Integer;
Mid : Integer;
Pivot : String;
Temp : String;

begin
Left := Start;
Right := Stop;
Mid := (Start + Stop) div 2;

Pivot := GetTempItemText(Mid, FSortSection);
Repeat
While GetTempItemText(Left, FSortSection) < Pivot do inc(Left);
While Pivot < GetTempItemText(Right, FSortSection) do dec(Right);
If Left <= Right then
begin
Temp := FTempItems[Left];
FTempItems[Left] := FTempItems[Right];
FTempItems[Right] := Temp;
inc(Left);
dec(Right);
end;
Until Left > Right;

If Start < Right then SortItemsAscending(Start, Right);
If Left < Stop Then SortItemsAscending(Left, Stop);
end;


This works fine, but now I want to write another procedure which can sort them in descending order. Can any1 plz help me out (example would be gr8!)

Tx. D

[b]
A carelessly planned project takes 3 times longer to complete than expected; A carefully planned project takes only twice as long :-)

Derek )

[Eddy-B]

Obviously you need to do your sorting exactly the other way around:

procedure TMyCombo.SortItemsAscending(Start, Stop : Integer);
Var
Left : Integer;
Right : Integer;
Mid : Integer;
Pivot : String;
Temp : String;

begin
Left := Start;
Right := Stop;
Mid := (Start + Stop) div 2;

Pivot := GetTempItemText(Mid, FSortSection);
Repeat
While GetTempItemText(Left, FSortSection) > Pivot do inc (Left);
While Pivot > GetTempItemText(Right, FSortSection) do dec(Right);
If Left <= Right then
begin
Temp := FTempItems[Left];
FTempItems[Left] := FTempItems[Right];
FTempItems[Right] := Temp;
inc(Left);
dec(Right);
end;
Until Left > Right;

If Start < Right then SortItemsAscending(Start, Right);
If Left < Stop Then SortItemsAscending(Left, Stop);
end;



Eddy-B

Please click Accept as answer if this helped

[Eddy-B]

oh, i forgot, give this function a different name
...

Eddy-B

Please click Accept as answer if this helped

[Derek]

Thanks for replying, Eddy.
But it still sorts incorrectly
I have tried all sorts of changes (<> etc.) Some of them caused infinite loops and others just didn't sort correctly.

[b]
A carelessly planned project takes 3 times longer to complete than expected; A carefully planned project takes only twice as long :-)

Derek )

[dirso]

Hi,

Are u sure it doesn't work? I used the Eddy-B to sort a List Box and it worked very well, just change those 2 sign he told u to.

I hope it helps,
Dirso

[Derek]

Hi dirso. It doesnt work Here is the SortDescending procedure I use:

{--------------------------------------------------------------------}
procedure TMyCombo.SortItemsDescending(Start, Stop : Integer);
Var
Left : Integer;
Right : Integer;
Mid : Integer;
Pivot : String;
Temp : String;

begin
Left := Start;
Right := Stop;
Mid := (Start + Stop) div 2;

Pivot := GetTempItemText(Mid, FSortSection);
Repeat
While GetTempItemText(Left, FSortSection) > Pivot do inc (Left);
While Pivot > GetTempItemText(Right, FSortSection) do dec(Right);
If Left <= Right then
begin
Temp := FTempItems[Left];
FTempItems[Left] := FTempItems[Right];
FTempItems[Right] := Temp;
inc(Left);
dec(Right);
end;
Until Left > Right;

If Start < Right then SortItemsAscending(Start, Right);
If Left < Stop Then SortItemsAscending(Left, Stop);
end;
{--------------------------------------------------------------------}

I tried to sort he following items and this is what I got:

Before Sort After Sort
----------- ----------
G G
A H
M M
H U
F W
B A
U B
W E
E F


[b]
A carelessly planned project takes 3 times longer to complete than expected; A carefully planned project takes only twice as long :-)

Derek )

[dirso]

Hi,

Actually, it worked for me with ur data as well. I think the problem is in ur GetTempItemText or FSortSection. Why don't u remove them and use just FItems[Mid], FItems[Left] and so on? Here is the implementation i made:

/// QuickSort Implementation
function QuickPartitionDesc(Value: TStrings; nFirst, nLast: Integer): Integer;overload;
var
x: String;
i, j: Integer;
begin
x := Value[nFirst];
i := nFirst;
j := nLast;
while true do
begin
while Value[j] < x do dec(j);
while Value[i] > x do inc(i);
if i < j then
begin
TrocaValores(Value, J, I);
end
else
begin
result := j;
break;
end;
end;
end;

procedure JRQuickSortDesc(Value: TStrings; nFirst, nLast: Integer);
var
s: String;
q: Integer;
begin
if nFirst < nLast then
begin
q := QuickPartitionDesc(Value, nFirst, nLast);
JRQuickSortDesc(Value, nFirst, q);
JRQuickSortDesc(Value, q + 1, nLast);
end;
end;

// -----------------------------------
// now, this is how to use it
procedure TForm1.Button1Click(Sender: TObject);
begin
JRQuickSortDesc(listbox1.items, 0, listbox1.items.count - 1);
end;





I hope it helps,
Dirso