Java ArrayList quickSort algorithm not working properly

Question

I am trying to sort an ArrayList of integers in numerical order using a quicksort algorithm. The below code is what I have been able to come up with and it is getting close to sorting the list but unfortunately, it does not completely sort my ArrayList as it should. It will come pretty close but it is almost as if it just needs to run the while loop a few more times to completely sort the list. I have been trying for quite a long time now to figure out why my code won't work properly so any help would be appreciated.

Right now these are the results I am getting:

Pre-sort: [9, 2, 10, 3, 6, 7, 4, 8, 5, 1]

Post-sort: [1, 2, 5, 3, 4, 6, 7, 8, 9, 10]

 /**
     * 
     * This method performs a quicksort on the generic ArrayList given as input. You
     * must implement three different strategies for determining the pivot, and your
     * implementation should be able to easily switch among these strategies.
     * (Consider using a few private helper methods for your different
     * pivot-selection strategies.) You will perform timing experiments to determine
     * which strategy works best. Your implementation may switch to insertion sort
     * on some small threshold, if you wish.
     * 
     * @param <T>
     */
    static <T extends Comparable<? super T>> void quickSort(ArrayList<T> quickList, int begin, int end) {
        if (begin < end) {
            int partitionIndex = partition(quickList, begin, end);

            quickSort(quickList, begin, partitionIndex - 1);
            quickSort(quickList, partitionIndex + 1, end);
        }
    }

    
    private static <T extends Comparable<? super T>> int partition(ArrayList<T> quickList, int begin, int end) {
        int init = begin;
        int length = end;

        int pivot = quicksort.getRandom(quickList);
        
        while (true) {
            while ((int) quickList.get(length) > (int) pivot && length > begin) {
                length--;
            }

            while ((int) quickList.get(init) < (int) pivot && init < end) {
                init++;
            }

            if (init < length) {
                T temp;
                temp = quickList.get(init);
                quickList.set(init, quickList.get(length));
                quickList.set(length, temp);
                length--;
                init++;

            } else {
                return length;
            }
        }
    }

    
    public interface quicksort {
        /**
         * This method will grab the median of the entire ArrayList
         * 
         * @return median
         */
        static <T> int getMedian(ArrayList<T> passedArrayList) {
            double lower = 0;
            double upper = 0;

            if (passedArrayList.size() % 2 == 1)
                System.out.println(passedArrayList.get((passedArrayList.size() + 1) / 2 - 1));
            else {
                // Will make sure that our passed array is able to be divided
                lower = (double) (passedArrayList.size() / 2 - 1);
                upper = (double) (passedArrayList.size() / 2);
            }

            return (int) Math.round((lower + upper) / 2.0);
        }

        /**
         * This method will randomly grab a index out of the provided ArrayList
         * 
         * @param <T>
         * @return median
         */
        static <T> int getRandom(ArrayList<T> passedArrayList) {
            int arrayListSize = passedArrayList.size();

            Random rand = new Random(); // instance of random class
            int upperbound = arrayListSize;
            int randomIndex = rand.nextInt(upperbound);

            return randomIndex;
        }

        /**
         * This method will grab three random indexes and then determine the median
         * based off of those
         * 
         * @return median
         */
        static <T> int getThreeRandomThenMedian(ArrayList<T> passedArrayList) {
            int[] intArray;
            intArray = new int[3];

            // sets are array with 3 random numbers from our passedArrayList
            intArray[0] = getRandom(passedArrayList);
            intArray[1] = getRandom(passedArrayList);
            intArray[2] = getRandom(passedArrayList);

            // finds the median of our 3 random numbers
            Arrays.sort(intArray);
            double median;
            if (intArray.length % 2 == 0)
                median = ((double) intArray[intArray.length / 2] + (double) intArray[intArray.length / 2 - 1]) / 2;
            else
                median = (double) intArray[intArray.length / 2];

            // converts our median from a double to a int so we can grab the median from our
            // array
            int returnMedian = (int) Math.round(median);

            return returnMedian;
        }
    }

I'm not sure how running a String array though would help. When I do this is just fails at while ((int) quickList.get(length) > (int) pivot && length > begin) { length--; } — Alex
– Alex, Commented Oct 6, 2022 at 5:50
String values can be easy to tell from index values. (So choose "A", "G", "O"…, not "3", "1", "4"…) (Why cast to int?) — greybeard
– greybeard, Commented Oct 6, 2022 at 6:53

Oleg Cherednik · Accepted Answer · 2022-10-06 08:08:45Z

1

// 3-way quicksort
public final class QuickSort {

    public static <T extends Comparable<? super T>> void quickSort(List<T> items) {
        Collections.shuffle(items);  // sorted array is the worst case
        quickSort(items, 0, items.size() - 1);
    }

    private static <T extends Comparable<? super T>> void quickSort(List<T> items, int lo, int hi) {
        if (lo < hi) {
            Pair pair = partition(items, lo, hi);
            quickSort(items, lo, pair.lt - 1);
            quickSort(items, pair.gt + 1, hi);
        }
    }

    private static <T extends Comparable<? super T>> Pair partition(List<T> items, int lo, int hi) {
        int lt = lo;
        int i = lo + 1;
        int gt = hi;
        T item = items.get(lo);

        while (i <= gt) {
            int cmp = items.get(i).compareTo(item);

            if (cmp < 0)
                swap(items, lt++, i++);
            else if (cmp > 0)
                swap(items, i, gt--);
            else
                i++;
        }

        return new Pair(lt, gt);
    }

    private static <T> void swap(List<T> items, int i, int j) {
        T tmp = items.get(i);
        items.set(i, items.get(j));
        items.set(j, tmp);
    }

    private static final class Pair {

        private int lt;
        private int gt;

        public Pair(int lt, int gt) {
            this.lt = lt;
            this.gt = gt;
        }
    }

    private QuickSort() {
    }

}

Demo

List<Integer> items = Arrays.asList(9, 2, 10, 3, 6, 7, 4, 8, 5, 1);
System.out.println(items);  // [9, 2, 10, 3, 6, 7, 4, 8, 5, 1
QuickSort.quickSort(items);
System.out.println(items);  // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. - 2.3 Quicksort is your friend!

edited Oct 6, 2022 at 8:08

answered Oct 6, 2022 at 6:50

Oleg Cherednik

18.3k4 gold badges25 silver badges38 bronze badges

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

2 Comments

Alex Over a year ago

Thanks @oleg.cherednik this code worked great. I just have one other question for you how would I chose a different pivot point? Right now it is sorting the list based off of the first item an the array list but what if I wanted to sort the list based off of a random number? I tried changing the item variable and it does not sort the ArrayList properly.

Oleg Cherednik Over a year ago

This is a bit tricky. You can choose any point you want, even make it random. As result you should have two separated array in perfect case with the same size (to keep going sorting with O(log n))

Collectives™ on Stack Overflow

Java ArrayList quickSort algorithm not working properly

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