[ Pobierz całość w formacie PDF ]
.2 Refined version of Count SortCount Sort(A, Rank)For Pass = 1 to Number of items by 1Set Value to A[Pass]Set Count to 0For Index = 1 to Number of items by 1Actions for each passIf A[Index] e" ValueIncrement CountSet Rank[Pass] to CountEnd Count Sort" During each pass, a Value is selected." That Value is then compared to all the items in the array and a Countis kept of the number of elements that are greater than or equal to theValue." The resulting Count is stored into the Rank array.Notice that all of the values used in this example were different, producing alldifferent ranks from 1 to N.If some values were repeated, then some rankswould be repeated, and some ranks would not correspond to any values.Forexample, if the value 8 were changed to 9, then there would be two itemshaving rank 2 and none having rank 1.Count Sort AnalysisWhenever you develop an algorithm, you should do two things:(i) Test it to make sure it works, and(ii) Analyze it to see how well it performs.An algorithm s performance can be measured in several ways.It can bemeasured through its execution time or through the storage space needed for thedata.This algorithm analysis can become quite complex, and a thoroughtreatment of this subject is beyond our scope here.However, a brief introductionto measuring algorithm performance, often called efficiency, is important.The time it takes for an algorithm to run is called its execution time.It isdirectly related to the number of operations it must perform.For example, inCount Sort, for an array of N values, the outer loop repeats N times and, foreach of these N times, the inner loop also repeats N times.Hence, the totalnumber of repetitions is N × N or N2.In our example, there were 81 repetitionsbecause the array had 9 elements.Since each repetition means one comparison,we can say that there were 81 comparisons.You can see that doubling the size of the array (say from 9 to 18) does not simplydouble the number of comparisons, but quadruples it (from 81 to 324).Thisquadratic growth results in a very slow sorting algorithm, especially for largesize arrays.Some computers are better than others for doing comparisons.In order tomeasure the algorithm s performance in a manner which is independent fromthe computers that run them, we must rate algorithms by assigning them ordersof complexity.We call time complexityan expression that gives us an estimateof the running time of the algorithm.For example, Count Sort requires about n2comparisons for sorting an array of n items.Such an algorithm is said to have acomplexity of order n-squared, denoted O(n2) read as big-oh of n-squared .This big-O notation defines an upper bound for the complexity of thealgorithms.More formally the big-O notation is defined as follows: Section 9.2 Sorting 421We say that g(n) is O(f(n)) if there exist two constants, C and k, such that:|g(n)| k.If a sort has a complexity of O(n3) it is definitely slower than Count Sort.Thebest general sorts have a complexity of O(n log2 n), which is far better thanO(n2).If the sorts are very specific and limited in some way, then theircomputing times could be shorter, possibly linear (of order O(n) ) or evenlogarithmic (of order O(log n) ).Space efficiencyis related to the amount of memory required.In the Count Sortalgorithm, a second array R is required for storing the ranks, so this Count Sortalgorithm is not the most economical of space.However, although the extraarray has N elements, if the original array were an array of records, the extraarray is likely to be much smaller since it only has to store Integers.The spaceefficiency of the algorithm might be acceptable after all.Of course, in ourspecific example, the rank array is as big as the original array (they bothcontain Integers), and the space efficiency might be considered to be somewhatweak.Swap SortThis family of sorts comprises a great number of variations on a common theme.We will introduce the Swap Sort theme on a specific and very well knownexample, the Bubble Sort.Bubble Sort involves the comparison of adjacent values in the array beingsorted, and swapping them if they are not in order.The top half of Figure 9.5shows the first pass over all the items of an original array A, where all pairsof adjacent items are compared.After this pass we can say that the array isslightly more sorted.Notice that the largest value (originally in position 4)has finished in the first position, which is where it should be.The results after each pass are summarized in the bottom half of Figure 9.5.Aswe see, after pass 1, the largest value (which is 9) has bubbled up to its finalposition at the top of the array, and everything else has shifted past it.Afterpass 2, the second largest value (which is 8) has bubbled down to the secondposition.This continues for each pass as shown by the shaded values.Thisbubbling action of each value leads to the name of this sorting method, BubbleSort .Note that after pass 4 all the values are already sorted, but the algorithmcontinues and does all 8 passes.Why? Because in a worst case scenario, thealgorithm actually requires N 1 passes for all N values to arrive at their finalpositions.To check this out, try sorting some values that are already sorted inreverse order (like A[9] = 9, A[8] = 8, etc.).Let s develop the algorithm top-down as usual, starting with a first draft of the algorithm.Pseudocode 9.3 First draft of our Bubble Sort algorithmBubble Sort(A, Size)For Pass = 1 to Size - 1 by 1Bubble largest value upEnd Bubble SortWe now need to refine the bubbling action, where we must pass through allpairs of adjacent elements, comparing and swapping them as we go along. 422 Chapter 9 Algorithms To Run WithPseudocode 9 [ Pobierz caÅ‚ość w formacie PDF ]