quicksort algorithm not sorting final element?

Question

I have this code that I wrote using an algorithm I found on Wikipedia:

    public static void quicksort(int[] arr, int low, int hi)
    {
        if(low < hi)
        {
            int pivot = part( arr, low, hi);
            quicksort( arr, low, pivot - 1);
            quicksort( arr, pivot + 1, hi);
        }
    }
    public static int part(int[] arr, int low, int hi)
    {
        int pivot = arr[hi];

        int i = low;
        for(int j = low; j < hi - 1; j++)
        {
            if(arr[j] <= pivot)
            {
                swap(arr, i, j);
                i++;
            }
        }
        swap(arr, i, hi);
        return i;
    }

    public static void swap(int[] ar, int a, int b)
    {
        int temp = ar[a];
        ar[a] = ar[b];
        ar[b] = temp;
    }

Given this input:

31, 5, 5, 5, 5, 4, 4, 4, 5, 4

one should expect to get:

4, 4, 4, 4, 5, 5, 5, 5, 5, 31

but instead I get:

4, 4, 4, 4, 5, 5, 5, 5, 31, 5

What gives?

I call the initial sort with: quicksort(array, 0, array.Length - 1);

Goes out of bounds on the array when I do that. Zero-indexing means that the upper index is one less than the length. — Joel Trauger
– Joel Trauger, Commented Jul 25, 2016 at 16:10

trashr0x · Accepted Answer · 2016-07-25 16:25:10Z

3

If you call it using Length - 1, then this loop:

 for (int j = low; j < hi - 1; j++)

..should be:

 for (int j = low; j <= hi ; j++)

edited Jul 25, 2016 at 16:25

trashr0x

6,5953 gold badges33 silver badges41 bronze badges

answered Jul 25, 2016 at 16:10

MoustafaS

2,03113 silver badges20 bronze badges

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

2 Comments

Joel Trauger Over a year ago

That fixed it. Thanks. I just needed a second set of eyes to look at it because I couldn't see that error. I'll accept ASAP but it won't let me right now.

BMW Over a year ago

I think you still need the -1, i.e j <= hi - 1.

Collectives™ on Stack Overflow

quicksort algorithm not sorting final element?

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related