# Quicksort using Lomuto partition scheme in C

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);

• 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; – Mr R Apr 3 at 10:42
• @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. – Andy Sukowski-Bang Apr 3 at 12:32
• @MrR Is there something else that could be optimized? – Andy Sukowski-Bang Apr 8 at 18:44
• @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). – Mr R Apr 8 at 20:44