Quick sort parameters

Question

I'm trying to apply a quicksort snippet to my program; however, none of the vast amount of tutorials or examples that I've found explain in layman's terms what I use for the second and third parameters, most commonly referred to as left and right; the explainations are not in simple enough terms for me to understand.

Beneath is the snippet verbatim; if there are any issues I apologize.

void quickSort(int arr[], int left, int right) 
{
    int i = left, j = right;
    int tmp;
    int pivot = arr[(left + right) / 2];
      /* partition */
    while (i <= j) 
    {
        while (arr[i] < pivot)
            i++;
        while (arr[j] > pivot)
            j--;
        if (i <= j)
        {
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    };

      /* recursion */
    if (left < j)
    quickSort(arr, left, j);

    if (i < right)
    quickSort(arr, i, right);
}

I understand that the first parameter is the array to be sorted, but what exactly in reference to that array am I passing in for "left" and "right?"

I've been coding for a few years now but I haven't had the best guidance, so if this is remedial to you please educate me as I'm still very much in the learning phase.

Answer 1

Before I answer there is one point,

while (i <= j) 
{
    while (arr[i] < pivot)
        i++;
        while (arr[j] > pivot)
            j--;
            if (i <= j) 
            {
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;
            }
};

This part of your code has a while loop that is indented incorrectly, so it is a bit confusing.

So the left and the right are referring the left and right most index of your desired array.

Let's say that we have an array [1, 4, 5, 6, 3] the sorting part of quick sort will arrange the array into [1, 4, 3, 6, 5]

What happens after is a you will have the recursive call to quickSort(arr, 0, 2) quickSort(arr, 3, 4) So one quickSort will sort them based on the left (index 0) to right (index 2) and another will quickSort base on the left (index 3) to the right (index 4) until the array has reach the length < 1

Answer 2

The left and right are indexes into the array to be sorted for the current invocation of the quicksort call.

When you first call quicksort at the top level, left and right are the complete array. For example:

int arr[] = { 3,4,6,2,5,6,6,7,4,4,6,5,3,6,7,8,8,6,4,3 };

quicksort(arr, 0, 19);