QuickSort Java implementation issue

Question

I'm trying to implement a QuickSort algorithm as a homework at the university, but I just fail to understand where there is a mistake in my code. I suppose it's a logical mistake, I think I swap my pivot wrongly. I could really use some help, thank you in advance. There is the code:

public class QuickSort {
    private int [] array;

    public QuickSort(int [] array){
        this.array = array;
    }

    public void sort(){
        partition(0, array.length - 1);
    }

    public void partition(int start, int end){
        if (end - start < 2){
            return;
        }
        int pivot_index = end;
        int i = start;
        int j = end - 1;
        while (i < j){
            //both elements are not in the right place
            if(array[i] > array[pivot_index] && array[j] <= array[pivot_index]){
                swap(array, i, j);
                i++;
                j--;
            }
            //the element on the left is not in place
            else if (array[i] > array[pivot_index] && array[j] > array[pivot_index]){
                j--;
            }
            //the element on the right is not in place
            else if (array[i] < array[pivot_index] && array[j] < array[pivot_index]){
                i++;
            }
            //both elements are in place
            else {
                i++;
                j--;
            }
        }
        if (array[i] > array[pivot_index]){
            swap(array, pivot_index, i);
            pivot_index = i;
        }
        partition(start, pivot_index - 1);
        partition(pivot_index + 1, end);
    }

    private static void swap(int [] tab, int index1, int index2){
        int temp = tab[index1];
        tab[index1] = tab[index2];
        tab[index2] = temp;
    }
}

Describe the behaviour you observe and how that is erroneous. What have you done to find out what goes wrong? What have you based your implementation on? — greybeard
– greybeard, Commented Apr 23, 2017 at 8:05
@greybeard I've been observing the algorithm on many examples, using the debug feature. In some examples it does work, in others it doesn't. The sorting issue usually occurs, when there are repeated elements in the array. I understand how it works exactly, but I fail to understand what I should add to make it work. For instance, there is the input array: 19 3 10 9 2 1 4 19 and the output after sorting: 1 2 3 4 9 19 10 19 — Andrej Korowacki
– Andrej Korowacki, Commented Apr 23, 2017 at 11:57
(Generally, only comment comments asking for information or clarification when you are positive your post isn't lacking - otherwise, edit your post.) I understand how it works exactly Please explain how the handling of values equal to array[pivot_index] is correct. Comment your code! — greybeard
– greybeard, Commented Apr 23, 2017 at 13:10

Junbang Huang · Accepted Answer · 2017-04-23 14:29:11Z

2

Solution one

The idea is iterating through the array to check whether the current element is smaller than the last one (the pivot), if yes swap with the first one that is not (index is lastSmaller + 1).

private void partition(int start, int end) {
    if (start >= end) {
        return;
    }

    int lastSmallest = start - 1;
    for (int i = start; i < end; i++) {
        if (array[i] < array[end])
            swap(++lastSmallest, i);
    }

    swap(++lastSmallest, end);
    partition(start, lastSmallest - 1);
    partition(lastSmallest + 1, end);
}

Solution two

I think this is what you want to implement. Iterate through the array, skip all the elements in good place on the left and right. Swap the two in wrong place.

    private void partition(int start, int end) {
        if (end <= start) {
            return;
        }
        int k = end;
        int i = start;
        int j = end - 1;
        while (i < j) {
            // left is in place
            while (i < j && array[i] < array[k]) {
                i++;
            }
            // right is in place
            while (i < j && array[j] >= array[k]) {
                j--;
            }

            // both are not good
            if (i < j) {
                // swap
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;

                i++;
                j--;
            }
        }

        // swap left and pivot
        if (array[i] >= array[k]) {
            int temp = array[i];
            array[i] = array[k];
            array[k] = temp;
        }
        partition(start, i - 1);
        partition(i + 1, end);
}

The reason why your solution does not work is that when you find both are not in place, you swap them and continue to partition the rest of the array. However, you can not guarantee what you have swapped does not violate the rule. Therefore, you need to skip all the elements in place on both side first then swap.

edited Apr 23, 2017 at 14:29

answered Apr 23, 2017 at 0:41

Junbang Huang

1,97719 silver badges28 bronze badges

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

3 Comments

Andrej Korowacki Over a year ago

yes, it works, thank you very much, but I still want to know, what is wrong with my implementation

Junbang Huang Over a year ago

I will work on that, please show what you got and how it different from what you want it to be,

Junbang Huang Over a year ago

@AndrejKorowacki I've updated my answer based on your idea. Hope this helps. If it does, please upvote and mark as correct. If it does not, let me know.

Collectives™ on Stack Overflow

QuickSort Java implementation issue

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest