Partition(numbers, lowIndex, highIndex) { midpoint = lowIndex + (highIndex - lowIndex) / 2 pivot = numbers[midpoint]...

Partition(numbers, lowIndex, highIndex) { midpoint = lowIndex + (highIndex - lowIndex) / 2 pivot = numbers[midpoint] done = false while (!done) { while (numbers[lowIndex] < pivot) lowIndex++ while (pivot < numbers[highIndex]) highIndex-- if (lowIndex >= highIndex) { done = true } else { temp = numbers[lowIndex] numbers[lowIndex] = numbers[highIndex] numbers[highIndex] = temp lowIndex++ highIndex-- } } return highIndex } Quicksort(numbers, lowIndex, highIndex) { if (lowIndex >= highIndex) return lowEndIndex = Partition(numbers, lowIndex, highIndex) Quicksort(numbers, lowIndex, lowEndIndex) Quicksort(numbers, lowEndIndex + 1, highIndex) } (i) Re-write the code of Quicksort so that it sorts the array of integers in descending order. Writing the specific lines of code which should be changed is sufficient. (ii) What is the worst-case runtime of this Quicksort algorithm?

Expert Solution

To sort the given array in descending order we need to mdify only 2 lines so that the new code partitions such that all numbers greater that pivot lie before(left side) it and all smaller than it lie after(right side) it.

The modified code is :

Partition(numbers, lowIndex, highIndex) {
  midpoint = lowIndex + (highIndex - lowIndex) / 2 pivot = numbers[midpoint] done = false
  while (!done) {
    //   < changed to >
    while (numbers[lowIndex] > pivot) lowIndex++
    //  < is changed to >
    while (pivot > numbers[highIndex]) highIndex--
    if (lowIndex >= highIndex) {
      done = true
    } else {
      temp = numbers[lowIndex] numbers[lowIndex] = numbers[highIndex] numbers[highIndex] = temp lowIndex++highIndex--
    }
  }
  return highIndex
}
Quicksort(numbers, lowIndex, highIndex) {
  if (lowIndex >= highIndex) return lowEndIndex = Partition(numbers, lowIndex, highIndex) Quicksort(numbers, lowIndex, lowEndIndex) Quicksort(numbers, lowEndIndex + 1, highIndex)
}

2.

Here the worst case will be N². In this case all the pivots will be maximum/minimum value.

venereology answered 1 year ago

Use quickselect algorithm to partition an array into 3 subsets: values less than pivot, values equal...

Use quickselect algorithm to partition an array into 3 subsets: values less than pivot, values equal to pivot, and values greater than pivot. The pivot must be a random element of the array. Find S1(the number of elements less than the pivot), S2 (the number of elements equal to the pivot), and S3 (the number of elements greater than the pivot). Your code must use only one array and must be able to handle duplicate array elements. Use Java.

Given an array of numbers, find the index of the smallest array element (the pivot), for...

Given an array of numbers, find the index of the smallest array element (the pivot), for which the sums of all elements to the left and to the right are equal. The array may not be reordered. Example arr=[1,2,3,4,6] the sum of the first three elements, 1+2+3=6. The value of the last element is 6. Using zero based indexing, arr[3]=4 is the pivot between the two subarrays. The index of the pivot is 3. Function Description Complete the function balancedSum...

How to proof that the 2-partition problem can be transformed to 3-partition problem and the time...

How to proof that the 2-partition problem can be transformed to 3-partition problem and the time complexity of the transformation (i.e. the 2-partition problem can be solved by using an algorithm that solves the 3-partition problem)

Following is the algorithm of Quicksort for sorting an array of integers in ascending order. Partition(numbers,...

Following is the algorithm of Quicksort for sorting an array of integers in ascending order. Partition(numbers, lowIndex, highIndex) { midpoint = lowIndex + (highIndex - lowIndex) / 2 pivot = numbers[midpoint] done = false while (!done) { while (numbers[lowIndex] < pivot) lowIndex++ while (pivot < numbers[highIndex]) highIndex-- if (lowIndex >= highIndex) { done = true } else { temp = numbers[lowIndex] numbers[lowIndex] = numbers[highIndex] numbers[highIndex] = temp lowIndex++ highIndex-- } } return highIndex } Quicksort(numbers, lowIndex, highIndex) { if (lowIndex...

Quick Sort as explained in class uses a Pivot value to arrangeall numbers greater than...

Quick Sort as explained in class uses a Pivot value to arrange all numbers greater than the pivot on oneside and all values smaller than the pivot on the other side. Pivot in the class example used the firstelement of the array. “Median of three” rule uses the median of the first last and the middle elementsof the array as the Pivot so that we avoid the chance of picking the smallest or the largest element in thearray.a) Write the...

(2) PQRS is a quadrilateral and M is the midpoint of PS. PQ = a, QR...

(2) PQRS is a quadrilateral and M is the midpoint of PS. PQ = a, QR = b and SQ = a – 2b. (a) Show that PS = 2b. Answer(a) [1] (b) Write down the mathematical name for the quadrilateral PQRM, giving reasons for your answer. Answer(b) .............................................................. because ............................................................... ............................................................................................................................................................. [2] __________ A tram leaves a station and accelerates for 2 minutes until it reaches a speed of 12 metres per second. It continues at this speed for...

Does there exist a partition of R that is an uncountably infinite partition that consists of...

Does there exist a partition of R that is an uncountably infinite partition that consists of uncountably infinite sets? If so, construct such a partition, otherwise prove that such a partition can not exist.

. True or false? (1) There is at most one pivot in any row. (2) There...

. True or false? (1) There is at most one pivot in any row. (2) There is at most one pivot in any column. (3) There is at least one pivot in any row. (4) There is at least one pivot in any column. (5) There cannot be more free variables than pivot variables. (6) There is a linear system that has exactly two solutions. (7) The weights c1, ..., cp ? R in a linear combination c1v1 + ......

After running the experiment with the pivot, comment out the line, update the pivot selection to...

After running the experiment with the pivot, comment out the line, update the pivot selection to use the median of the first, middle, and last items, and run the experiment. What line needs to be commented out and how would I update the pivot selection to use the median? Example.java package sorting; import java.io.IOException; import java.util.Random; import sorters.QuickSort; public class Example { public static void main(String args[]) throws IOException { int n = 100; // adjust this...

Why is the partition function important, and what does the partition function measure?

Question