CODEWITHSUNDEEP
algorithmsortingbig-oquicksort
cris
cris

Reputation: 275

Is the worst case scenario for the time complexity of this quicksort implementation O(n log n)?

I want to say its worst time complexity is still n log n. Just because I'm using the middle element as a pivot and so even if the array is already sorted, it will still half the array when it returns from the partitioning method. I could be wrong though, my DS isn't the best

 public static void quicksort(int [] arr, int low, int high){
      if(low < high){
          int pivot = partition(arr, low, high);
          quicksort(arr, low, pivot);
          quicksort(arr, pivot+1, high);
        }
    }

 public static int partition(int [] arr, int low, int high){
     
        int i = low; 
        int j = high;
        int mid = low + (high-low)/2;
        int pivot = arr[mid];
       
        while(true){
           while(arr[i] < pivot){
               i++;
           }
           while(arr[j] > pivot){
               j--;
           } 
            

        if( i >= j) return j;
            
        swap(arr, i, j);
        i++;
        j--;  
         
    }
 }

Upvotes: 0

Views: 453

Answers (2)

templatetypedef
templatetypedef

Reputation: 372784

The paper “A Killer Adversary for Quicksort” gives an algorithm that, for any quicksort implementation that satisfies certain “reasonable” requirements and runs deterministically, produces arbitrarily long input sequences that cause the algorithm to run in quadratic time. So while you’re correct that using the middle value as the pivot will prevent your algorithm from running in quadratic time on an already-sorted array, the fact that the pivots are picked deterministically means that there will be some input to the algorithm that causes the performance to degrade, and the linked paper can be used to construct such a pathological input.

Upvotes: 2

Ethan
Ethan

Reputation: 26

the worst case of quick sort is when each time the pivot is chosen it's the max or min number/value in the array. in this case it will run at O(n^2) for the regular version of Quick sort. However, there's a version of Quick sort that uses the partition algorithm in order to choose better pivots. In this version of Quick sort the worst case is O(nlogn).

Upvotes: 0

Related Questions