Pre-requisites:

1. Experience applying L'Hospital's Rule in the form lim_{x → ∞} [ f(x) / g(x) ].

Goals:

1. To provide an application of calculus to computer science.
2. To experience, first hand, the growth in time to sort a list via bubble sort and via quicksort.
3. To use the "order" of a function to compare and measure growth rates.

Time is money. Computers save a lot of time, which makes them valuable. A two- gigahertz computer costs more than twice as much as an old one-gigahertz model. However, computer scientists know that the algorithm, or method, by which a computer performs a task is more important than the speed of the hardware. A fast machine will not make up for a slow algorithm.

A major problem in computer science is to measure the speed of an algorithm and to compare the speeds of different algorithms that do the same job. Of particular interest is the time needed for large jobs, since small jobs don't usually take long.

In this laboratory the job is to sort a list. When students register for a course their names are added to a course list, which is then sorted alphabetically. During the year new telephone customers are added to a database, which must be sorted before the next phone book can be published. Some applications may require sorting long lists hundreds or thousands of times per day.

For simplicity, this lab will sort a list of random numbers instead of names. We will use two different algorithms: BubbleSort and QuickSort.

The central question is whether QuickSort deserves its name. Is QuickSort significantly faster than BubbleSort? QuickSort requires considerably more programing than BubbleSort. Is it worth the extra effort? We first investigate the question experimentally and then confirm our results using L'Hospital's Rule.

Do all the parts below, but only turn in answers to questions 6-12 which should be done on a separate sheet of paper to hand in.

1. Start Maple. Make sure Maple is in Worksheet mode, not document mode. Copy and paste the following code into your Maple worksheet. The color is only for your own reference (Maple does not use purple). You may want to edit the purple characters, but probably not the red.

restart: with(plots):
ListLength:=10;                               	#Set the length of the list to sort.

with(RandomTools):
ListToSort:=Generate(list(integer,ListLength)):	#Create list of random numbers.
MyList:=convert(ListToSort,array);             	#Maple prefers arrays to long lists.

for 
 i from 1 
   to   min(5,ListLength) 
 do MyList[i] end do;                              	#Print the first part of MyList.

for 
 i from (ListLength-min(5,ListLength)-1) 
   to ListLength-1 
 do MyList[i+1] end do;                            	#Print the last part of MyList.

2. After pasting the code into Maple, press < enter > (or < return >). After Maple executes the commands, you should see a list of 10 integers followed by separate lists of the first and last 5 elements of the list. Find and identify all these features.
3. The values in the Maple code in purple are the parts that we will be editing. Experiment with different values of ListLength. Since we are interested in long lists, keep ListLength above 5.
4. Find the purple semicolon at the end of the line defining MyList. Change the purple semicolon, ;, to a colon, :, and back. What difference does it make when the line is executed? For a large value of ListLength, would you rather use a colon or semicolon?
5. When you are done experimenting, copy and paste the code below into Maple. This code sorts the list using BubbleSort and computes the time it takes. It also reprints the first and last parts of the list to verify it has been sorted. Try it for a list of length 10. Is the list completely sorted? [You will not be asked any questions about how BubbleSort works. However, the comments in the code should help you understand the general idea if you are interested.]

BubbleStart:=time():
for Top from ListLength to  2 by -1                	#Everything above Top is sorted.
do                                                 	#Next-largest element will "bubble"
                                                   	#up to Top. 

   for BubbleSpot from 1 to Top-1                  	#Bubble from bottom to Top.
   do
    if (MyList[BubbleSpot]> MyList[BubbleSpot+1]) 	#Check whether a swap is needed.
    then 
        Temp:=MyList[BubbleSpot];                  	#Swap: i.e. "bubble", the
        MyList[BubbleSpot]:= MyList[BubbleSpot+1]; 	#larger element
        MyList[BubbleSpot+1]:= Temp;               	#up by one position. 

    end if                                       #Position BubbleSpot+1 now contains
                                                 #the largest element in the list from
                                                 #position 1 to position BubbleSpot+1.
   end do;
end do;

BubbleTime:=time()-BubbleStart;

for 
 i from 1 
   to   min(5,ListLength) 
 do MyList[i] end do;                                   #Print the first part of MyList.

for 
 i from (ListLength-min(5,ListLength)-1) 
   to ListLength-1 
 do MyList[i+1] end do;                                 #Print the last part of MyList.

6. For short lists the time is so short it appears as nearly zero. Try lists of length 100, 200, 300, etc. and find the first one that requires 1 second or more for BubbleSort to sort the list. What is the length of the list you found?
7. You might expect BubbleSort to take about 2 seconds to sort a list twice as long and about 3 seconds to sort a list three times as long. Try it and see. Does it? [You may be surprised.] Describe what you find.
8. Copy and paste the code for QuickSort, below, into Maple. For lists of lengths 10, 25, and 50 find which method, BubbleSort or QuickSort, is faster.

   [As for BubbleSort, you will not be expected to explain how QuickSort works, but the comments in the code should help give you some idea if you are interested. Notice that the QuickSort code is significantly longer and more complex than the code for BubbleSort. CS270, Data Structures, covers these and other sorting methods thoroughly. ]

