Question

In The Practice Of Programming, on the chapter regarding quicksort, there is some C code that walks through a basic algorithm for quicksort (I've compiled the code into a program that prints the arbitrary array values pre and post sorting):

#include<stdio.h>
#include<stdlib.h>

void swap(int v[], int i, int j)
{
    int temp;

    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
}

void quicksort (int v[], int n)
{
    int i, last;
    if (n <= 1)
        return;
    swap(v, 0, rand() % n);
    last = 0;
    for (i = 1; i < n; i++) 
    {
        if (v[i] < v[0]) 
        {
            swap (v, ++last, i);
        }
    }
    swap(v, 0, last);
    quicksort(v, last);
    quicksort(v+last+1, n-last-1);
}

void printIntegerArray(int arrayInput[], int arraySize)
{
    for (int i = 0; i < arraySize; i++)
    {
        printf("%d ", arrayInput[i]);
    }
    printf("\n");
}

int main(void)
{
    int array[5] = {7, 10, 14, 12, 4};
    int arraySize = sizeof(array) / sizeof(array[0]);
    printf("Before sorting: ");
    printIntegerArray(array, arraySize);
    quicksort(array, arraySize); 

    printf("After sorting: ");
    printIntegerArray(array, arraySize);
}

I understand everything, except the second recursive call:

quicksort(v+last+1, n-last-1);

What does "v+last+1" do? I wouldn't assume C to change the size of an array at runtime, so is it simply saying that the input is 'an array, starting from V[last+1]' or is it something else? As always, sorry if I've missed this on another post. I've tried searching with a few variant versions of my question.

Était-ce utile?

La solution

is it simply saying that the input is 'an array, starting from V[last+1]' or is it something else?

It's pointer arithmetic, your guess is basically correct, except that it's really a pointer that's passed.

An array is always automatically converted to a pointer to the first element when passing as function argument. So when v is passed, it's really a pointer to its first element that is passed. While v+last+1 is the pointer that points last+1 elements after the first element of v.

Autres conseils

quicksort(v+last+1, n-last-1);

is similar to

quicksort(&v[last+1], n-last-1);
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top