Saturday, March 11, 2023

Quick Sort in Java

 Quick Sort in Java

  1. Time complexity : O(n*n) - Worst case , O(nlogn) - Best Case
  2. Space complexity : O(logn) - height of recursion tree

Best case :

n/2^k = 1 2^k = n k= log(n)

 Worst case :

Worst case occur when when the pivot partition the array in an extreme way e.g.
one array is empty and other array contains n-1 elements.
Quick Sort in Java
So, for calculating quick sort time complexity in the worst case,
we put i = n — 1 in the above equation of
T(n) => T(n) = T(n — 1) + T(0) + cn = T(n — 1) + cn .
In this method, we draw the recursion tree and sum the partitioning cost
for each level => cn + c(n−1) + c(n−2) +⋯+ 2c + c ​=
c (n + n−1 + n−2 + ⋯+ 2 + 1) = c(n(n+1)/2) = O(n²).
So worst case time complexity of quick sort is O(n²).

_______________

static void swap(int arr[],int a,int b){ int temp =arr[a]; arr[a]=arr[b]; arr[b] = temp; } static void quickSort(int arr[], int low, int high) { // code here if(high>low){ int piv = partition(arr,low,high); quickSort(arr,low,piv-1); quickSort(arr,piv+1,high); } } static int partition(int arr[], int low, int high) { // your code here int piv = low; int i = low; int j = high; while(i<j){ while(arr[i]<=arr[piv] && i<=high-1){i++;} while(arr[j]>arr[piv] && low+1<=j){j--;} if(i<j){ swap(arr,i,j); } } swap(arr,piv,j); return j; }

Quick Sort in Java


No comments:

Post a Comment

Quick Sort in Java

 Quick Sort in Java Time complexity : O(n*n) - Worst case , O(nlogn) - Best Case Space complexity : O(logn) - height of recursion tree Best ...