How to make sense of or interpret the first call to partition in Quicksort?

Question

This covers "a software algorithm" from https://stackoverflow.com/help/on-topic or in this case, the quicksort algorithm to sort a set of numbers.

Here is the quicksort algorithm code I am using (From cracking the coding interview 5th edition)

static void quickSort(int[] arr, int left, int right) {
    int index = partition(arr, left, right);
    if(left < index - 1) {
        //sort left half
        quickSort(arr, left, index - 1);
    }
    if(index < right) {
        //sort right half 
        quickSort(arr, index, right);
    }
}
static int partition(int[] arr, int left, int right) {
    int pivot = arr[ (left + right) / 2];
    while(left <= right) {
        while(arr[left] < pivot) {
            left ++;
        }
        while(arr[right] > pivot) {
            right --;
        }
        if(left <= right) {
            swap(arr, left, right);
            left ++;
            right --;
        }
    }
    return left;
}
static void swap(int arr[], int one, int two) {
    int temp = arr[one];
    arr[one] = arr[two];
    arr[two] = temp;
}

I know a summary of quicksort algorithm is to have all the elements less than the pivot be on the left of the pivot and all the elements greater than the pivot are on the right of the pivot. By the way, is there a rule for where elements that are the same as pivot are supposed to go?

So my test run is this unsorted array from https://www.hackerrank.com/challenges/angry-children

{10, 100, 300, 200, 1000, 20, 30}

After the first call to partition, this is the state of my array

[10, 100, 30, 20, 1000, 200, 300]

The pivot I chose based on this algorithm was the value 200. However after this first call, I don't know how to make sense of this because everything to the left of 200 is not less than 200(the 1000). I know this algorithm works because I got the end result sorted array.

Can someone help me interpret the results of the first call to partition?

All the elements less than 200 are before all the elements not less than 200. — user253751
but i thought it was "partitions a with elements < pivot on left and elements > pivot on right" from courses.cs.washington.edu/courses/cse373/13wi/lectures/02-27/… slide 16 — committedandroider
@lared but it should still follow the rule right? everything less than pivot on left, everything greater than pivot on right — committedandroider
quickSort(arr, right, index + 1);??? There are misplaced arguments for left and right. It shouldn't make partitioning for right subarray at all o_O — Lurr

committedandroider committedandroider · Accepted Answer · 2015-03-22T20:13:04

I think the confusion I had was the whole idea of quicksort. If anyone else is struggling, with this, here's how I would explain it now.

int index = partition(arr, left, right);

&nbsp&nbsp&nbspWill partition the array with regards to a pivot, which would be index in this case. It is guaranteed that everything to left is less than pivot while everything to the right of the pivot is greater than the pivot.

Now if we look at this code

if(left < index - 1) {
    quickSort(arr, left, index - 1);
}

is basically asking is there anything to the left of the pivot? If there is, sort everything to the left of pivot. Notice that this test will not pass if left = index - 1 or there is only one element to the left of the pivot. There is no need to sort.

Its the same exact logic with this code segment as well(apply to the right of pivot)

 if(index < right) {
        //sort right half 
        quickSort(arr, index, right);
    }

How to make sense of or interpret the first call to partition in Quicksort?

2 Answers