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.
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.
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.
[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. ]
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.
(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.
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?