CODEWITHSUNDEEP
calgorithmquicksort
Trt Trt
Trt Trt

Reputation: 5532

Quicksort Partition

I am trying to understand and implement quicksort: So I have been reading this:

http://www.geeksforgeeks.org/iterative-quick-sort/

I do not understand the partition code.

/* A typical recursive implementation of quick sort */

/* This function takes last element as pivot, places the pivot element at its
   correct position in sorted array, and places all smaller (smaller than pivot)
   to left of pivot and all greater elements to right of pivot */
int partition (int arr[], int l, int h)
{
    int x = arr[h];
    int i = (l - 1);

    for (int j = l; j <= h- 1; j++)
    {
        if (arr[j] <= x)
        {
            i++;
            swap (&arr[i], &arr[j]);
        }
    }
    swap (&arr[i + 1], &arr[h]);
    return (i + 1);
}

/* A[] --> Array to be sorted, l  --> Starting index, h  --> Ending index */
void quickSort(int A[], int l, int h)
{
    if (l < h)
    {        
        int p = partition(A, l, h); /* Partitioning index */
        quickSort(A, l, p - 1);  
        quickSort(A, p + 1, h);
    }
}

so lets say I have this array, [3,8,7] so it takes the last element as a pivot. that is 7.

The first step of the partition function will be (for l=0 and h=2):

x = 7
i = -1

then at the loop, arr[j] <= x will be true. Because 3 <= 7. So it will increase i by 1, and then swap 3 with 3? it doesn't make sense. That will just return the same array

Upvotes: 2

Views: 2248

Answers (1)

IVlad
IVlad

Reputation: 43477

Let's see what happens:

x = 7
j = 0:

  3 <= 7: swap(arr[0], arr[0]) => nothing happens

j = 1:

  8 <= 7 is false => nothing happens

Now, notice that i == 0, and we have the line:

swap (&arr[i + 1], &arr[h]);

Which means that we swap arr[1] with arr[2], and your array will be 3 7 8. You did not take this line into consideration in your analysis.

This is correct, and the returned position of the pivot, i + 1 == 1, is also correct.

You can add print statements after each line of interest or step through with a debugger to better understand what is going on. Doing this on paper can lead to such mistakes, where you accidentally skip steps, especially when learning something (to be honest, it took me a few minutes to realize that you missed that line).

Upvotes: 4

Related Questions