Author: Chris Baldwin
I find that alot of developers that use sorting and search algorithms, taking the
Quick Sort algorithm for an example, will reimplement it for every use.
Answer:
Sorting algorithms rarely depend on actual knowledge what they are sorting, and
when we require an algorithm and implement it, why restrict the algorithm to a
specific use, as the algorithm itself will never change.
They are only dependent on an index of which they then need to compare and exchange
the information that resides at those indexes.
The quick sort algorithm for the example would require only 3 main factors of which
could be passed to a quick sort method.
Start and End indexes
Method for Comparing points
Method for Exchanging points
This going to apply for practially all sorting/searching algorithms.
All that is required is that we specify the types that will define the Compare and
Exchange methods.
1 type
2 TIndexCompare = function(const ixA, ixB: integer): integer of object;
3 TIndexExchange = procedure(const ixA, ixB: integer) of object;
4 //-- Also these methods could be also reused for multiple sort algorythms.
5 //-- e.g
6 //-- procedure InsertionSortByIndex(ixLo, ixHi: Integer;
7 //-- IndexCompare: TIndexCompare;
8 //-- IndexExchange: TIndexExchange);
9 //-- etc....
10
11 procedure QuickSortByIndex(ixLo, ixHi: Integer;
12 IndexCompare: TIndexCompare;
13 IndexExchange: TIndexExchange);
14 implementation
15
16 procedure QuickSortByIndex(ixLo, ixHi: Integer;
17 IndexCompare: TIndexCompare;
18 IndexExchange: TIndexExchange);
19
20 procedure SortIndex(aLo, aHi: Integer);
21 var
22 I, J, P: Integer;
23 tmpInt: Integer;
24 begin
25 repeat
26 I := aLo;
27 J := aHi;
28 P := (aLo + aHi) shr 1;
29 repeat
30 while (I < aHi) and (IndexCompare(I, P) < 0) do
31 Inc(I);
32 while (J > aLo) and (IndexCompare(J, P) > 0) do
33 Dec(J);
34 if I <= J then
35 begin
36 IndexExchange(I, J);
37 if P = I then
38 P := J
39 else if P = J then
40 P := I;
41 Inc(i);
42 Dec(j);
43 end;
44 until I > J;
45 if aLo < J then
46 SortIndex(aLo, J);
47 aLo := I;
48 until I >= aHi;
49 end;
50
51 begin
52 SortIndex(ixLo, ixHi);
53 end;
54
55 Now to use this..lets say i want to sort a listbox for the example(rather than
56 using the Listbox standard sorting)
57
58 type
59 TMyForm = class(TForm)
60 private
61 ListBox1: TListBox;
62 btnSort: TButton;
63 .....
64 public
65 function IndexCompare(const ixA, ixB: integer): integer;
66 procedure IndexExchange(const ixA, ixB: integer);
67 end;
68 ..
69
70 implementation
71
72 function TMyForm.IndexCompare(const ixA, ixB: integer): integer;
73 //-- Source to compare items.
74 begin
75 Result := AnsiCompareText(ListBox1.Items[ixA], ListBox1.items[ixB]);
76 end;
77
78 procedure TMyForm.IndexExchange(const ixA, ixB: integer);
79 // -- Source to exchange items.
80 var
81 tmpStr: string;
82 begin
83 tmpStr := ListBox1.Items[ixA];
84 ListBox1.Items[ixA] := ListBox1.Items[ixB];
85 ListBox1.Items[ixB] := tmpStr;
86 end;
87
88 procedure TMyForm.btnSortClick(Sender: TObject);
89 begin
90 with ListBox1.items do
91 begin
92 BeginUpdate;
93 try
94 if UseQuickSort then
95 QuickSortByIndex(0, count - 1, IndexCompare, IndexExchange)
96 else
97 InsertionSortByIndex(0, count - 1, IndexCompare, IndexExchange);
98 finally
99 EndUpdate;
100 end;
101 end;
102 end;
103
104 //----
Well hopefully that might of been some use
Later All
|
