hw2-2

pdf

School

University of British Columbia *

*We aren’t endorsed by this school

Course

221

Subject

Computer Science

Date

Jan 9, 2024

Type

pdf

Pages

Uploaded by AdmiralStrawCrocodile17

Question 2: Sorting Quickly In practice, Quick Sort is one of the fastest sorting algorithms. In this problem, we teach you the algorithm and begin to examine its theoretical properties. You will learn more about Quick Sort in future courses. Scrutinze the code for function gsort below. It employs a helper function called partition whose functionality we describe in detail later. Assume that you are also given a function void swap(int & a, int & b) that can be used to exchange the datain a vector. void gsort(vector<int> & x, int lo, int hi) if (lo < hi) { int pivot = partition(x, lo, hi); gsort(x, lo, pivot-1); gsort(x, pivot+l, hi); -} } Which of the following sorting algorithms does gsort most closely resemble? (a) Merge Sort C] (b) Insertion Sort (c) Selection Sort Even before we give a robust analysis of Quick Sort, we know a significant lower bound for its running time. Which of the following is the greatest lower bound for Quick Sort's worst case running time (Hint: quick sort is a comparison based sorting algorithm)? (@) 2(n?) (b) Q(nlogn) (] (© Q(n) (d) Q(logn) (e) (1) Consider the following nearly complete helper function: int partition(vector<int> & x, int lo, int hi) { int p = lo+1; for( int i=lo+l; i <= hi; i++ ) if( x[1] < x[1o] ) { swap(x[p], x[1]); ++p; } // What Lline of code is missing here? return p-1; Any partition algorithm should do the following: 1. Pick an array element, and call it the pivot. 2. Rearrange the array so that all elements less than the pivot occur before it, and all elements greater than (or equal to) the pivot occur after it. 3. Return the proper location of the pivot. Given this algorithm, what is partition's missing line of code? (Include the semicolon at the end of the line!) line 5: | swap(x[lo],x[p-11); © The running time of the Quick Sort algorithm depends on the partition function. Consider the general partition algorithm we described, and suppose that we always choose the first element in the sub-array, Allo], as our pivot. Suppose also that we implement the partition algorithm so that the relative order between the elements in each partition is maintained. For example, if elements x and y are less than A[lo] and z occurred before ¥ in the original array, then x occurs before y after the partition step,

