[ Pobierz całość w formacie PDF ]
.The items of dataare sorted in increasing or decreasing order of a specific field called the sort key(numerical or alphabetical).The small sorts that we have seen in Chapter 7,Sort2 and Sort3, worked with a fixed number of items.Now, we want to beable to sort any number of items stored in an array.The sorting process can operate according to three different strategies, asillustrated in Figures 9.1, 9.2 and 9.3.We will assume that we want to sortnumbers in decreasing order here.Figure 9.1 Sort and copyGeneral Method Example21 12 54 48A A1A1 2 A3.An A2 A3.AnSort and copy Sort array A into BB1 B2 B3.Bn B1 B2 B3.Bnsorteditems ofarray AB1 > B2 > B3 >.> Bn 54 52 48 12 Section 9.2 Sorting 417" Sort and copy(Figure 9.1)This method sorts the items of array A and copies them in their properorder into another array, B.This method may waste space, since itneeds a second array as big as the original array to store the result.Theimportant thing to note is that the original array is preservedthroughout the sorting process.Figure 9.2 Sort and rank23 11 90 47A1 A2 A3.An A A2 A 3.An1Sort and rank Sort A showing rank in RR1 R2 R3.Rn R1 R2 R3.Rn positions ofsorted itemsIf A > Aj then i appearsi 3 18 11 22before j in array R" Sort and rank(Figure 9.2)Here, using A once again, we generate a second array R which containsthe rankof each sorted item.The rank is expressed as the position ofthe specific item in the original array A.For instance, in Figure 9.2, thehighest value in A is 90.So R1 refers to 90 by containing the positionthat 90 occupied in the original array, A: position 3.As for sort andcopy, this method preserves the original array but requires a secondarray.That second array is probably not as big as the original one sinceits elements are only Integers instead of complete records.Figure 9.3 Sort in place11 45 99 78A A1A1 2 A3.An A2 A3.AnSort in place Sort and destroy the values in AA1 A2 A3.An A1 A2 A3.An sorted itemsA1 > A2 > A3 >.> An 99 78 69 11." Sort in place(Figure 9.3)This technique is also known as sort in situor sort and destroy, since ituses only one array A.The final ordered values are placed back into A,thus destroying the original values in A.On the up side, this sorting inplace is economical of space, as it requires only one array. 418 Chapter 9 Algorithms To Run WithThe Four Methods of SortingFor each of these three fundamental strategies (Figures 9.1 to 9.3), there aremany different algorithms for sorting.All of them fall into one of thefollowing four categories:1.Count Sort, where enumerating and comparing occur;2.Swap Sort, where pairs of items are swapped;3.Select Sort, where extreme values are selected;4.Insert Sort, where moving and inserting of values occur.We will illustrate these basic sorting methods with specific algorithms in thefollowing sections.In order to simplify the algorithms, we assume that we willsort positive, non equal integer values into decreasing order.These algorithmscan be modified very easily to sort character strings in alphabetical order.Toillustrate the workings of our algorithms, we will use the first nine decimaldigits as the sequence of numbers to be sorted.The original sequence is asfollows:8, 5, 4, 9, 1, 7, 6, 3, 2You might have noticed that these values are sorted in alphabetic order(eight, five, four, nine, etc.).However, we wish to sort them into numericalorder.Count SortOne of the simplest sorting methods is Count Sort although it tends to beforgotten.This method finds the rank of all values in an array: the largestvalue has a rank of 1, the smallest has a rank of N (if all values are different).The top left part of Figure 9.4 shows the original array A before it is sorted.The rank of a value X is found by comparing it to all values in the array of Nelements, and counting the number of values that are greater than or equal tothat value X.The largest value has only one value (itself) equal to it, and sohas rank 1.The second largest has two values greater than or equal to it, and sohas rank 2.The smallest has all N values greater than or equal to it, and sohas rank N. Section 9.2 Sorting 419Figure 9.4 Count SortThere are only 2array elementsgreater than orequal to 8.Trace of Pass 1: Ranking A[1]Beforecounter trace for the first element (8) in AI A[I]1 8 C= 12 5 C = 13 4 C = 14 9 C = 2C = 25 16 7 C = 2C = 27 68 3 C = 29 2 C = 2After the first pass, the first value 8 has rank 2.RankAfterI R[I] R[I]1 2 2 2 2 2 2 2 2 22 5 5 5 5 5 5 5 56 6 6 6 6 63 61 1 1 1 14 19 9 9 95 96 3 3 3 34 47 48 7 79 8After pass = 1 2 3 4 5 6 7 8 9The first pass of the sort is shown in the top half of Figure 9.4.It takes the firstvalue, 8, and compares it to all of the values in the array (including itself).Itincrements a counter each time it finds a value that is greater than or equal to 8.1.In our case, it takes 8, compares it to the first value, 8, and puts thecounter at 1.2.Then, when it encounters the 9, the counter goes to 2.This determines that the first value, 8, has a rank of two because only twovalues are larger or equal to it.The bottom half of Figure 9.4 shows how theresults of each pass are used to build the Rank array.Nine passes are done inall, one for each value (N=9).Now that we have seen how the sorting process operates, we can develop analgorithm.We will proceed top-down, first defining a rough outline for theCount Sort algorithm.Pseudocode 9.1 Rough outline of Count Sort algorithmCount Sort(A, Rank)For Pass = 1 to Number of Items by 1Count values larger than or equal to A[Pass]Actions for each passSet Rank[Pass] to countEnd Count SortWe now refine this algorithm by giving the detail of the loop body
[ Pobierz całość w formacie PDF ]