a. Suppose A[0···n1] just contains the numbers1,0,1. Design an algorithm that so

Question

a. Suppose A[0···n1] just contains the numbers1,0,1. Design an algorithm that sorts the elements of A in-place in O(n) time. That is, your algorithm shouldn’t use another array. The main operations should just involve swapping elements. b. We’ve discussed heapsort, mergesort and quicksort. (i) For each one, determine if it is stable or not. If yes, explain why; otherwise, provide an example that shows the algorithm is not stable. (ii) If the algorithm is not stable, describe a x you can make so the algorithm is stable.

Explanation / Answer

a.

Before beginning we need to plan how to proceed, so let us consider a mid-scenario:

(-1 -1 -1 -1) (0 0 0) -1 0 0 1 -1 0 1 -1 (1 1) where data within the parenthesis are sorted data, therefore we need three pointers a> begin0 b> end0 c> begin1 (I think the pointer names are self-explanatory)

So the position between end0 to begin1 is unsorted

Step 1: Initialize begin0 and end0 to zero, initialize begin1 to n-1 (n is size of array)

Step 2: if a[end0] == 0 goto step 4, else if a[end0] == 1 goto step 5

Step 3: if begin0 is not equal to end0 swap (begin0, end0) and finally increase begin0 and end0 by 1, and go to step 6

Step 4: just increase end0 and proceed to step 6

Step 5: swap (end0, begin1) and decrease begin1 by 1

Step 6: if end0 is less than or equal to begin1 go to step 2

Step 7: We have the array sorted

b. the algorithm is not stable. consider the following example:

Array                                    begin0         end0          begin1

-11 01 02 -12 11 12 03 -13                    0                0               7
-11 01 02 -12 11 12 03 -13                      1                1               7
-11 01 02 -12 11 12 03 -13                      1    2    7
-11 01 02 -12 11 12 03 -13                      1                3               7
-11 -12 02 01 11 12 03 -13                      2               4                7    //stabiliy is lost
-11 -12 02 01 -13 12 03 11                              2               4                6

. . .

To make the program stable, instead of performing swap in step 3 and step 5, we need to perform shift operation such that the relative position of similar items are not disturbed.

I hope you understood the algorithm. In case you dont, let me know.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.