Shell Sort for small tables. URLS to other sorts info
Posted: 15 Nov 2009
Here is a shell sort from http://en.wikipedia.org/wiki/Shell_sort for those of us who do not like the map commands. The pseudocode is an almost perfect EL code match. I tested it and it seems to work. You can cut and paste this for a clean compile and get a clean lineup of comments too.
Note: If keys are equal this sort may invert them as the link below points out. If this is important and you want to use a sort then go to the link below and find one that is marked as "stable"
for other sort algorithms see http://en.wikipedia.org/wiki/Sorting_algorithm
OF NOTE: There is another type of sort called the "comb sort". I use to have the code for Cobol (Probably still do somewhere). There is lots of info on this sort on Goggle.
I had an interesting web page about quicksort, shell sort and heap sort.
However the link is wrong now so I removed it. It is unfortunate this has to happen.
If you do a google search "quicksort, shell sort and heap sort" you get a comparison.
Note: I only test for the time in this sort. If you are sorting over a day you need to adjust the test to include the date and time. Of course your sort could be completely different with different tables alltogether.
Note: If keys are equal this sort may invert them as the link below points out. If this is important and you want to use a sort then go to the link below and find one that is marked as "stable"
for other sort algorithms see http://en.wikipedia.org/wiki/Sorting_algorithm
OF NOTE: There is another type of sort called the "comb sort". I use to have the code for Cobol (Probably still do somewhere). There is lots of info on this sort on Goggle.
I had an interesting web page about quicksort, shell sort and heap sort.
However the link is wrong now so I removed it. It is unfortunate this has to happen.
If you do a google search "quicksort, shell sort and heap sort" you get a comparison.
Note: I only test for the time in this sort. If you are sorting over a day you need to adjust the test to include the date and time. Of course your sort could be completely different with different tables alltogether.
Code: Select all
Arrays:
{Must match tablemax}
IntraBarPersist Arw_IDs[200](0),
IntraBarPersist Arw_Date[200](0),
IntraBarPersist Arw_Time[200](0),
IntraBarPersist Arw_Dir[200](false);
variables:
inc(0),
n(0),
ii(0),
j(0),
tempTime(0),
tempIDs(0),
tempDate(0),
tempDir(false),
X(0),
TableMax(200);
{X points at last item.}
if X > 0 then {do we need to sort.}
begin
{standard shell sort}
{
algorithm in pseudocode from http://en.wikipedia.org/wiki/Shell_sort
input: an array a of length n with array elements numbered 0 to n - 1
inc = round(n/2)
while inc > 0 do:
for i = inc .. n - 1 do:
temp = a[i]
j = i
while j >= inc and a[j - inc] > temp do:
a[j] = a[j - inc]
j = j - inc
a[j] = temp
inc = round(inc / 2.2)
}
{other sort algorithms - http://en.wikipedia.org/wiki/Sorting_algorithm}
n = X + 1; {Add 1 to X to get N because the first item is in array[0]}
inc = round(n/2,0);
while inc > 0
begin
for ii = inc to n - 1 {ii is used because i does not compile in EL}
begin
tempTime = Arw_Time[ii]; {sort order Table}
tempIDs = Arw_IDs[ii]; {matching table}
tempDate = Arw_Date[ii]; {matching table}
tempDir = Arw_Dir[ii]; {matching table}
j = ii;
while j >= inc and Arw_Time[j - inc] > tempTime {sort test}
begin
Arw_Time[j] = Arw_Time[j - inc]; {sort order Table}
Arw_IDs[j] = Arw_IDs[j - inc]; {matching table}
Arw_Date[j] = Arw_Date[j - inc]; {matching table}
Arw_Dir[j] = Arw_Dir[j - inc]; {matching table}
j = j - inc;
end;
Arw_Time[j] = tempTime; {sort order Table}
Arw_IDs[j] = tempIDs; {matching table}
Arw_Date[j] = tempDate; {matching table}
Arw_Dir[j] = tempDir; {matching table}
end; {for ii = inc to n - 1}
inc = round(inc / 2.2,0);
end; {while inc > 0}
{End OF Shell Sort from http://en.wikipedia.org/wiki/Shell_sort}
end;