Shell Sort for small tables. URLS to other sorts info

bowlesj3 · Postby **bowlesj3** » 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.

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;