Quicksort with last element as pivot not sorting

Question

I have an assignment to create a quicksort algorithm which chooses the last element as the pivot element. Further inside the partition() function when an Element n is found which is greater or equal to the pivot the function should perform a "ring swap". It should swap n with pivot-1 and after that pivot-1 with pivot.

So i wrote this program:

int partition(uint8_t *arr, int left, int right){
int pivot_position = right;
if (right-left >1)
{
    for (int i = right; i >= left; i--)
    {
        for (int j = left; j < i; j++)
        {
            if (arr[j] >= arr[i])
            {
                pivot_position = i;
                int tmp = arr[j];
                arr[j] = arr[i-1];
                arr[i-1] = arr[i];
                arr[i] = tmp;
                break;
            }
        }
    }
}else{
    if (right-left == 1 && arr[left] > arr[right])
    {
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
    }
    return 0;
}

return pivot_position;

}

void quicksort( uint8_t *arr, int left, int right){
int pivot = partition(arr, left, right);

if (pivot != 0)
{
    quicksort( arr, left, pivot-1);
    quicksort( arr, pivot+1, right);
}

}

If given the Array: [160, 32, 96, 128, 224, 64, 192, 0, 255] The expected Output: [0, 32 , 64 ,96, 128, 160, 192, 224, 256]

What have I done wrong?

EDIT: As requested:

void main() {
uint8_t *arr = malloc(sizeof(uint8_t)*9);

arr[0] = 160;
arr[1] = 32;
arr[2] = 96;
arr[3] = 128;
arr[4] = 224;
arr[5] = 64;
arr[6] = 192;
arr[7] = 0;
arr[8] = 255;

for(int i = 0; i < 9, i++){
    printf(arr[i]);
}
quicksort(arr, 0, 8);

for(int i = 0; i < 9; i++){
    printf(arr[i]);
}
}

Sorry if this does not work coudnt test it I am currently not infront of my machine.

Answer 1

The main issue is that you are not always comparing with the pivot value. Your code assumes it is at i, but that will not be true once the j loop doesn't find anything to swap. In that case your outer loop will still decrease i, which at that moment no longer points to the pivot.

Also when you update pivot_position, you should take into account that you are about to move that pivot to index i-1, so it should take that value.

Then there is also a type issue. You've declared arr as a pointer to u_int8. But then your temp should not be defined as an int but as uint8_t.

If we just want to fix the minimum necessary, you could replace this:

        if (arr[j] >= arr[i])
        {
            pivot_position = i;
            int tmp = arr[left];

with this:

        if (arr[j] >= arr[pivot_position])
        {
            pivot_position = i-1;
            uint8_t tmp = arr[left];

But the double loop is inefficient. The inner loop starts from left over and over again. This is not needed. You only need to compare a value once with the pivot. Also, when there are only two values to partition, you don't really need a special case (the else block).

Also,

Here is how I would write it -- using that 3-cycle constraint:

int partition(uint8_t *arr, int left, int right) {
    // right will be the pivot index
    while (left < right) {
        if (arr[left] >= arr[right]) {
            uint8_t tmp = arr[left];
            arr[left] = arr[right-1];
            arr[right-1] = arr[right]; // Pivot value
            arr[right] = tmp; // Current value
            right--; // Adjust pivot index
        } else {
            left++; // The value is in the correct partition, so move on 
        }
    }
    return right; // Return pivot index
}