Sorting is one of the simplest and most often employed tasks when writing computer code. But how do you do it?
All sorting algorithms share one thing in common:
1. Look at a list of items one by one,
2. If the next item is out of sequence,
3. Then swap the items.
The bubble-sort is not the fastest choice as a sorting algorithm, but it is the easiest to understand. For lists of a few thousand items, the bubble-sort will be fast enough. A simple IF/THEN comparison in a bubble-sort might look like this.
IF array(k) > array(k+1) THEN
temp(k)=array(k) 'Put the current element into a waiting room
array(k)=array(k+1) 'Replace the current element with the next element
array(k+1)=temp(k) 'Put the element from the waiting room here
END IF
If a swap is to be made, the current element must be held somewhere without being over written, then the next element is assigned here, followed by getting the value from the waiting room and assigning it to the next value. This completes the swap.
When you want to sort the array in reverse order, simply reverse the sign for the IF/THEN comparison. If you are sorting string values, use the $ to identify the array and array elements. If one field is a string, the entire array must be array$().
Caveat Emptor! JB/LB require arrays of mixed data (numerical and string) be constructed as string arrays. Numerical data in a string array will be ordered according to ASCII value, not the numerical value, that is, the ASCII value of 347 is less than 5, and 5 will follow 347 when the sort is completed. Numerical values can be "padded" with leading zeros, in which case they will be ordered according to actual numerical value.
The alternative is to convert numerical data from string to numerical value using the VAL() statement, or to use separate arrays for string data and numerical data. Either method can be used successfully, as long as the user is aware how Basic evaluates values.
The code above illustrates the routine to swap one element in an array, but how about an array of many elements?
FOR i=1 TO x
FOR j=1 TO (x-1)
IF array(j) > array(j+1) THEN
temp(j)=array(j)
array(j)=array(j+1)
array(j+1)=temp(j)
END IF
NEXT j
NEXT i
In this routine, x is the number of elements in the array. The loop, FOR i=1 TO x, will examine every element of the array. The loop, FOR j=1 TO (x-1), will compare the current element to the next element and swap them if they are out of order. Why is the 'j' loop one less than the 'i' loop? Because the 'j' loop compares this item to the next item. By the time we get to (x-1), the next item is the last item in the array and we don't wish to crash with an OS array(j) error.
So far, the code is written to sort an array of only one dimension. What if we have a multi-dimensioned array? The routine remains essentially the same, but additional code must be written to keep added data fields in the proper order.
FOR i=1 TO ln
FOR j=1 TO (ln-1)
IF myContacts$(j,fld) > myContacts$((j+1), fld) THEN
' = = = Put current record/fields into temporary fields
temp$(1)=myContacts$(j,1) 'The surname
temp$(2)=myContacts$(j,2) 'The christian name
temp$(3)=myContacts$(j,3) 'The age
temp$(4)=myContacts$(j,4) 'The phone number
' = = = Put the next record/fields into current fields
myContacts$(j,1)=myContacts$((j+1),1)
myContacts$(j,2)=myContacts$((j+1),2)
myContacts$(j,3)=myContacts$((j+1),3)
myContacts$(j,4)=myContacts$((j+1),4)
' = = = Put the temporary record/fields into the next record
myContacts$((j+1),1)=temp$(1)
myContacts$((j+1),2)=temp$(2)
myContacts$((j+1),3)=temp$(3)
myContacts$((j+1),4)=temp$(4)
END IF
NEXT j
NEXT i
This code sorts an array called myContacts$(), a simple file of names, ages, and telephone numbers. myContacts$() has ln records and fld fields for each record. The variable fld allows the user to select which field will be the "key" for the sorting routine if fld elements are out of sequence. When sorting myContacts(), it is essential that if one field is swapped, all fields are swapped.
You can modify the code above to suit any purpose. If there are 10 to 15 fields in your array and one record is to be swapped, include a line to put all fields of the current record into temp (the waiting room). Then assign the next value for every field into the current record, and lastly, put the temp values into the next record and field.
The re-assignments can be made with individual lines of code, as done here for clarity of explanation, or with multiple-statement lines of code, or even with "mini-loops" if your records have numerous fields.
The BAS code in this tutorial writes the sorted output to myContacts.txt and leaves myTestData.txt (for input) unchanged. In another lesson, we'll add routines to allow you to edit or add records to the existing myTestData.txt file.
When you understand the basics of sorting, you are ready to modify other algorithms for your use. See also FUNCTION jbSORT (http://justbasic.conforums.com/index.cgi?board=tutorial&action=display&num=1112900199) for a Quick Sort routine adapted to JB.
Feel free to modify any code to suit your own purpose.