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.