9. Repeat steps 6 and 7 using QuickSort instead of BubbleSort.

   
   Partition:=proc(List, LeftIndex,RightIndex,InitialPivotIndex)
   local PivotValue,temp,SmallIndex,i;
   
   PivotValue:=List[InitialPivotIndex];       #Find Pivot value.
   
   List[InitialPivotIndex]:=List[RightIndex]; #Swap Pivot value with Right value to
   List[RightIndex]:=PivotValue;              #temporarily put Pivot out of the way.
   
   SmallIndex:=LeftIndex;                     #First "small" element will go here.
   for i from LeftIndex to RightIndex-1
   do 
    if List[i]<=PivotValue 
     then
   
      temp:=List[SmallIndex];                 #Swap List[i] with List[SmallIndex]
      List[SmallIndex]:=List[i];
      List[i]:=temp;
   
      SmallIndex:=SmallIndex+1;               #Next "small" element will go here.
   
    end if;
   end do;
   
   List[RightIndex]:=List[SmallIndex];        #Swap PivotValue with first "large"
   List[SmallIndex]:=PivotValue;              #element. 
   
   SmallIndex;                                #Return correct index for Pivot value.
   
   end proc:
   QuickSort := proc(List, LeftIndex, RightIndex )
   local InitialPivotIndex,FinalPivotIndex;
   
   if (LeftIndex < RightIndex)                     #If not, List has 0 or 1 
                                                 #elements. Hence is sorted.
    then
     InitialPivotIndex:=round((LeftIndex+RightIndex)/2);        #Compute Pivot index
     FinalPivotIndex:=                                          #Find correct spot
                                                                #for Pivot value.
   
        Partition(List, LeftIndex,RightIndex,InitialPivotIndex);#Put smaller values
                                                                #on left and larger
                                                                #ones on right.
   
     QuickSort(List, LeftIndex,FinalPivotIndex-1);              #Recurcively sort
     QuickSort(List, FinalPivotIndex+1,RightIndex);             #the sublists on 
                                                                #each side.
   end if;
   
   end proc:
   MyList:=convert(ListToSort,array):            #Get fresh, unsorted copy of MyList.
   
   QuickStart:=time():
   QuickSort(MyList,1,ListLength);                #Execute the QuickSort proceedure
   QuickSortTime:=time()-QuickStart;
   
   for 
    i from 1 
      to   min(5,ListLength)
    do MyList[i] od;                        #Print the first part of MyList.
   
   for 
    i from (ListLength-min(5,ListLength)-1) 
      to ListLength-1 
    do MyList[i+1] od;                      #Print the last part of MyList.
   
   

10. One commonly measures the efficiency of different sorting methods by counting the number of comparisons needed to sort the list. For example, the number of times

    (if (MyList[BubbleSpot]> MyList[BubbleSpot+1])then ...)

    is executed in BubbleSort, or

    (if List[i]<=PivotValue then ...)

    is executed in QuickSort.

    The comparisons in QuickSort can be shown, on average, to increase like some constant times n ln(n), while the comparisons in BubbleSort increase like ½ n(n-1). Thus, since ln(n) increases very slowly, we'd expect the times taken by QuickSort to go up a little faster than linearly. Hence, we'd expect a list of length 2n to take a little longer than twice the time of a list of length n. Similarly we'd expect the times taken by BubbleSort to go up quadratically, i.e. more or less like the square of n. Does this prediction agree with your results in parts 6, 7 and 9? Explain.

11. Let f and g be two positive valued functions. If lim_{x → ∞} [f(x)/g(x)] = c, then for large values of x, [f(x)/g(x)) ≈ c, i.e. f(x) ≈ c g(x).

    If c≠0, we say f and g are of the same order. If either f or g is going to infinity so is the other. If either f or g is going to zero, so is the other. In general, f acts like a constant multiple of g for large values of x. We say f is "big oh" of g and write f=O(g).

    If c=0, then g is getting large much faster than f. For large values of x, f is much smaller than g. We say f is "little oh" of g and write f=o(g).

    L'Hospital's Rule can be used to determine c. Use L'Hospital's Rule to find out whether f(n)= n ln(n) is big or little oh of g(n)=½ n(n-1). What does this say about the relative speeds of BubbleSort and QuickSort?

12. There are certain "standard" functions that one can compare to and which serve as a yardstick for measuring growth rates. Some are given in the following list. Use L'Hospital's Rule or any other appropriate method to show that each function listed, a-f, is "little oh" of the one below it.
    1. 1
    2. ln(x)
    3. x
    4. x ln(x)
    5. x²
    6. x^m, m>2
    7. e^x