Simple sorting algorithm for arrays

, ,
1

Hello all!

The logic END-ALL SORT … END-SORT has a very bad performance for small amounts of data on our system - i.e. small arrays.

So here’s my quick’n’dirty implementation of a bubble sort. Please feel free to improve it - but please let the community know your improvements.

define data parameter
1 #sorting-tab(1:*)
  2 #values    (A) dynamic
  2 #indexes   (I4)  /* e.g. for referencing a table-line
*
local
*
1 #index            (I4)
1 #value            (B) dynamic
*
1 #i                (I4)
1 #n                (I4)
1 #newn             (I4)
1 #occ-1            (I4)
end-define
*
#n := *OCC(#sorting-tab.#values)
repeat
*
  #newn := 2
  #occ-1 := #n - 1
  for #i = 1 to #occ-1
    if #sorting-tab.#values(#i) > #sorting-tab.#values(#i + 1)
*
      #value                        := #sorting-tab.#values(#i)
      #sorting-tab.#values(#i)      := #sorting-tab.#values(#i + 1)
      #sorting-tab.#values(#i + 1)  := #value
      #index                        := #sorting-tab.#indexes(#i)
      #sorting-tab.#indexes(#i)     := #sorting-tab.#indexes(#i + 1)
      #sorting-tab.#indexes(#i + 1) := #index
*
      #newn := #i + 1
    end-if
  end-for
  #n := #newn
*
  if #n <= 2
    escape bottom
  end-if
end-repeat
*
end

regards

Matthias

2

Hi Matthias;

A number of years ago I wrote a bunch of sorts in Natural. Then I compared them to Natural’s own SORT. I did not even come close to Natural’s times. As I recall, a double bubble sort came closest, but it was 50% longer than Natural. I will have to see if I can find the old library where those tests would reside.

Have you tried both DYNAMIC and non DYNAMIC lengthed values, and X-array and non X-arrays? My guess is that perhaps the SORT does not deal well with variability in the data structure. For example, the IF statement has to deal with length values whereas with non DYNAMIC values, there is no length. Perhaps SORT has some less than optimal code for dealing with lengths. You might run your comparison with everything fixed ( no X-array, no DYNAMIC).

I too had an “index” array. Since I was playing with fixed lengthed fields then, what I did was define them as:

           1 #sort-field (a12/1:20)                    /* note, keeping within the old A253 constraint. old habits die hard
           1 redefine #sort-field
              2  #value (a10)   
              2  #index (n2)

Then you can reduce your six assigns to three. More importantly, you reduce your subscript use by half.

steve

3

Hi Steve Robinson!

Sounds interesting…

Natural’s SORT is not able to deal with dynamics…

define data local
01 #myarray (A/9) dynamic
init <'bla','blub','foo','bar','zoo','a','c','bla'>
01 #i1 (I1)
end-define
for #i1 = 1 to 8
  ignore
end-all
sort by #myarray(#i1) using #i1  /* NAT0232 here
  display #i1 #myarray(#I1)
end-sort
end

Next thing is that you can’t nest Natural’s SORT. So this is one more reason to write an own sort…

Regards,

Matthias

4

Hello my friend
Thanks for attaching a sample code of the table sort
Thank