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 1 year 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)
***C++ Coding*** Write a program for sorting a list of integers in ascending order using the...
***C++ Coding*** Write a program for sorting a list of integers in ascending order using the bubble sort algorithm. Please include comments to understand code. Requirements Implement the following functions: int readData( int **arr) arr is a pointer to pointer for storing the integers. The function returns the number of integers. The function readData reads the list of integers from a file call data.txt into the array arr. The first integer number in the file is the number of intergers....
C++ Write a program for sorting a list of integers in ascending order using the bubble...
C++ Write a program for sorting a list of integers in ascending order using the bubble sort algorithm Requirements Implement the following functions: Implement a function called readData int readData( int **arr) arr is a pointer for storing the integers. The function returns the number of integers. The function readData reads the list of integers from a file call data.txt into the array arr. The first integer number in the file is the number of intergers. After the first number,...
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...
Quicksort - Divider and Conquer Illustrate the operation of PARTITION on the array: A = {9,...
Quicksort - Divider and Conquer Illustrate the operation of PARTITION on the array: A = {9, 19, 13, 5, 12, 8, 7, 4, 21, 6, 11}. Let A[1] = 9 be the pivot value.
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.
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. Radix Sort assignment (CISP430 ignore this part) This is only for those who are using Java How many classes do I need? A: Node, Queue, Radix, Driver...
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT