1. Short programming assignment. Implement the binary quicksort where Item is an

Question

1. Short programming assignment. Implement the binary quicksort where Item is an integer in the range 0 - 32,767 (that is, fifteen bits). You will need to write a digit function to extract a particular bit from an integer. Test your function on an array of randomly generated integers.

2. Consider the following sorting scenarios. Which is more appropriate for a radix sort, and why?

a. An input file with 100 records. The records are to be sorted on a 256-bit key.

b. An input file with 10000 records. The records are to be sorted on a 16-bit key.

3.The following refers to the perfect shuffle and unshuffle operations.

a. Perform a perfect shuffle on the following: F G T E A H I W A B T D K U Q Z

b. Perform a perfect unshuffle on the following: J E Y B D A H I Y K E Q B T S L

4. Explain how Batcher’s odd-even merge actually merges two subfiles while only exchanging adjacent locations in the array.

5. Design a sorting network for a file of five elements. Demonstrate, in the manner of figure 11.4, that your network would correctly sort a file starting in reverse order such as E D C B A.

6. Show in the style of figure 11.12 a 4-way balanced merge sort on the following file, with initial sort size of 3.    A S O R T I N G P R O B L EM W I T H E N O U G H K E Y S

7. How many parallel steps (as defined in property 11.8) would be required to sort 100,000 records using 32 processors?

8. For the following set of numbers, perform both a MSD and LSD radix sort. Show the resulting column of numbers after each pass (each digit).

1143

7788

8478

6352

6323

6478

1253

2235

2834

4443

Explanation / Answer

1)
def quicksortB(int a[], int l, int r, int w){
   int i = l, j = r;
   if (r <= l || w > bitsword) return;
   while (j != i){
        while (digit(a[i], w) == 0 && (i < j)) i++;
        while (digit(a[j], w) == 1 && (j > i)) j--;
        swap(a[i], a[j]);
    }
    if (digit(a[r], w) == 0) j++;
    quicksortB(a, l, j-1, w+1);
    quicksortB(a, j, r, w+1);
}

2. Radix sort is good for 1st scenrio as we have 100 entry with 256-bit key, so there will be less collisions.

3.

To perfect shuffle F G T E A H I W A B T D K U Q Z"
first save them in array
char l[] = {F G T E A H I W A B T D K U Q Z};
for i = n-1 to 1:
   j = random integer between 0 and i;
   swap(a[j],a[i])
end

4.
To perfect shuffle F G T E A H I W A B T D K U Q Z"
first save them in array
char l[] = {J E Y B D A H I Y K E Q B T S L};
not sort the array so that all become in original order("default");
def unshuffle(l):
   l = sorted(l)
   return l

5. No Image
6. No Image
7. Step taken is (Log 2 100000)
8.

LSD
least significant digit first
Step 1 :- 6352, 1143, 6323, 1253, 4443, 2834, 2235, 7788, 8478, 6478
Step 2 :- 6323, 2834, 2235, 1143, 4443, 6352, 1253, 6478, 8478, 7788
Step 3 :- 1143, 2235, 1253, 6323, 6352, 4443, 6478, 8478, 7788, 2834
Step 4 :- 1143, 1253, 2235, 2834, 4443, 6323, 6352, 6478, 7788, 8478

MSD
Most signifincant digit first
Step 1 :- 1143, 1253, 2235, 2834, 4443, 6352, 6323, 6478, 7788, 8478
Step 2 :- 1143, 1253, 2235, 6352, 6323, 4443, 6478, 8478, 7788, 2834
Step 3 :- 6323, 2234, 2834, 1143, 4443, 1253, 6352, 6478, 8478, 7788
Step 4 :- 6352, 6323, 1143, 4443, 1253, 2234, 2834, 6478, 8478, 7788

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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