Question

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?

Answer 1

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.