How to generate the worst case for quick sort algorithm?

Question

How could i generate and print the worst case set for Quick Sort considering as pivot the middle element?. This is my implementation of quicksort algorithm:

  void quickSort(int arr[], int left, int right) {

     int index = partition(arr, left, right);

        if (left < index - 1)

           quickSort(arr, left, index - 1);

        if (index < right)

           quickSort(arr, index, right);
 }


 int partition(int arr[], int left, int right){

  int i = left, j = right;
  int tmp;
  int pivot = arr[(left + right) / 2];

   while (i <= j) {
        while (arr[i] < pivot)
               i++; 
       while (arr[j] > pivot)

              j--;

        if (i <= j) {

              tmp = arr[i];

              arr[i] = arr[j];

              arr[j] = tmp;

              i++;

              j--;

        }

  };
  return i;

 }

Any idea of how to generate the worst case for this algorithm?.

score 5 · Answer 1 · answered Oct 16 '13 at 04:42

5

Set the pivot element equal to the lowest or highest number, should get the worst case. And the complexity at this case is O(n^2).

answered Oct 16 '13 at 04:42

Rakesh KR

6,357
5
40
55

jester · Answer 2 · 2013-10-16T05:51:35.347

The worst case of the quick sort algorithm occurs when the array is already sorted. The pivot is supposed to split the array as equally as possible, where elements to the left of the pivot are lesser than the pivot and elements to its right are greater, i.e the pivot gets fixed in its final position in the sorted array and no further swaps occur across the pivot. This allows us to treat the array to the left of the pivot and the array to the right independently and apply the same algorithm recursively on it.

The worst case occurs when our pivot element splits the array as unequally as possible, i.e instead of an ideal n/2 elements in the smaller half, we get zero - meaning the pivot is the biggest or smallest in the array.

Hence the worst case occurs when the input array is already sorted - if the pivot is chosen to be the first or last element.

when the pivot choosing algorithm is to pick the middle element, basically worst case occurs when the pivot is chosen such that it leaves one partition empty, i.e every time the pivot chosen is the smallest/largest.

This answer and the one by YS Bhai both assume that the pivot chosen is the first or last element. Since his pivot choosing algorithm is to pick the middle element, he actually wants something more like `[sorted second half | sorted first half]`. — rliu, Oct 16 '13 at 05:12
@roliu : Thanks for pointing that out and sorry for missing that point. Editing my answer — jester, Oct 16 '13 at 05:48

score 1 · Answer 3 · answered Oct 16 '13 at 04:44

1

The worst case for quickshort is every time you divide the arrary it should be one sided. so the input array can be a sorted array.

answered Oct 16 '13 at 04:44

dead programmer

4,223
9
46
77

score 0 · Answer 4 · answered Oct 16 '13 at 06:46

The worst case for quicksort is when you choose your pivot to be either the lowest or highest element in your array and then attempt to partition around it. If you keep choosing the lowest or highest element in the array as the partition each time, you will make close to n² comparisons/swaps. To avoid this worst case behavior, you can use the median of medians algorithm which is linear time (O(n)) to choose an appropriate pivot for you and it will make your worst case O(n log n).

How to generate the worst case for quick sort algorithm?

4 Answers4