and they both occur before the pivot. This adaptation does not change the asymptotic running time of the function, but it does change its memory footprint. We are not concerned with that issue here. (Note that our given code for partition does not maintain the relative order of the elements.) Suppose the array that you would like to sort includes the following elements in some order: 83 10 82 37 70 92 §| Give three different arrangments of these elements, each of which would induce worst case running time for quick sort, using our most recent version of partition. A— [ 92 83 82 70 37 10 8 ] o < 4 A= [ 8 10 37 70 82 83 92 ] o < 2 A= [ 92 8 83 10 82 37 70 ] e 4 2 Write the recurrence that corresponds to this worst case behavior. In any case where you would normally choose an arbitrary constant, please use 1. Furthermore, in the T'(n) recurrence line below, there are two recursive terms. If one argument is larger than the other, please enter it first (in the left cell). In the final blank of the T'(n) recurrence line below, enter only the highest- order term. E.g., if you think the answer is n? 4+ nlgn, you would enter just n?. T(0)=T(1) = - @ (). Tn)=T( n1 @ (g )+T( @ () )+ n @ (). n > 1 Find a closed form solution to this recurrence; T(n) =0( nr @ () ) Now suppose in every recursive call to sort a subarray, we choose a pivot in time proportional to the size of the subarray, and that pivot is never one of the smallest 1/4 or largest 1/4 elements. What is the worst case running time of Quick Sort on inputs of size nn in this case? Write a simplified recurrence that corresponds to this behavior. As above: In any case where you would normally choose an arbitrary constant, please use 1. Furthermore, in the T'(n) recurrence line below, there are two recursive terms. If one argument is larger than the other, please enter it first (in the left cell). For this part, in every blank of the T'(n) recurrence line below, enter only the highest-order term. E.g., if you think the answer in some blank is n/3 — 1, you would enter just /3. In addition, please don't worry about floors and ceilings in your answers. T(0)=T(1)= - @ (). T(n) <T( eor © (o)) )+T( s @ (Com) )+ n @ (), n > 1 Find a closed form solution to this recurrence; T(n) =0O( rigm © (o) )

In CPSC 320 you will learn and analyze an algorithm for selecting the pivot which guarantees that worst case behavior for Quick Sort is O(n logn). Despite this asymptotic result, our simple pivot choice typically runs faster, in practice. This question is complete and cannot be answered again. Correct answer Which of the following sorting algorithms does gsort most closely resemble? (a) Merge Sort Even before we give a robust analysis of Quick Sort, we know a significant lower bound for its running time. Which of the following is the greatest lower bound for Quick Sort's worst case running time (Hint: quick sort is a comparison based sorting algorithm)? (b) Q(nlogn) Given this algorithm, what is partition's missing line of code? (Include the semicolon at the end of the line!) line 5: swap(x[lo],x[p-1]); A=[70 82 8 10 37 92 83] A=[70 82 8 10 37 92 83] A=1[70 8 8 10 37 92 83] Write the recurrence that corresponds to this worst case behavior. In any case where you would normally choose an arbitrary constant, please use 1. Furthermore, in the T'(n) recurrence line below, there are two recursive terms. If one argument is larger than the other, please enter it first (in the left cell). In the final blank of the T'(n) recurrence line below, enter only the highest- order term. E.g., if you think the answer is n? 4+ n1lgn, you would enter just n°. T(0) = T(1) =1 T(n) = T(n— 1) - T(l)—l- nnN > 1. Find a closed form solution to this recurrence; T(0) = T(1) =1 Tn)<T(E)+T(2)+nn>1 T(n) — @(nlog (n)) Submitted answer 4 Submitted at 2023-10-18 13:29:30 (PDT) (0] [ee~ ] Which of the following sorting algorithms does gsort most closely resemble? (a) Merge Sort Even before we give a robust analysis of Quick Sort, we know a significant lower bound for its running time. Which of the following is the greatest lower bound for Quick Sort's worst case running time (Hint: quick sort is a comparison based sorting algorithm)?

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

(b) Q(n logn) Given this algorithm, what is partition's missing line of code? (Include the semicolon at the end of the line!) line 5: swap(x[10],x[p-11); A=1[92 83 8 70 37 10 8| 1004 A=[8 10 37 70 82 83 92|( %) A=1[92 8 83 10 82 37 70| 100%) Write the recurrence that corresponds to this worst case behavior. In any case where you would normally choose an arbitrary constant, please use 1. Furthermore, in the T'(n) recurrence line below, there are two recursive terms. If one argument is larger than the other, please enter it first (in the left cell). In the final blank of the T'(n) recurrence line below, enter only the highest- order term. E.g., if you think the answer is n? 4+ n1gn, you would enter just n?. TO)=T(1) = = T(n)=Tkr-1 Cw)+Th D)+ CBn>1 Find a closed form solution to this recurrence: T(n)=0(r () TO)=T(1)=1 T(n) <T(3 Co)+T(3 Co)+n Cogn>1 T(n) = O(nlog(n) () Submitted answer 3 Submitted at 2023-10-18 13:09:35 (PDT) saved, not graded ] [ e ] [ show v ] Submitted answer 2 Submitted at 2023-10-12 15:40:37 (PDT) saved, not graded ] l [ ] ] [ show v l [ Show/hide older submissions v Homework 2 [ Assessment overview Question Submission status: Available points: — Total points: 8 /8 Auto-graded question [Report an error in this question ]

Previous question Next question Personal Notes No attached notes Notes can't be added or deleted because the assessment is closed.

hw2-2

Related Documents