ZuoTi.Pro
Question

(20 points) Consider the following strategy for choosing a pivot element for the Partition subroutine of QuickSort, applied tAnd the related algorithms:

QUICKSORT(A, p, r) 1 if p <r 9 %3 PARTITION(A, р, r) QUICKSORT(A, р,q — 1) QUICKSORT(A, q+1,г) 2 4PARTITION (A, p, r) 1 x = A[r] 2 = p -1 3 forj p to r - 1 if A]x i = i +1 exchange A[i] with A[j] 5 6 1] with A[r] exchange A

(20 points) Consider the following strategy for choosing a pivot element for the Partition subroutine of QuickSort, applied to an array A. .Let n be the number of elements of the array A. If n 24, perform an Insertion Sort of A and return. Otherwise: Choose 2n/2)| elements at random from n; let S be the new list with the chosen elements. Sort the list S using Insertion Sort and use the median m of S as a pivot element pivot Partition using m as a Carry out QuickSort recursively on the two parts. (a) How much time does it take to sort S and find its median? Give a 0 bound. (b) If the element m obtained as the median of S is used as the pivot, what can we say about the sizes of the two partitions of the array A? (c) Write a recurrence relation for the worst case running time of QuickSort with this pivoting strategy
QUICKSORT(A, p, r) 1 if p
engineering   Computer-Science   
0 0
Add a comment Improve this question Transcribed image text
Next > < Previous
Sort answers by oldest

Homework Answers

Answer #1

a). tist s contain te know that to sotn clements uiing insetiom sorut ime eauieal is nlnt) = B(n) 2-fn elenens. 20, to sort

0 0
Add a comment
Know the answer?
Add Answer to:
And the related algorithms: (20 points) Consider the following strategy for choosing a pivot element for...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions

  • In an effort to balance the distribution (length) of partitions created in the Quicksort algorithm so...

    In an effort to balance the distribution (length) of partitions created in the Quicksort algorithm so that worst case performance can be avoided, one can employ randomization, rather than selecting the element at a certain position as the pivot. Use your favorite programming language to implement the randomized Quicksort algorithm. So, you will need to use the following algorithms to implement it: RANDOMIZED-PArtitioN (A, p, r) 1 i = RANDOM (p, r) 2 exchange A[r] with A[i] 3 return PARTITION...

  • c++ please read all question edit the program to test different random sizes of the array and give me the time in a file will be like random size of the array and next to it the time it took for each...

    c++ please read all question edit the program to test different random sizes of the array and give me the time in a file will be like random size of the array and next to it the time it took for each size Im trying to do time analysis for Quick sort but i keep getting time = 0 also i want edit the program to test different random sizes of the array and give me the time in a...

  • (20 points) Recall the following deterministic select algorithm: (a) Divide the n elements into groups of...

    (20 points) Recall the following deterministic select algorithm: (a) Divide the n elements into groups of size 5. So n/5 groups. (b) Find the median of each group. (c) Find the median x of the n/5 medians by a recursive call to Select. (d) Call Partition with x as the pivot. (e) Make a recursive call to Select either on the smaller elements or larger elements (de- pending on the situation); if the pivot is the answer we are done....

  • Suppose the quicksort program shown uses a partition function that always picks a[m] as the 5B....

    Suppose the quicksort program shown uses a partition function that always picks a[m] as the 5B. 2M separator v. When the array a[m],....a[n] is reordered, assume that the order is preserved as much as possible. That is, first come all the elements less than v, in their original order, then all elements equal to v, and finally all elements greater than v, in their original order. int a[11]; void readArray0 {/* Reads 9 integers into int I; void quicksort( int...

  • Data Structure Question. I need help solving this question. I know quicksort has the worst case...

    Data Structure Question. I need help solving this question. I know quicksort has the worst case of O(n^2) if it is implemented choosing the pivot as the first element. A[1] is the first element here. Please justify why the number of comparison is the smallest possible number assuming the array ensures that. And give an example of that type of an array. Thank you thumbs up will be given for correct and justified answer! qs(A): if A has at most...

  • Question 5 (10 points) Below is the PARTITION(A, p. r) pseudocode where pivot is always selected...

    Question 5 (10 points) Below is the PARTITION(A, p. r) pseudocode where pivot is always selected as the last element and array A=(-23,7,-14,1,5,1). a. Illustrate the PARTITIONCA, P.7) module operation like below when call it with the above array A. Show clearly the position of i and ; in each picture. Pj PARTITIONCA, p,r) 1. x=A[r] 2. i=p - 1 3. for j =p tor-1 4. if Allsx 5. i=i+1 exchange A[i] with AD 7. exchange A[i+1] with 4[r] 8....

  • 7.11 LAB: Sorting user IDs Given a main() that reads user IDs (until -1), complete the...

    7.11 LAB: Sorting user IDs Given a main() that reads user IDs (until -1), complete the quicksort() and partition() methods to sort the IDs in ascending order using the Quicksort algorithm, and output the sorted IDs one per line. Ex. If the input is: kaylasimms julia myron1994 kaylajones -1 the output is: julia kaylajones kaylasimms myron1994 Code: import java.util.Scanner; import java.util.ArrayList; public class UserIDSorting { // TODO: Write the partitioning algorithm - pick the middle element as the // pivot,...

  • quickSort function. Calling previous functions already implemented. This is a bit different type of quicksort function...

    quickSort function. Calling previous functions already implemented. This is a bit different type of quicksort function where my partition function has 3 parameters instead of 4. So I need to write a function quicksort that actually puts all 3 of my functions together and finalizes the sorting process "There should be almost nothing done besides calling the other 3 functions and recursively calling itself (except to check for basecase) class quicksort { private: int left; int right; int* array;   ...

  • Implement quicksort and bucket sort. Use the code in your book to help; the partition in...

    Implement quicksort and bucket sort. Use the code in your book to help; the partition in quicksort is tricky. Make sure your implementations are correct — it is easy to gain some confidence in the correctness of your code by writing a program which creates arrays filled with random numbers, sorts them, and then checks that they are sorted. Then time your code (using clock() or similar methods) on both methods for arrays filled with random integers of the following...

  • Sorting Sort the following array using the quick sort algorithm: (4 Marks) a. 12 26 8...

    Sorting Sort the following array using the quick sort algorithm: (4 Marks) a. 12 26 8 9 7 0 4 Pivot selection is defined to be the first element of each sub-list. Show the array before and after each quicksort round (when the array is partitioned after placing the pivot at its correct position). Also, clearly highlight the pivot in each partition b. Consider an unsorted array of integers of size n. Write a Java program to arrange the array...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT