0

I'm currently working on QuickSort in Java, and I've successfully sorted the list for the first iteration. Nonetheless, my recursion implementation is not doing what I want. What can be the reason for that?

The list is [11, 4, 53, 65, 44, 23, 202, 37, 1]

...
quickSort(list, 0, list.size() - 1);
...

public static List<Integer> quickSort(List<Integer> l1, int from, int to) {
        if (l1.size() < 2)
            return l1;
        int pivot = l1.get(to);
        int counterLastSwapPos = 0;
        int counter = from;
        while (counter < l1.indexOf(pivot)) {
            if (l1.get(counter) >= pivot)
                counter++;
            else {
                int temp = l1.get(counter);
                l1.set(counter, l1.get(counterLastSwapPos));
                l1.set(counterLastSwapPos, temp);
                counterLastSwapPos++;
            }
            System.out.println(l1);
        }
        quickSort(l1, 0, l1.indexOf(pivot));
        quickSort(l1, l1.indexOf(pivot) + 1, l1.size());
        return l1;
    }

8
  • By the way, you should either choose your pivot randomly or keep it right in the middle of from and to, rather than putting it at the end (to) Commented May 24, 2020 at 20:13
  • @user really? What can you say about this explanation video ?youtu.be/ZHVk2blR45Q?t=507 Commented May 24, 2020 at 20:17
  • @user I tried with sublists already, but then how will I add them all up together? I wanted to manipulate the original list only so I don't have to think about how to connect the sorted list like in Merge Sort e.g. Commented May 24, 2020 at 20:26
  • I'm not sure, but that video doesn't seem to be using the same algorithm that you are, as far as I can see. See this: geeksforgeeks.org/quick-sort Commented May 24, 2020 at 20:26
  • 1
    What do you mean? Is it here? quickSort(l1, 0, l1.indexOf(pivot)); quickSort(l1, l1.indexOf(pivot) + 1, l1.size()); If so, do this quickSort(l1, from, l1.indexOf(pivot)); quickSort(l1, l1.indexOf(pivot) + 1, to); Commented May 24, 2020 at 20:29

1 Answer 1

1

Here is the correct implementation of Quicksort In-Place in Java (ascending order).

 public static List<Integer> quickSort(List<Integer> l1, int from, int to) {
        System.out.println("Quick Sort \n");

        long startTime = System.nanoTime();
        //select a pivot - the last element of the list
        int pivot = l1.get(to - 1);
        //introduce two counters:
        int counterLastSwapPos = 0;//this first one will track the index of the element
        //that is bigger than the pivot - we start from zero (we never actually
        // know that this number is actually bigger - it is a
        // presupposition)
        for (int counter = 0; counter < l1.indexOf(pivot); counter++) {
            //we also have a counter to track our position during the iteration
            //if the element at the current position is smaller than the pivot
            //swap the element(current position) with the element that is bigger
            //than the pivot.
            if (l1.get(counter) < pivot) {
                int temp = l1.get(counter);
                l1.set(counter, l1.get(counterLastSwapPos));
                l1.set(counterLastSwapPos, temp);
                //Once the swap has happened - increment the counter
                //that tracks the number bigger than the pivot
                counterLastSwapPos++;
                //finally, in the loop, the position counter will be
                //automatically incremented
            }
            //when the position counter reaches the last allowed position,
            //swap the pivot with the the counter that tracks
            // the number bigger than the pivot
            if (counter == l1.indexOf(pivot) - 1) {
                l1.set(l1.indexOf(pivot), l1.get(counterLastSwapPos));
                l1.set(counterLastSwapPos, pivot);
            }
        }
        //as this sorting is a "Divide&Conquer" type, we use recursion to perform
        //the same operations on two parts of the list. That is why, (if you scroll up),
        //you'll see that once the list becomes size of 1, the recursion will stop.
        //Our pivot is now somewhere in the middle - this was our aim.
        //Now, pay attention to perform the recursion on
        //two lists that WILL NOT include the pivot itself
        if (from < l1.indexOf(pivot)) quickSort(l1, from, l1.indexOf(pivot));
        if (l1.indexOf(pivot) + 1 < to) quickSort(l1, l1.indexOf(pivot) + 1, to);
        //list is sorted
        long endTime = System.nanoTime();
        long duration = (endTime - startTime);
        System.out.println("Time: " + duration + "\n");

        return l1;
    }
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.