Scribd
Upload
32 views15 pages

Subset and N Queens Problem

Analysis and algorithm design notes

Uploaded by

samaira96919691
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
32 views15 pages

Subset and N Queens Problem

Analysis and algorithm design notes

Uploaded by

samaira96919691
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
You are on page 1/ 15
7.1 Sorting by Counting As a first example of applying the input enhancement technique, we discuss its application to the sorting problem. One rather obvious idea is to count, for each element of a list to be sorted, the total number of elements smaller than this element and record the results ina table. These n of the elements in the sorted list: e.g., if the count is 10 for some element, it should be in the 11th position (with index 10, if we start counting with 0) in the sorted array. Thus, we will be able to sort the list b : nanan st by simply copying its elements to theit appropriate positions in a new, sorted list. This algorithm is called comparison counting sort (Figure 7.1). umbers will indicate the positions Spaco and Time Tradeoffs 239 Array AIO. 51 (ez [ ar [aa [oa [9 | 47 Initially Countti[O [oo [0 ]0 [0 Alter pass =O — Countil [3 [Oo |1 {1} 0] 0 After pass i = 1 Count {} 1 2 2 [0 1 After pass i = 2 Count II 4/3 [0 1 Afterpassi =3 Count! 5 [ott Afterpassi=4 — Counti] o}2 Final state Count |] [73 1 4[5[o[2 Array S10..5) 19 [31 [47 [62 | 84 | 96 FIGURE 7.1 Example of sorting by comparison counting ALGORITHM = ComparisonCountingSort(A[0..n — 1) HSorts an array by comparison counting Mnput: An array A[0..1 — 1] of orderable elements Output: Array S{0..n — 1] of A’s elements sorted in nondecreasing order fori — 0 ton — 1 do Count{i] <0 fori —Oton—2do forj —i+1ton—1do if Afi] < AU] Count{j] — Countlj} +1 else Count{i] — Count{i] +1 for i — Oton — 1 do S{Count{i]] < Ali) return S What is the time efficiency of this algorithm? It should be quadratic because the algorithm considers all the different pairs of an n-element array. More for- mally, the number of times its basic operation, the comparison Ali] < Alj] executed is equal to the sum we have encountered several times already: 2 nel ad a2 4 cme D1 = Diep G4 += Dat -pe Me, in0 jail is iso is Since the algorithm makes the same number of key comparisons as selection sort and in addition uses a linear amount of extra space, it can hardly be recommended for practical us But the counting idea does work productively in a situation in which elements to be sorted belong to a known small set of values, Assume, for example, that we have to sort a list whose values can be either | or 2, Rather than appl general sorting algorithm, we should be able to take advantage of this addi information about values to be sorted, Indeed, we ean sean the list to compute the number of I's and the number of 2's in itand then, on the second pass, simply make the appropriate number of the first clements equal to Land the remaining clements equal to 2. More generally, if element values ure integers between some of Algorithms Introduction to the Design & Anc Jower bound Zand upper bound 1. we can compute the frequency of each of those values and store then: in array FTO. ~ fl. Then the first F(0] positions in the verted list must be filled with /, the next F[1] positions with J+ 1, and s0 on, Ai this can be done, of course, only if we can overwrite the given elements, Let us consider a more realistic situation of sorting a list of items with some other information associated with their keys so that we cannot overwrite the lis’, elements. Then we can copy elements into a new array S{0..n—1] to hold the sorteg list as follows. The elements of A whose values are equal to the lowest possible value fare copied into the first F[0] elements of S, i.c., positions 0 through F(0]—1 the elements of value / + | are copied to positions from F[0] to (F[0] + F[1}) — 1 and so on, Since such accumulated sums of frequencies are called a distribution in statistics, the method itself is known as distribution counting. EXAMPLE Consider sorting the array 13 | 11} 12} 13] 12 | 12 whose values are known to come from the set (11, 12, 13} and should not be overwritten in the process of sorting. The frequency and distribution arrays are as follows: Array values W122 13 —____ Frequencies lesen? Distribution values 1 4 6 Sees Note {hat the distribution values indicate the proper positions for the last occur- a . ey pene in the final sorted array. If we index array positions from 0 ~ I, the distri Piel ibution values must be reduced by 1 to get corresponding element It i i iS the to venient to process the input array right to left. For the exam- 12 in position 4" td Pa and, since its distribution value is 4, we place this = 3 of the array S$ that will hold the sorted list. Then we M|npur: An array Al0..n — Nofi Imited range by distribution counting Output: Array Sl0.n ~ Lop qn ees Oeween Land w (I 15 34+7<15 sdution x 8<15 for its termination or, if all the solutions need to be found, continue by backtracking to the node’ Parent. If s’ is not equal to d, we can terminate the no s u ; de as nonpromising if either of the following two inequalities holds: 8’ + Si, > d(the sums is too large) n s+ > 5;

You might also like