I've been trying to implement quick sort in a particular way and I couldn't find it all over the internet-

1. I'm choosing randomly a pivot (I decided it's going to be the last item on the right side)
2. i index is start index
3. j index is end-2 (to skip pivot)
4. when one item is bigger on the left and other item is smaller on the right, I'm swapping between them
5. after i is meeting j, I can tell for certainty that all the items from 0 to i are smaller than pivot and all the items from j to the end of the array are bigger than pivot
6. now, I want to put pivot in the correct place - it should be between i to j, and return it's index

The problem is that I have mistake in my algorithm and I can't figure it out. Can anyone tell me what am I doing wrong?

Here is my code:

public static void swap(int[] a, int i, int j)
{
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
}

public static int partition(int[] a, int start, int end)
{
        int pivot = a[end];
        int i = start;
        int j = end - 1;

        while (i < j)
        {
            while (i < j && a[i] <= pivot)
                i  ;
            while (i < j && a[j] > pivot)
                j--;
            swap(a, i, j);
        }

        swap(a, i 1, end);
        return i 1 ;
 }

 public static void QuickSort(int[] a, int start, int end)
 {
        if (start >= end)
            return;
        int p = partition(a, start, end);
        QuickSort(a, start, p - 1);
        QuickSort(a, p   1, end);
 }

 static void Main(string[] args)
 {
        int[] a = { 9, 1, 4, 7, 3 };
        QuickSort(a, 0, a.Length-1);
        //PrintArr(a);
 }

CodePudding user response：

you partition method has issue.

you should have it like this.

public static int partition(int[] a, int start, int end)
{
    int pivot = a[end];
    int i = (start - 1);

    for (int j = start; j <= end - 1; j  )
    {
        if (a[j] < pivot)
        {
            i  ;
            swap(a, i, j);
        }
    }
    swap(a, i   1, end);
    return (i   1);
}