CODEWITHSUNDEEP
c#quicksort
Joel Trauger
Joel Trauger

Reputation: 732

quicksort algorithm not sorting final element?

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

Upvotes: 1

Views: 624

Answers (1)

MoustafaS
MoustafaS

Reputation: 2031

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

Upvotes: 3

Related Questions