8-Bit Software Online Conversion

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.