Note: At the end of the document is a discussion of the various techniques,
a short evaluation of the goods and bads, and also a small enhancement
to the Bubble-Sort algorithm called Back-Track (in C).
- Amit Margalit (9-MAY-1992)
Information
ÄÄÄÄÄÄÄÄÄÄÄ
By definition, sort routines place un-ordered numeric or string data into
ascending or descending order. Many sort algorithms have been discovered,
and delineating their characteristics is a favorite pastime of Pascal
tutorials.
Bubble Sort
The bubble sort algorithm derives its name from the way it systematically
floats the largest values in an array to the top, like bubbles in a bottle
of soda.
The algorithm goes like this: starting at the bottom of the array, compare
each adjacent pair of values; if the lower member of the pair is greater
than the upper member, swap. Once you've worked your way to the top in this
fashion, theArray[ARRAYSIZE] is known to be the largest number in the
array. Now repeat the process, but this time stop one element short of the
top (since we already know this value is the largest). Repeat this process
until finally on the last pass you examine only the bottom two members of
the array.
procedure BubbleSort (var theArray: arrayType);
var
last, current : integer;
begin
for last := ARRAYSIZE downto 2 do
for current := 1 to last-1 do
if theArray[current] > theArray[current+1] then
Swap(theArray[current], theArray[current+1]);
end; { BubbleSort }
Insertion Sort
The insertion sort is on the simple end of the scale, and resembles the way
people sort a bridge hand. Working from one end of the array to the other,
each value is placed in its correct position relative to the values that
have already been sorted.
The routines shown here are designed to process arrays of integers into
ascending order (i.e., theArray[1] gets the lowest value;
theArray[ARRAYSIZE] gets the highest), although with only trivial changes
the algorithms could easily work with string data and/or descending order.
const
ARRAYSIZE = 100;
type
arrayType = array[1..ARRAYSIZE] of integer;
procedure InsertionSort (var theArray: arrayType );
var
newValue, newPos, currentPos: integer;
begin
for newPos := 2 to ARRAYSIZE do
begin
newValue := theArray[newPos];
currentPos := newPos;
while (currentPos > 1) and (theArray[currentPos-1] > newValue) do
begin
theArray[currentPos] := theArray[currentPos-1];
currentPos := currentPos - 1;
end;
theArray[currentPos] := newValue;
end;
end; { InsertionSort }
Shell Sort
The Shell Sort was invented by a computer scientist named Donald Shell. His
sorting method compares and swaps numbers the greatest distance from each
other first, shrinking the distance between numbers until you return to the
ones in closest proximity to each other.
procedure ShellSort(var List: ListType; ListMax: integer);
label
ExitLoop;
var
Indx, Jndx, TheVal, Incr : integer;
begin
Incr := 1;
repeat
Incr := 3 * Incr + 1;
until Incr > ListMax;
repeat
Incr := Incr div 3;
for Indx := Incr + 1 to ListMax do
begin
TheVal := List[Indx];
Jndx := Indx;
while List[Jndx - Incr] > TheVal do
begin
List[Jndx] := List[Jndx - Incr];
Jndx := Jndx - Incr;
if Jndx <= Incr then
goto ExitLoop;
end;
ExitLoop:
List[Jndx] := TheVal;
end;
until Incr = 1;
end; { ShellSort }
Quicksort
King of the sorting algorithms is Quicksort. The gist of Quicksort is
summarized here (in general it is a recursive algorithm):
-- Pick a pivot point in the center of the array
-- Partition the array:
Exchange equal or larger elements (working from the left) with equal or
smaller elements (working from the right). Repeat this process until the
array has been organized such that every value left of the pivot point is
smaller than every value right of the pivot point, and the value at the
pivot point itself is in exactly the right position.
-- If there's more than one element left of the pivot point,
call Quicksort recursively on the left-hand part of the array
-- If there's more than one element right of the pivot point,
call Quicksort recursively on the right-hand part of the array
procedure Quicksort(start, finish: integer);
{ sorts global variable theArray }
var
pivot, left, right : integer;
begin
{ set pivot point }
left := start;
right := finish;
pivot := theArray[(start + finish) div 2];
{ partition }
repeat
while theArray[left] < pivot do
left := left + 1;
while pivot < theArray[right] do
right := right - 1;
if left <= right then
begin
Swap( theArray[left], theArray[right] );
left := left + 1;
right := right - 1;
end;
until right <= left;
{ sort right and left halves }
if start < right then QuickSort(start, right);
if left < finish then QuickSort(left, finish);
end; { QuickSort }
------------------------------------------------------------------------------
Following are a few additions by Amit Margalit
------------------------------------------------------------------------------
BackTrack - An enhancement of the Bubble-Sort.
The idea of BackTrack is simple: You run only once on the entire array, and
every time you find an element out of place, you search backwards through
the array to find where is the right place for it.
/* Assumes that we are sorting int's */
void backtrack(int* array, int nelem)
{
int idx,temp;
void track(int* arr,int cidx);
if(nelem == 1)
return;
for(idx=1;idx < nelem; idx++) {
if(*(array+idx) < *(array+idx-1)) {
track(array,idx);
}
}
}
void track(int* array, int idx)
{
do {
swap(*(array+idx) , *(array+idx-1)); /* swap elements */
idx--; /* decrease index */
} while ( (idx > 0) && (*(array+idx) < *(array+idx-1)) );
/* repeat while index is 1 or more, and element still not in place */
}
swap(int* v1, int* v2)
{
int temp;
temp = *v1;
*v1 = *v2;
*v2 = temp;
}
Merge-Sort
----------
Actually, this is the most efficient of all algorithms (where speed is
concerned...). It needs twice as much storage space. Here are the basics:
Note: when you have two already-sorted arrays and you want to merge them into
a single sorted array, you simply read the first elements, compare them. The
one that fits to be before the other is sent to the output stream, and a new
one from its array is read, and the comparison goes on again and again until
the arrays are merged.
- Divide the array into 2 separate ones.
- If the number of elements on the left side is more than one, call
merge-sort in recursion giving it the left array as an array to sort.
- Do the same about the right side.
- When both side have finished and returned, merge the array on the left
with the one on the right.
Here is a C source (to sort an array of ints):
/* assume lower memory addresses on the left going up to the right */
mergesort(int* array, int length)
{
int leftsize=length/2;
int rightsize=length-leftsize;
int lidx,ridx,nidx;
int *newarray;
if(leftsize>1)
mergesort(array,leftsize);
if(rightsize>1)
mergesort(array+leftsize,rightsize);
/* both sides are now sorted arrays, so we can merge the two sides */
lidx=ridx=nidx=0;
if((newarray=(int*)malloc(length*sizeof(int)))==NULL)
error("Out of memory."); /* and terminate */
for(;;) {
if(*(array+leftsize+ridx) < *(array+lidx)) {
*(newarray+nidx) = *(array+leftsize+ridx);
nidx++; ridx++;
}
else {
*(newarray+nidx) = *(array+lidx);
nidx++; lidx++;
}
if(lidx>leftsize) /* no more? copy the rest */
for(;ridx<=rightsize;ridx++,nidx++)
*(newarray+nidx) = *(array+leftsize+ridx);
if(ridx>leftsize)
for(;lidx<=rightsize;lidx++,nidx++)
*(newarray+nidx) = *(array+lidx);
}
for(lidx=0;lidx