jeudi 30 mars 2017

Random Pivot(QuickSort) not sorting correctly

This is a quick sort algorithm with a random pivot. It is not sorting the array correctly and I cannot figure out why. Would anyone be able to point out any mistakes I made? I don't know if I screwed up in a place or if there is something just wrong somewhere. Thanks in advance.

import java.util.*;

public class QuickRand
{
    public static <T extends Comparable<? super T>> void quickSort(T[] array, int n)
    {
        quickSort(array, 0, n-1);
    }

    public static <T extends Comparable<? super T>> void quickSort(T[] array, int first, int last)
    {
        if (first < last)
        {
            // create the partition: Smaller | Pivot | Larger
            int pivotIndex = partition(array, first, last);

            // sort subarrays Smaller and Larger
            quickSort(array, first, pivotIndex - 1);
            quickSort(array, pivotIndex + 1, last);
        }
    }

    private static <T extends Comparable<? super T>> int partition(T[] a, int first, int last)
    {
        Random r = new Random();
        int pivotIndex = first + r.nextInt(last - first + 1); //random pivot
        T pivot = a[pivotIndex];

        // determine subarrays Smaller = a[first..endSmaller]
        //                 and Larger  = a[endSmaller+1..last-1]
        // such that elements in Smaller are <= pivot and 
        // elements in Larger are >= pivot; initially, these subarrays are empty

        int indexFromLeft = first; 
        int indexFromRight = last; 

        boolean done = false;
        while (!done)
        {
            // starting at beginning of array, leave elements that are < pivot; 
            // locate first element that is >= pivot
            while (a[indexFromLeft].compareTo(pivot) < 0)
                indexFromLeft++;

            // starting at end of array, leave elements that are > pivot; 
            // locate first element that is <= pivot

            while (a[indexFromRight].compareTo(pivot) > 0 && indexFromRight > first)
                indexFromRight--;

            // Assertion: a[indexFromLeft] >= pivot and 
            //            a[indexFromRight] <= pivot.
            if (indexFromLeft < indexFromRight)
            {
                swap(a, indexFromLeft, indexFromRight);
                indexFromLeft++;
                indexFromRight--;
            }
            else 
                done = true;
        } // end while

        // place pivot between Smaller and Larger subarrays
        swap(a, pivotIndex, indexFromLeft);
        pivotIndex = indexFromLeft;

        return pivotIndex; 
    }  // end partition

    private static void swap(Object [] a, int i, int j)
    {
        Object temp = a[i];
        a[i] = a[j];
        a[j] = temp; 
    } // end swap
}




Aucun commentaire:

Enregistrer un commentaire