Sorting methods by Jon Ripley (D5B)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Sorting forms an important aspect of computing. There are many different ways
of sorting, some being faster and more effective than others.

In this article four different methods, the Bubble sort, Insertion sort, Shell
sort and the Quick sort are described and the algorithms and a BASIC listing
given for each.

N() is the name of the array to be sorted, this could be any type of array

 The Bubble Sort

Go through the the array examining pairs of elements. If a pair is in the wrong
order then they are swapped.  This is repeated until the array is examined with
no elements being swapped.

sort(start,finish)
 1 repeat
 2  set finished to true
 3  loop for current = start to finish-1
 4  if N(current) > N(current+1)
 5  then
 6   swap N(current) with N(current+1)
 7   set finished to false
 8  endif
 9  end for loop
10 until finished

Translated into BASIC this becomes;

DEF PROCsort(start,finish)
 LOCAL finished,current,temp
 REPEAT
  finished=TRUE
  FOR current=start TO finished
   IF N(current)>N(current+1) THEN temp=N(current):N(current)=N(current+1):
N(current+1)=temp:finished=FALSE
  NEXT
 UNTIL finished
ENDPROC

 The Shell Sort

The Bubble sort is slow because the elements only move one place at a time. The
Shell sort tries to overcome this by moving the elements further.

In practice the initial value of d should be set to the highest power of 2
below n/2. (Where n is the number of elements.)

sort(start,finish)
 1 d = finish - start + 1 (number of elements)
 2 repeat
 3  d = d div 2
 4  loop for current = start to finish-d
 5   if N(current) < N(current+d)
 6   then
 7    swap N(current) with N(current+1)
 8   endif
 9   end for loop
10 until d=1

Translated into BASIC this becomes;

DEF PROCsort(start,finish)
 LOCAL d,current,temp
 d=finish-start+1
 REPEAT
  d=d DIV 2
  FOR current=start TO finish-d
   IF N(current)<N(current+d) THEN temp=N(current):N(current)=N(current+d):
N(current+d)=temp
  NEXT
 UNTIL d=1
ENDPROC

 The Insertion Sort

For each element in the unsorted part of the array. Search through the list
and find the position of the highest element and swap it with the element at
the top of the array. The top element is now in the correct position and thus
forms part of the sorted list.

sort(start,finish)
 1 loop for current = start to finish-1
 2  set highest to current
 3  loop for i = current+1 to finish
 4   if N(i) > N(highest)
 5   then
 6    set highest to i
 7   endif
 8  end for loop
 9  swap N(current) with N(highest)
10 end for loop

Translated into BASIC this becomes;

DEF PROCsort(start,finish)
 LOCAL current,highest,i,temp
 FOR current=start to finish-1
  highest=current
  FOR i=current+1 TO finish
   IF N(I)>N(highest) THEN highest=i
  NEXT
  temp=N(current)
  N(current)=N(highest)
  N(highest)=temp
 NEXT
ENDPROC

 The Quick Sort

Select the first element in the array and partition the list sp that the items
less than the first come after it and items greater than the first come after
it. The first item is now in the correct position, the two lists are then
sorted.

sort(start,finish)
 1 if start < finish
 2 then
 3  partition the list forming a pivot at i
 4  sort(start,i-1)
 5  sort(i+1,finish)
 6  endif

The process of partitioning the list are quite complex and are expanded in the
next algorithm.

sort(start,finish)
 1 if start < finish
 2 then
 3  set i to start
 4  set j to finish
 5  set jstep to -1
 6  set condition to true
 7  repeat
 8   if condition = (N(i) < N(j))
 9   then
10    swap n(i) with n(j)
11    swap i with j
12    set jstep to -jstep
13    set condition to not condition
14   endif
15   set j to j + jstep
16  until i = j
17  sort(start,i-1)
18  sort(i+1,finish)
19 endif

Translated to BASIC this becomes;

DEFPROCsort(start,finish)
 IF start<finish THEN PROCpartition(start,finish):PROCsort(start,i-1):
PROCsort(i+1,finish)
ENDPROC
DEF PROCpartition(i,j)
 LOCAL jstep,condition,temp
 jstep=-1
 condition=TRUE
 REPEAT
  IF condition=(N(i)<N(j)) THEN temp=N(i):N(i)=N(j):N(j)=temp:temp=i:i=j:
j=temp:jstep=-jstep:condition=NOT condition
  j=j+jstep
 UNTIL i=j
ENDPROC

For the bubble and the shell sort the more ordered the array is the less time
that is taken to complete the sort. So for a list of 1000 items where 10 are
out of place then the sort would be completed in a relatively short time,
however if all or a majority of the items in the list were in the incorrect
place then it would take a long time to sort the array.

The shell sort is faster than the bubble sort.

For the quick sort and the inserting sort the time taken to sort the array
remains the same irrespective of how ordered the array is.

With a small number of items the insertion sort is slower than the bubble and
shell sorts. However, as the list becomes longer the time taken by the
insertion sort becomes less than that taken by the shell and bubble sort.

The final sort, the quick sort is overall the slowest sorting method or small
arrays. Not to be fooled though, as the size of the array increases the time
taken to perform the sort increases slowly as opposed to all the other methods
described here where the time taken increases dramatically as the array size
increases. Especially the bubble and shell sort if the lists are very unsorted.

When deciding which method to use generally...

Small number if items -
Shell/Bubble

Small to Medium number of items -
Insertion

Large number of items -
Quick

Another method sometimes used for very large arrays is to use the quick sort
until the partitions are about 50-100 items in size and then use the insertion
sort to finish.

If you would need a machine code version of any of the above sorting methods
then please contact me through 8BS and I will include it in the next issue.

Any comments and criticisms on this article are welcomed as are suggestions
for improvements and changes or suggestions for future articles.