Quicksort with pivot at the middle

[open bear]

Can anyone help me out with quick sort using pivot as middle element

public class Quicksort_improved {

    //for improving quicksort we need to select the pivot at middle or randomly
    //because if array is already sorted taking partition at first index will lead to O(n*n) time complexity
    //although the time complexity of quick sort in worst case is always O(n*n) in some cases.

    public static void swap(int arr[], int a, int b){
        int t = arr[a];
        arr[a] = arr[b];
        arr[b] = t;
    }

    public static int pivot(int arr[], int low, int high){
        int mid = (low+high)/2;
        int pivot = arr[mid];
        int i = low, j = high;

        while(i < j){
            while(i<= high && arr[i] <= pivot){
                i++;
            }
            while(arr[j] > pivot){
                j--;
            }
            if(i<j){
                swap(arr,i,j);
            }
        }
        swap(arr, j, mid);
        return j;
    }

    public static void quicksort(int arr[], int low, int high){
        if(low < high){
            int partition_idx = pivot(arr,low,high);
            quicksort(arr, low, partition_idx-1);
            quicksort(arr, partition_idx+1, high);
        }
    }
    public static void main(String[] args) {

        int[] arr = {4,6,2,5,7,9,1,3,8};
        int n=arr.length;

        quicksort(arr,0,n-1);

        for(int i=0; i < n;i++)
        {
            System.out.print(arr[i]+" ");
        }

    }
}```


I been trying this from past 1 hr.
My output: 1 6 2 3 4 5 7 8 9 (almost got it)

[hot geode]

Detected code, here are some useful tools:

Formatted code

package sorting;

public class Quicksort_improved {
  //for improving quicksort we need to select the pivot at middle or randomly
  //because if array is already sorted taking partition at first index will lead to O(n*n) time complexity
  //although the time complexity of quick sort in worst case is always O(n*n) in some cases.
  public static void swap(int arr[] , int a, int b) {
    int t = arr[a] ;
    arr[a]  = arr[b] ;
    arr[b]  = t;
  }
  public static int pivot(int arr[] , int low, int high) {
    int mid = (low + high) / 2;
    int pivot = arr[mid] ;
    int i = low, j = high;
    while (i < j) {
      while (i <= high && arr[i]  <= pivot) {
        i++;
      }
      while (arr[j]  > pivot) {
        j--;
      }
      if (i < j) {
        swap(arr, i, j);
      }
    }
    swap(arr, j, mid);
    return j;
  }
  public static void quicksort(int arr[] , int low, int high) {
    if (low < high) {
      int partition_idx = pivot(arr, low, high);
      quicksort(arr, low, partition_idx - 1);
      quicksort(arr, partition_idx + 1, high);
    }
  }
  public static void main(String[] args) {
    int [] arr = {
      4, 6, 2, 5, 7, 9, 1, 3, 8};
    int n = arr.length;
    quicksort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) {
      System.out.print(arr[i]  + " ");
    }
  }
}

<@&987246883653156906> please have a look, thanks.

Here is an AI assisted attempt to answer your question 🤖. Maybe it helps! In any case, a human is on the way 👍. To continue talking to the AI, you can use </chatgpt:1108714622413963314>.

o choose a good pivot element
//one way to do this is to choose the middle element as the pivot

public static void quicksort(int[] arr, int low, int high) {
    if (low < high) {
        //find the middle element
        int mid = (low + high) / 2;
        //set the middle element as the pivot
        int pivot = arr[mid];
        
        //partition the array around the pivot
        int i = low;
        int j = high;
        
        while (i <= j) {
            while (arr[i] < pivot) {
                i++;
            }
            while (arr[j] > pivot) {
                j--;
            }
            
            if (i <= j) {
                //swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                
                i++;
                j--;
            }
        }
        
        //recursively sort the sub-arrays
        if (low < j) {
            quicksort(arr, low, j);
        }
        
        if (high > i) {
            quicksort(arr, i, high);
        }
    }
}

public static void main(String[] args) {
    int[] arr = {5, 2, 9, 1, 7};
    
    System.out.println("Original array: ");
    for (int num : arr) {
        System.out.print(num + " ");
    }
    
    quicksort(arr, 0, arr.length - 1);
    
    System.out.println("\nSorted array: ");
    for (int num : arr) {
        System.out.print(num + " ");
    }
}

}