270 Part V: Algorithms: Telling the Computer What to Do

Measuring efficiency with Big-O notation

To measure the efficiency of specific algorithms, computer scientists created something known as Big-O notation. Essentially, Big-O notation measures the speed of a particular algorithm (such as a sorting algorithm) based on the number of items it must manage.

If you have an algorithm that sorts a list of names alphabetically, for example, the speed of that algorithm depends on the number of names to search. In Big-O notation, you express this relationship as O(N), where O stands for “order of magnitude” and N stands for the total number of items the algorithm must manage.

The way that programmers determine the Big-O notation of a particular algorithm depends on that algorithm’s speed of execution and the number of items it must handle. For example, if an algorithm’s speed of execution and number of items (N) it can handle is expressed as N2 + N + 1, the Big-O notation for this algorithm is O(N2).

In calculating the Big-O notation for an algorithm, you choose the fastest-growing item

(in this case, N2) and ignore the rest of the expression. (Naturally, if you use the wrong expression to represent your algorithm, your Big-O notation is wrong as well.)

Programmers often use Big-O notation to measure the average and worst-case scenarios as they study how an algorithm behaves while managing a typical number of items and how that same algorithm behaves while managing an extremely large number of items.

Not surprisingly, some algorithms are fast at managing relatively small numbers of items but slow down rapidly if you force them to manage a large number of items. Curiously, other algorithms are very fast and efficient in sorting items that are almost correctly sorted initially but slow if sorting items that you randomly scatter in the list.

Programmers study the average and worstcase scenarios of an algorithm by using Big-O notation to help them choose the algorithm that’s best suited for their particular program.

Insertion Sort

Imagine that you’re playing cards and the dealer deals the cards to you. As soon as you get two cards, your first inclination is probably to sort those two cards in relation to one another (perhaps by suit or by number). After the dealer gives you a third card, you sort that card in relation to your previous two cards. You sort each additional card that you receive in relation to your previously sorted cards. This method is how an insertion sort works (see Figure 20-1). From the computer’s point of view, the insertion sort algorithm works as follows:

1.It compares the first two items in the list and sorts those two items.

2.It looks at the next item in the list and sorts that item in relation to the previously sorted items.

Chapter 20: Sorting 271

3.It repeats Step 2 for each additional item in the list until it finishes sorting the entire list.

		Initial list	15	4	78	29	16
Figure 20-1:
An insertion
			4	15	78	29	16
sort
removes
one item at			4	15	78	29	16
a time and
sorts it in
			4	15	29	78	16
relation to
the previous										Sorted portion of the list
sorted items
			4	15	16	29	78			Unsorted portion of the list
in the list.

To see for yourself how the insertion sort algorithm works, try the following program:

MaxSize = 5

REDIM MyArray(MaxSize)

FOR I = 1 TO MaxSize

MyArray(I) = INT(RND(1) * 100) + 1

PRINT MyArray(I); SPACE$(1);

NEXT I

PRINT “(Initial array)”

FOR ArrayPos = 2 TO MaxSize

TempValue = MyArray(ArrayPos)

StopNow = 0

Count = 1

Time2Stop = 0

WHILE (Time2Stop = 0)

IF TempValue < MyArray(Count) THEN

FOR J = ArrayPos TO Count STEP -1

MyArray(J) = MyArray(J - 1)

NEXT J

MyArray(Count) = TempValue

StopNow = 1

FOR I = 1 TO MaxSize

PRINT MyArray(I); SPACE$(1);

NEXT I

PRINT

END IF

272 Part V: Algorithms: Telling the Computer What to Do

Count = Count + 1

IF (StopNow = 1) OR (Count = ArrayPos) THEN

Time2Stop = 1

END IF

WEND

NEXT ArrayPos

FOR I = 1 TO MaxSize

PRINT MyArray(I); SPACE$(1);

NEXT I

PRINT “(Sorted array)”

END

A typical output for this program appears as follows:

44 4 98 99 26 (Initial array)

4 44 98 99 26

4 26 44 98 99

4 26 44 98 99 )Sorted array)

The insertion sort program works as follows:

1.The first through seventh lines create the variable MaxSize, which equals 5; create the array MyArray to hold five integers; generate a random number; create a random number between 1 and 100; store it in the array MyArray; and then print the array on-screen along with the string (Initial array).

2.The eighth line is the start of a FOR-NEXT loop that starts counting from the second item in the array, using the variable ArrayPos.

3.The ninth line creates the variable TempValue and stores the value in the array location that the ArrayPos variable designates. At the beginning of this FOR-NEXT loop, the value of TempValue is equal to the second item in the array.

4.The tenth line creates the variable StopNow and sets its value to zero. You use the StopNow variable later in the program to tell the computer that it’s already moved a number to its correctly sorted position in the array.

5.The eleventh line creates the variable Count and sets its value to one. You use the Count variable to locate where in the array to move the number that the TempValue variable stores.

6.The twelfth line creates the variable Time2Stop and sets its value to zero. You use the Time2Stop variable to tell the program when the array is completely sorted.

