How do I change iterative quicksort with fixed pivot to iterative quicksort with random pivot?

Question

I found this code for quicksort with a fixed pivot. It always takes a right-hand side element of the given table as a pivot. I want it to take a random element as a pivot. I think that x is a pivot here, so I thought it was a good idea to change it to a random element from a given list, but it turns out that it is not working.

void swap ( int* a, int* b )
{
    int t = *a;
    *a = *b;
    *b = t;
}


int partition (int arr[], int l, int h)
{
    int x = arr[h];
    int i = (l - 1);
    for (int j = l; j <= h- 1; j++)
    {
        if (arr[j] <= x)
        {
            i++;
            swap (&arr[i], &arr[j]);
        }
    }
    swap (&arr[i + 1], &arr[h]);
    return (i + 1);
}

void quickSortIterative (int arr[], int l, int h)
{
    int stack[ h - l + 1 ]; 
    int top = -1;

    stack[ ++top ] = l;
    stack[ ++top ] = h;

    while ( top >= 0 )
    {
        h = stack[ top-- ];
        l = stack[ top-- ];

        int p = partition( arr, l, h );

        if ( p-1 > l )
        {
            stack[ ++top ] = l;
            stack[ ++top ] = p - 1;
        } 
        if ( p+1 < h )
        {
            stack[ ++top ] = p + 1;
            stack[ ++top ] = h;
        }
    }
}

I tried changing lines

int x = arr[h];

and

swap(&arr[i+1], &arr[j]);

to

int r = l+rand()%(h-l);
int x = arr[r];

and then

swap(&arr[i+1], &arr[r]);

but it is not sorting properly. Obviously I'm doing something wrong here. Please help.

Any reason why recursion is replaced with the use of variable-length arrays? It's not going to save you from stack overflows. — Alexey Frunze
– Alexey Frunze, Commented Mar 20, 2013 at 6:21
@Alexey Frunze It is my college exercise. I am supposed to compare different kinds of quicksorts. No problems with recursive one (either with fixed and random pivot), but iterative was a problem to implement for me. I ended up using someone else's code and that resulted in not understanding it. — raven_raven
– raven_raven, Commented Mar 20, 2013 at 6:37

Syed Albiz · Accepted Answer · 2013-03-20 06:03:05Z

2

Your partition function assumes the pivot is at the end of the partition. Consider moving your random pivot to the end of the partition first.

i.e. add

swap(&arr[r], &arr[h]);

after choosing your pivot.

answered Mar 20, 2013 at 6:03

Syed Albiz

912 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

nullptr · Accepted Answer · 2013-03-20 06:05:41Z

2

The problem is that the 'partition' function now moves the pivot so it doesn't remain at the r index. And the function also misses the last element (at index h). The simplest solution would be to place the pivot to the right-most position just after selecting it, and remain everything other the same: put swap(&arr[r], &arr[h]); before the first loop in partition(), and restore the last swap to swap (&arr[i + 1], &arr[h]);

answered Mar 20, 2013 at 6:05

nullptr

11.1k1 gold badge26 silver badges19 bronze badges

Collectives™ on Stack Overflow

How do I change iterative quicksort with fixed pivot to iterative quicksort with random pivot?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related