3
\$\begingroup\$

This is my implementation of the divide-and-conquer Quicksort algorithm using the Lomuto partition scheme in C. This is part of a personal project and I'm following Linus Torvalds's coding style.

void swap(int *i, int *j)
{
    int tmp = *i;
    *i = *j;
    *j = tmp;
}

int partition(int *arr, int l, int r)
{
    int pivot = arr[r];
    int i = l;
    for (int j = l; j < r; ++j) {
        if (arr[j] < pivot) {
            swap(&arr[i], &arr[j]);
            ++i;
        }
    }
    swap(&arr[i], &arr[r]);
    return i;
}

void quicksort(int *arr, int l, int r)
{
    if (l >= r)
        return;

    int i = partition(arr, l, r);

    quicksort(arr, l, i - 1);
    quicksort(arr, i + 1, r);
}

The function void quicksort(int *arr, int l, int r) can be called like this:

int arr[] = {4, 1, 0, 2, 5, 3, 8, 9, 7, 6};
size_t arrlen = sizeof(arr) / sizeof(int);
quicksort(arr, 0, arrlen - 1);
\$\endgroup\$
4
  • \$\begingroup\$ HI @andySukowsiBang - partition function doesn't seem to be correct ... It always does a swap on the first element with itself ... should it perhaps be for (j = l+1; \$\endgroup\$ – Mr R Apr 3 at 10:42
  • \$\begingroup\$ @MrR You are partially right. The first element is swapped with itself, but the reason why the for-loop needs to start with j = l is that ++i has to be reached if the first element is smaller than pivot. \$\endgroup\$ – Andy Sukowski-Bang Apr 3 at 12:32
  • \$\begingroup\$ @MrR Is there something else that could be optimized? \$\endgroup\$ – Andy Sukowski-Bang Apr 8 at 18:44
  • \$\begingroup\$ @AndySukowskiBang Anything unnecessary is always a problem. What happens for bad inputs - e.g. negative numbers, null value for arr, &arr[offset] might be slower than using pointers directly [depends on your platform & compiler]. Is it really the intention for partition to always do at least one swap (whenever l < r). \$\endgroup\$ – Mr R Apr 8 at 20:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.