7.The thirteenth line is the start of a WHILE-WEND statement that checks whether the value that the Time2Stop variable stores is still equal to zero. If so, all the instructions inside the WHILE-WEND statements run.

Chapter 20: Sorting 273

8.The fourteenth line is the start of an IF THEN statement that checks whether the value that the TempValue variable (which represents the number that you want to sort) stores is less than the value that the array position that the Count variable specifies stores. The first time that this line runs, it checks whether the second item in the list is less than the first item.

9.The fifteenth through seventeenth lines form a FOR-NEXT loop that moves each item in the array down (to the right) one position to make room for inserting the TempValue number in its sorted place in the array.

10.The eighteenth line moves the number that TempValue stores to its newly sorted position in the array location that the Count variable specifies.

11.The nineteenth line sets the value of the StopNow variable to 1. This line tells the computer that it’s correctly sorted the number that the TempValue variable stores.

12.The twentieth through twenty-third lines print the partially sorted array on-screen so that you can see its progress.

13.The twenty-fourth line is the end of the IF THEN statement that starts on the fourteenth line.

14.The twenty-fifth line increases the value of the Count variable.

15.The twenty-sixth through twenty-eighth lines check to see whether the StopNow variable is equal to one or whether the Count variable is equal to the value that the ArrayPos variable stores. If so, the Time2Stop variable is set to one.

16.The twenty-ninth line is the end of the WHILE loop that begins on the thirteenth line.

17.The thirtieth line is the end of the FOR loop that begins on the eighth line.

18.The thirty-first through thirty-fourth lines print the final sorted array onscreen, along with the message (Sorted array).

19.The thirty-fifth line tells the computer that the program is at an end.

Bubble Sort

The bubble-sort algorithm bears that name because individual items in a list appear to “bubble up” to their correct locations. The bubble-sort algorithm examines a list of items repeatedly and sorts adjacent items until it sorts the entire list, as shown in Figure 20-2. Your computer handles a bubble-sort algorithm as follows:

274 Part V: Algorithms: Telling the Computer What to Do

Figure 20-2:

The bubble sort examines each item in a list and sorts it in relation to its neighbor.

1.It compares the first two items in the list and sorts those two items.

2.It moves to the next item in the list and sorts that item with the last item of the previously sorted pair.

3.It repeats Step 2 for each additional item in the list until the entire list is examined.

4.It repeats Steps 1 through 3 until the entire list is sorted.

Initial list	15	4	78	29	16
	4	15	78	29	16
	4	15	78	29	16
	4	15	29	78	16
	4	15	29	16	78
	4	15	29	16	78
	4	15	29	16	78			Sorts these two items
	4	15	16	29	78
	4	15	16	29	78	Sorted list

One drawback to the bubble-sort algorithm is that it often must re-examine a list two or more times before it correctly sorts all items (refer to Figure 20-2).

To see for yourself how the bubble-sort algorithm works, look at the following program:

MaxSize = 5

REDIM MyArray(MaxSize)

FOR I = 1 TO MaxSize

MyArray(I) = INT(RND(1) * 100) + 1

PRINT MyArray(I); SPACE$(1);

NEXT I

PRINT “(Initial array)”

Pass = 1

Time2Stop = 0

WHILE (Time2Stop = 0)

NoSwaps = 1

FOR I = 1 TO (MaxSize - Pass)

IF MyArray(I) > MyArray(I + 1) THEN

TempValue = MyArray(I)

MyArray(I) = MyArray(I + 1)

Chapter 20: Sorting 275

MyArray(I + 1) = TempValue

NoSwaps = 0

FOR J = 1 TO MaxSize

PRINT MyArray(J); SPACE$(1);

NEXT J

PRINT

END IF

NEXT I

IF NoSwaps = 1 THEN

Time2Stop = 1

END IF

WEND

FOR I = 1 TO MaxSize

PRINT MyArray(I); SPACE$(1);

NEXT I

PRINT “(Sorted array)”

END

A typical output for this program looks as follows:

5 19 61 26 27 (Initial array)

5 19 26 61 27

5 19 26 27 61

5 19 26 27 61 (Sorted array)

The following list breaks down the workings of the bubble-sort program:

1.The first through seventh lines create the variable MaxSize equal to 5, create the array MyArray to hold five integers, create a random number between 1 and 100, store it in the array MyArray, and then print the array on-screen along with the string (Initial array).

2.The eighth line creates the variable Pass and sets its value to 1.

3.The ninth line creates the variable Time2Stop and sets its value to 0.

4.The tenth line starts a WHILE-WEND loop that continues while the value of the Time2Stop variable is equal to zero.

5.The eleventh line creates the variable NoSwaps and sets its value to 0.

6.The twelfth line creates a FOR-NEXT loop that repeats (5 - Pass) times. The first time that the FOR-NEXT loop runs, it repeats four times. The second time, it repeats three times, and so on.

7.The thirteenth line tells the computer, “Check the value of an array item with the item next to it.” The first time that this IF THEN statement runs, it checks the first item with the second item in MyArray.

8.The fourteenth through sixteenth lines switch two numbers that MyArray stores next to each other.