Question

In: Computer Science

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 >= 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?

Solutions

Expert Solution

i)

Code of Quicksort that sorts the array of integers in descending order is as follows:

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)

}

ii)

In the worst case the list will be traversed completely and the comparisons will be done throughout leading to n2 time for n elements.

Therefore, the worst-case time complexity of quicksort algorithm is O(n2).

venereology answered 8 months ago
Next > < Previous

Related Solutions

The purpose here is to implement the QuickSort sorting algorithm to sort integers. Write a C...
The purpose here is to implement the QuickSort sorting algorithm to sort integers. Write a C program which accepts 1 command-line argument: the name of a text file which contains integers, one-per line. Your C program must be named project3. Your C program needs to implement the QuickSort algorithm to sort the integers read from the file specified on the command-line. Your QuickSort implementation must utilize the median-of-three algorithm for choosing a pivot, and BubbleSort any sub arrays with less...
What is the running time of Quicksort when the input array is sorted in ascending order?...
What is the running time of Quicksort when the input array is sorted in ascending order? (please explain in detail)
1a)Use the Lomuto's quicksort algorithm to sort the following list of integers in nondecreasing order for...
1a)Use the Lomuto's quicksort algorithm to sort the following list of integers in nondecreasing order for the first pivot item. Use pointers i and j for swapping items (if necessary) for each step leading to your answer. Note do the problem just for the first pivot item. 123,34,189,56,150,12,9,24 1b)Use the same list of numbers and use the Hoare's quicksort algorithm using pointers l and r and updating the pointers i and j and swapping items. Do the problem just for...
Is quicksort a stable sorting algorithm? If yes, prove it, if not, give an example
Is quicksort a stable sorting algorithm? If yes, prove it, if not, give an example
Modify the quicksort algorithm such that it uses the last item as the pivot instead of the 1st. Also, sort in descending order, instead of ascending order.
Programming Language : JavaModify the quicksort algorithm such that it uses the last item as the pivot instead of the 1st. Also, sort in descending order, instead of ascending order.NOTE: Do not move the last element into the first element of the array. You must treat the algorithm as if the pivot is actually sitting in the last location of the array.After it has been sorted in descending order, go through all the items in the array and make sure...
Radix sortCome up with an unsorted array of numbers (integer array). Sort the numbers in ascending...
Radix sortCome up with an unsorted array of numbers (integer array). Sort the numbers in ascending order and descending order and display them using radix sort. First sort in ascending, then reset the array to its original order and finally sort the array again in descending order. I need this in java language.
Java : Modify the selection sort algorithm to sort an array of integers in descending order....
Java : Modify the selection sort algorithm to sort an array of integers in descending order. describe how the skills you have gained could be applied in the field. Please don't use an already answered solution from chegg. I've unfortunately had that happen at many occasion ....... ........ sec01/SelectionSortDemo.java import java.util.Arrays; /** This program demonstrates the selection sort algorithm by sorting an array that is filled with random numbers. */ public class SelectionSortDemo { public static void main(String[] args) {...
C Language NO ARRAY UTILIZATION OR SORTING Create a .txt file with 20 integers in the...
C Language NO ARRAY UTILIZATION OR SORTING Create a .txt file with 20 integers in the range of 0 to 100. There may be repeats. The numbers must not be ordered/sorted. The task is to find and print the two smallest numbers. You must accomplish this task without sorting the file and without using arrays for any purpose. It is possible that the smallest numbers are repeated – you should print the number of occurrences of the two smallest numbers....
Excel sorting In excel how do you sort a column of months in ascending order and...
Excel sorting In excel how do you sort a column of months in ascending order and not alphabetical when the month is in word format?
1. Read 20 integers into an array. Next, use the unique algorithm to reduce the array...
1. Read 20 integers into an array. Next, use the unique algorithm to reduce the array to the unique values entered by the user. Use the copy algorithm to display the unique values. 2. Modify the Exercise 1 above to use the unique_copy algorith. The unique values should be inserted into a vector that's initially empty. Use a back_inserter to enable the vector to grow as new items are added. Use the copy algorithm to display the unique values.
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT