Mega Code Archive
Double Ended Selection Sort
<![CDATA[
Title: Double-Ended Selection Sort
Question: Double-Ended Selection sort algorithm
Answer:
{ Double-Ended Selection Sort
A take on an elementary sorting algorithm that is designed
to minimize the number of exchanges that are performed.
It works by making n-1 passes over the shrinking unsorted
portion of the array, each time selecting
the smallest and largest value. Those values are then moved
into their final sorted position with one exchange a piece. }
//------------------------------------------------------------------------------
procedure FindSmallestAndLargest(Items : TStrings;
iLowIndex,
iHighIndex : Integer;
var iSmallestIndex,
iLargestIndex: Integer);
var
iIndex: Integer;
begin //procedure FindSmallestAndLargest
if Items[iLowIndex] begin //if..then
iSmallestIndex := iLowIndex;
iLargestIndex := iHighIndex;
end //if..then
else
begin //if..else
iSmallestIndex := iHighIndex;
iLargestIndex := iLowIndex;
end; //if..else
for iIndex := Succ(iLowIndex) to Pred(iHighIndex) do
begin //for
if Items[iIndex] iSmallestIndex := iIndex;
if Items[iIndex] Items[iLargestIndex] then
iLargestIndex := iIndex;
end; //for
end; //procedure FindSmallestAndLargest
//------------------------------------------------------------------------------
procedure Swap(Items : TStrings;
iIndex1,
iIndex2: Integer);
var
sTempString: string;
begin //procedure Swap
sTempString := Items[iIndex1];
Items[iIndex1] := Items[iIndex2];
Items[iIndex2] := sTempString;
end; //procedure Swap
//------------------------------------------------------------------------------
procedure DoubleEndedSelectionSort(Items: TStrings);
var
iFrontIndex,
iBackIndex,
iLargestIndex,
iSmallestIndex: Integer;
begin //procedure DoubleEndedSelectionSort
iFrontIndex := 0;
iBackIndex := Pred(Items.Count);
while iBackIndex iFrontIndex do
begin //while
FindSmallestAndLargest(Items, iFrontIndex, iBackIndex, iSmallestIndex, iLargestIndex);
if iSmallestIndex iFrontIndex then
begin //if..then
Swap(Items, iFrontIndex, iSmallestIndex);
if iLargestIndex = iFrontIndex then
iLargestIndex := iSmallestIndex;
end; //if..then
if iLargestIndex iBackIndex then
Swap(Items, iBackIndex, iLargestIndex);
Inc(iFrontIndex);
Dec(iBackIndex);
end; //while
end; //procedure DoubleEndedSelectionSort
]]>