QuickSort function in Java is giving a StackOverflow

Question

I know this isn't really a bug-testing place, but I've been trying to spot my error in my java quicksort for hours, and I can't see it, so if anyone can point it out to me I'd be very very grateful.

Here's example:

     public class QuickSort {
    public static int partition(int[] a, int start, int end) {

        int piv = a[end];
        int iLeft = start;
        int iRight = end;
        while (iLeft < iRight) {
            while (a[iLeft] < piv) {
                iLeft++;
            }
            while (a[iRight] >= piv) {
                iRight--;
                if (iRight == iLeft) {
                    break;
                }
            }

            if (iLeft < iRight) {
                int val = a[iLeft];
                a[iLeft] = a[iRight];
                a[iRight] = val;
            }

        }
        return iRight;
    }

    public static int[] Sort(int[] a, int start, int end) {
        if (a.length < 2) {
            return a;
        } else {
            int Next_Mid = partition(a, start, end);
            Sort(a, start, Next_Mid);
            Sort(a, Next_Mid + 1, end);
            return a;
        }
    }

    public static void main(String[] args) {
        int[] c = new int[] { 1, 10, 2, 9, 3, 8, 3, 7, 4, 6, 5 };
        Sort(c, 0, c.length - 1);
    }
}

How do you know there is an error? Have you seen the error? When does it occur? — Uxonith
– Uxonith, Commented Jan 22, 2014 at 16:23
Pasting / explaining the bug you are seeing would be helpful... — drunkenRabbit
– drunkenRabbit, Commented Jan 22, 2014 at 16:23

Sergey Kalinichenko · Accepted Answer · 2014-01-22 16:24:37Z

4

Since your Sort method never makes a new sub-array for a, your exit condition is wrong: if a starts with 10 elements, it would always have ten elements, so your recursion will never end.

You need to check if the start and the end indexes are two or less positions apart:

if (end-start < 2) {
    return a;
}

answered Jan 22, 2014 at 16:24

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

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

Comments

Ingo · Accepted Answer · 2014-01-22 16:25:05Z

1

The error is obvious:

public static int[] Sort(int[] a, int start, int end) {
  if (a.length < 2) {
    return a;
  } else {
    int Next_Mid = partition(a, start, end);
    Sort(a, start, Next_Mid);
    Sort(a, Next_Mid + 1, end);
    return a;
  }
}

Recursion can only end if length of the array is < 2, and yet you pass the same array all the time.

You probably want to look for end-start or something.

answered Jan 22, 2014 at 16:25

Ingo

36.4k6 gold badges57 silver badges102 bronze badges

Collectives™ on Stack Overflow

QuickSort function in Java is giving a StackOverflow

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related