(a)
To show that the values of array and auxiliary values after each iterations of while loop using HOARE-PARTITION.
(a)
Explanation of Solution
Given Information: The array is
Explanation: According to the HOARE-PARTITION,
Consider that
Now the array and auxiliary after each pass through HOARE-PARTITION algorithm will show in below table-
After the iteration
Hence, the HOARE-PARTITION algorithm exit the while loop with the auxiliary values of
(b)
To showthat the indices i and j are such that we never access an element of array A outside the sub-array.
(b)
Explanation of Solution
In the beginning of while loop when
Consider that it has an element k and
If it takes parameter
Hence, it is can be concluded that the indices i and j are such that one never access an element of array A outside the sub-array.
(c)
To explain that when HOARE-PARTITION terminates, it returns a value j such that
(c)
Explanation of Solution
The value of jis decreased after every iteration and at the final iteration of the loop i will equals to 1but greater than r .
Line 11 of HOARE-PARTITION illustrate that
Therefore, the HOARE-PARTITION algorithm terminates and returns
(d)
To explain that the every element of array is less than or equal to every element of
(d)
Explanation of Solution
Consider that it just finished the iteration of the loop in which j went to j1 and j2 and I went to i1 to i2 . The elements of the array
Similarly, the elements of the array
Now putting all the conditions of the array defined in the algorithm it has condition that is
Since at the termination of the algorithm
Therefore, the every element of array
(e)
To rewrite the QUICK-SORT procedure by using HOARE-PARTITION algorithm.
(e)
Explanation of Solution
QUICKSORT(A,p,r). If then q =HOARE-PARTITION(A,p,r). QUICKSORT(A,p,q-1). QUICKSORT(A,q+1,r). End if. HOARE-PARTITION(A,p,r) while TRUE repeat until . repeat . until . if then exchange with . else return j. end if. end while.
The quick sort algorithm is based on recursion. It first sets the parameters and then check the initial condition.
If the initial condition is true then it call the HOARE-PARTITION algorithm with recursion of calling itself again and again until the initial condition becomes false.
Want to see more full solutions like this?
Chapter 7 Solutions
Introduction to Algorithms
- See the pseudo-code of the Binary Search using recursion below. Fill in the XXXX and YYYY in the code Algorithm BinarySearch (A,v,low,hi) Input: array A indexed from low to hi with items sorted from smallest to largest. We are searching for the item v Output: returns a location index of item v in array A; if v is not found, -1 is returned. if (low > hi) then return (-1); mid = (lo + hi)/2; if (A[mid] = v) then == return(mid); if (A[mid] < v) then return(BinarySearch(A, XXXX ,hi, v)); else return(BinarySearch(a, lo, YYYY, v)); О а. ХX: lo+1, YҮҮ: hi O b. XXXX: mid, YYYY: mid О с. ХXXX: lo, YYYY: hi O d. XXXX: lo+1, YYYY: hi-1 O e. XXXX: mid+1. YYYY: mid-1arrow_forwardplease code in java or c++ implement and test the GET-MEMORY algorithm This algorithm uses the Next-Fit(First-Fit-With-A-Roving-Pointer) technique. then implement and test the FREE-MEMORY algorithm. Implement the “GET_MEMORY” and “FREE_MEMORY” algorithms. Comprehensive testing must be done for each algorithm. Following are sample run results for each: GET_MEMORY IS RUNNING……… Initial FSB list FSB# Location Size 1 7 4 2 14 10 3 30 20 . . . . . . Rover is 14 ---------------------------------------------------------------------------- Allocation request for 5 words Allocation was successful Allocation was in location 14 FSB# Location Size…arrow_forward12 - Consider the example of sorting, we implemented Bubble sort but the data started to grow and Bubble sort started getting very slow. In order to tackle this we implemented Quick sort. But now although the Quick sort algorithm was doing better for large datasets, it was very slow for smaller datasets. In order to handle this situation, implement a --------- small datasets, bubble sort will be used and for larger, quick sort will be used. design pattern where for According to the system definition given above, which design pattern did designers use when implementing the system. I) Template Method II) Singleton III) Strategy IV) None of the mentioned a) O II b) O IV c) O II d) O Iarrow_forward
- Exercise # 2: Map search For the location map search example explained in the Greedy best first search and A* algorithm, change the search algorithm to follow the uniform cost algorithm (UCS). Run the new code and compare the results of UCS versus Greedy & A*, in terms of the levels required and the number of nodes expanded. IT HAS TO BE IN PYTHON LANGUAGEarrow_forwardPython help----- Using HASH sorting algothrim create only one function def sortstring(filename): that takes in a file which has a bunch of sentences, each line of sentence consting of different length. Sort the setences from the lower length senteces to the highest length sentence. Print it after ( DON'T USE ANY SORTING BULT-IN FUNCTION ). Note: Keep note of time complexity as it should be able to run few 10,000 lines of sentences in few seconds.arrow_forwardApply the merge sort on the following list and sort the list in decreasing order: 91 98 29 93 98 53 68 33 33 47 You must show how the list is divided by the recursive calls to MERGE-SORT, then merged at each stage to obtain the final sorted list.arrow_forward
- Q: Modify the following algorithm of Merge Sort in such a way that during every recursive call it should divide the array into three partitions instead of two. What will be effect of this modification on the running time of Merge Time? Merge-Sort (A, left, right) if left ≥ right return else middle ← (left+right)/2 Merge-Sort(A, left, middle) Merge-Sort(A, middle+1, right) Merge(A, left, middle, right) Merge(A, left, middle, right) n1 ← middle – left + 1 n2 ← right – middle create array L[n1], R[n2] for i ← 0 to n1-1 do L[i] ← A[left +i] for j ← 0 to n2-1 do R[j] ← A[middle+j] k ← i ← j ← 0 while i< n1 & j< n2 if L[i] < R[j] A[k++] ← L[i++] else A[k++] ← R[j++] while i< n1 A[k++] ← L[i++] while j < n2 A[k++] ← R[j++]arrow_forwardThe following list of numbers is the return value of a partitioning algorithm (Lomuto's or Hoare's, e.g.). Circle all possible valid pivots (the values the arrays were partitioned with). 2 1 3 5 4 10 8 14arrow_forwardThe best case behaviour occurs for quick sort when the partition function splits the sequence of size n into subarrays of size: Select one: a.n/4 : 3n/4 b.n/4 : 3n/2 c.3n/8 : (5n/8) d.n/2 : (n/2)-1 e.n/2 : n/3arrow_forward
- Quick Sort is another sorting algorithm that follows a divide-and-conquer approach. The algorithm can be summarized in 3 steps: A pivot element is chosen, usually the first element. All elements smaller than the pivot are placed to the left of the pivot. This creates 2 partitions, elements greater than the pivot and elements less than the pivot. The 2 partitions are sorted using Quick Sort. Sample code in python3: def quick_sort(arr): def quick_sort_r(arr, start, end): if end - start < 2: # single element base case return # choose a pivot pivot = start # you may choose other elements store = pivot+1 # index to store less than elements # for all elements after the pivot for i in range(pivot+1, end): if arr[i] < arr[pivot]: # if element is less than pivot arr[i], arr[store] = arr[store], arr[i] # swap store += 1 # increment store index # swap pivot with last element in less than…arrow_forwardQ: Suppose you are given an array A of n elements. Your task is to sort n numbers stored in array A by reading the first element of A and placing it on its original position (position after sorting). Then read the second element of A, and place it on its original position. Continue in this manner for the first n-1 elements of A. What type of sorting is this? Write the algorithm and also mention the name of this sorting algorithm. What loop invariant does this algorithm maintain? Give the best-case and worst-case running times of this sorting algorithm.arrow_forwardYour task is sorting the given list by dictionary order, sortingoperation must be realized using the bubble sort algorithm. Additionally,this list implementation should be written using a two-dimensional char ar-ray.Bubble Sort Algorithm1 function swap ( a , b)2 // F i l l own your own !3 end function45 function compare ( a , b)6 // Compare f unc t i on should be implemented7 // to r e a l i z e the s o r t i n g c r i t e r i a .8 // For example , e l ement s in a are s t r i n g s and9 // the y are to be s o r t e d in d i c t i o n a r y order .10 // strcmp f unc t i on can be used in p l a c e11 // of compare f unc t i on .12 end function1314 function bubbl e s o r t ( a , n)15 while n != 016 high = 017 for i=0 to n=2 incremented by 118 i f compare ( a [ i ] , a [ i +1]) > 0 then19 swap ( a [ i ] , a [ i +1])20 high = i+121 end i f22 end for23 n = high24 end while25 end function1arrow_forward
- Database System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill EducationStarting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSONDigital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
- C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSONDatabase Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage LearningProgrammable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education