RaysWebClass.Com: Lesson 34 A Matter of Order

RaysWebClass.Com

Lesson 34: A Matter of Order

The two most important things that computers can do is store stuff, and change the order of stuff. Data files are used to store stuff, Sort routine are used to put stuff in order. We'll go over one of the most famous sort routines: the Bubble Sort.

First we need to learn to swap values. Lets say we have A = 9 and B = 1, we want to swap A and B's values so that when we write A & B their values will be in "ascending" order (from smallest to largest.): 1 9. We may think to let A=B and then B=A will do the trick, but this will not work because the moment we let A=B we will have wiped out A's value and can no longer put it in B. So we need a temporary place to store A's value. If we let T=A we can save A's value. Now we can let A=B. And to get A's value into B we can let B=T. So, the whole thing will look like this: T=A:A=B:B=T (NOTE: These are three separate commands but they can be written together by using colons between them) Therefore, a ASP program that sorts two user number would look like this:

<%Option Explicit%>

<html>
<body>
<%
Dim A,B,T
A = request.Form("A")
B = request.Form("B")
If IsNumeric(A) And IsNumeric(B) Then
If A*1 > B*1 Then T=A:A=B:B=T
Response.Write "The Numbers in Order are:<br><br>"
Response.Write A & ", " & B
End If
%>
<form method="post" action="asp34.asp">
Enter a value for A: <input type="number" name="A" size="5"><br><br>
Enter a value for B: <input type="integer" name="B" size="5"><br><br>
<input type="submit" value=" Sort ">
</form>
</body>
</html>

If IsNumeric(A) And IsNumeric(B) Then - tests the content of A and B to see if they are numbers. (IsNumeric return a True only if the variable is a number.)
If A*1 > B*1 Then - test to see if the value of A is greater then the value of B. (A*1 will convert A which is a string to a number)
If A is greater then B then values are swapped: T=A:A=B:B=T

If we add another number: C we now have to use three if statements:

If A > B Then T=A:A=B:B=T
If A > C Then T=A:A=C:C=T
If B > C Then T=B:B=C:C=T

A B C D would look like this:

If A > B Then T=A:A=B:B=T
If A > C Then T=A:A=C:C=T
If A > D Then T=A:A=D:D=T
If B > C Then T=B:B=C:C=T
If B > D Then T=B:B=D:D=T
If C > D Then T=C:C=D:D=T

And A B C D E would look like this:

If A > B Then T=A:A=B:B=T
If A > C Then T=A:A=C:C=T
If A > D Then T=A:A=D:D=T
If A > E Then T=A:A=E:E=T
If B > C Then T=B:B=C:C=T
If B > D Then T=B:B=D:D=T
If B > E Then T=B:B=E:E=T
If C > D Then T=C:C=D:D=T
If C > E Then T=C:C=E:E=T
If D > E Then T=D:D=E:E=T

Note how we check the first value against all the others values after it, and then the second value with all the other values after it. We continue this until we have only the second to last value and we check it against the last value and we're done! As you can clearly see, every time we add another number we substantially increase the number of If Statements as the following table shows:

Variables If Statements
2 1
3 3
4 6
5 10
6 15
7 21
8 28
9 36
10 45

If we had 8 million numbers to sort in 1965, using this method, we would still be writing the code! AND where do we start storing number beyond Z? In AA? What about 8 million?

We sort millions upon millions of names and numbers everyday. How do we do this? Well to answer this question we need to learn two things: A better was to store data, and a shorter sort routine.

Arrays

An Array is a better way to store large amounts of data. Instead of using A B C we can store all the data is A! let A(1) = 9 and A(2) = 6 and A(3) = 12. Where would the 8 millionth number be stored? In A(8000000)! This, be the way, is pronounced: A(1) "A sub 1" and this A(8000000) "A sub 8 million" How can we find the 500^th number? Response.Write A(500) As you can see, its an easy and organized way to store large amounts of data. The only monkey wrench is you have to know how many number you want to store before you can start. In the Dim statement you define an array like this: Dim A(800) where 800 is the maximum number of "elements" in the array. This has other advantages too. Suppose I want to write all the number to the browser. Instead of: Response.Write A(1) Response.Write A(2) Response.Write A(3) ... I can write them all out in three lines:

For X = 1 to 800
Response.Write A(X)
Next

(X is a variable whose value runs from 1 to 800. The first time around X is 1, so A(X) is A(1). The second time around X is 2, so A(X) is A(2). All the way through to 800.)
You can also use this method to read-in the values:

X = 0
Do Until txtFile.EndofStream
X = X + 1
A(X) = txtFile.ReadLine
Loop

Now that we know how to use arrays, we can look at the Bubble Sort.

The Bubble Sort

' * * * * * * * * * * * * * * * * *
' * T H E B U B B L E S O R T *
' * * * * * * * * * * * * * * * * *
' *** Set Z to the number of elements to sort ***
Z = 100
Dim A(Z), X, Y, T
For X = 1 to (Z-1)
For Y = (X+1) to Z
If A(X) > A(Y) Then
T = A(X) : A(X) = A(Y) : A(Y) = T
End If
Next
Next
' *** End BUBBLE SORT ***

The Bubble Sort does as our little example does, it checks the first element with all the other elements behind it e.g. when X is 1, Y is 2 ... Z. The If statement tests A(X) (where X is 1) with A(Y) (where Y is 2 through Z). If any of the value are out of order T = A(X) : A(X) = A(Y) : A(Y) = T swaps it. When For Y runs out, For X sets X to 2, now Y is 3 to Z. And so on till X is Z-1 (the second to last element) and Y is Z (the last element.) The routine will check these last two and then its done, the elements are all in order!

Variables	If Statements
2	1
3	3
4	6
5	10
6	15
7	21
8	28
9	36
10	45

Web Page Design: Exercise 34

Write an ASP program that reads the names from the list.txt file in to an Array and writes them out to the browser. Then sorts the Names in alphabetical order and writes them again out to the browser. Now write the names out a third time, this time First Name First. Use Horizontal Rules between each listing and an explanation as to what the listings are.

Save the file in the wwwroot folder as asp34.asp.