Implementing QuickSort With middle element as Pivot

Question

I tried and wrote a code for Quicksort with middle element as pivot.

I was successful in writing one.

But Pivot has the property that:

Elements on its left are lesser than pivot and greater on its right.

I was not able to achieve this in my following code.

private static void QuickSortAlgorithm(int[] a, int i, int n) 
{
    if(i<n)
    {
        int part = partition(a,i,n);

        QuickSortAlgorithm(a, i, part-1);

        QuickSortAlgorithm(a, part, n);
    }
}

private static int partition(int[] a, int i, int n) 
{
    int pivot = (i+n)/2;

    int left = i;

    int right = n;
    while(left<=right)
    {
        while(a[left]<a[pivot]){
            left++;
        }

        while(a[right]>a[pivot])
        {
            right--;
        }

        if(left<=right)
        {
            swap(a,left,right);
            left++;
            right--;
        }
    }
    return left;

}

Main Method:

    int a[]={5,7,3,9,1};
    int n = a.length;
    QuickSortAlgorithm(a,0,n-1);
    System.out.println(Arrays.toString(a));

My doubt is:

I am sending left as my partitioned index.

But, when I am recursively calling QuickSortAlgorithm()

I am sending i to part-1 and part to n;

What should I send as partition index so that

I could call something like this: So that pivot property is satisfied?

    QuickSortAlgorithm(a, i, part-1);

    QuickSortAlgorithm(a, part+1, n);

Thank you:)

Aditya Yadav Aditya Yadav · Accepted Answer · 2020-03-09T17:33:57

you have to send pivot value in first stack call inclusive and pivot+1 as lower index for second stack call. You also have to put value of left as i+1 then your code will give an correct output

Implementing QuickSort With middle element as Pivot

2 Answers