Quick Sort Algorithm showing Wrong Output

Question

I have written code of Quick Sort but it is showing Exception Array Index Out of bound.This works properly when written in C but in Java it is not working.Please tell what is the problem with it.Any Suggestion is appreciated.It is two way partition standard CLRS algorithm.

package Sorting;

public class QuickSort {

    public static void main(String arg[]) {
        int a[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };

        Sort(a, 0, a.length - 1);
        for (int i = 0; i < 9; i++) {
            System.out.print(" " + a[i]);
        }

    }

    private static void Sort(int[] a, int i, int j) {
        // TODO Auto-generated method stub
        if (i < j) {
            int k = Partition(a, i, j);
            Sort(a, i, k - 1);
            Sort(a, k + 1, j);

        }
    }

    private static int Partition(int[] a, int i, int j) {
        // TODO Auto-generated method stub
        int temp;
        int x = a[j];
        int l = i - 1;
        for (int n = i; n < j; n++) {
            if (a[n] >= x) {
                l++;
                temp = a[l];
                a[l] = a[n];
                a[n] = temp;
            }
        }
        temp = a[x];
        a[x] = a[l + 1];
        a[l + 1] = temp;
        return l + 1;

    }
}

Output: 9 3 5 7 4 1 6 2 8

I dont want to spend time going into the logic here but the error is in your for loop in partition. for (int n = i; i < j; n++) int i never gets incremented in the loop so this will run forever — Revive
– Revive, Commented Jun 26, 2014 at 13:26
At face value, Partition can't work. See the for loop. The condition is i < j. Neither i nor j changes in the body. Once execution enters, it's the Hotel California: "You can check out any time you like, but you can never leave." — Gene
– Gene, Commented Jun 26, 2014 at 13:26
@user3728933 I dont think you fully understand the quick sort algorithm. Your code doesnt look like its choosing a pivot to sort around at all/correctly. Here is a good link which explains how quick sort works youtube.com/watch?v=y_G9BkAm6B8 — Revive
– Revive, Commented Jun 26, 2014 at 14:46
Now your post says there is an out of bounds error and also gives output. Which is it? Assuming there is no more bounds error, I suggest you insert trace code (System.err.print), to figure out why Partition is not working. You will never learn if we debug your program for you. — Gene
– Gene, Commented Jun 26, 2014 at 15:46

s.u.m.i.t · Accepted Answer · 2014-06-27 08:44:30Z

2

there are some minor mistakes in your code, here is the updated code:

    private static int Partition(int[] a, int i, int j) {
    // TODO Auto-generated method stub      
    int temp;
    int x = a[j];
    int l = i - 1;
    for (int n = i; n < j; n++) {
        if (a[n] <= x) {      /*******Condition was wrong******/
            l++;
            temp = a[l];
            a[l] = a[n];
            a[n] = temp;
        }
    }
    temp = a[j];      /******a[j] not a[x] x is value of pivot element******/
    a[j] = a[l + 1];
    a[l + 1] = temp;
    return l + 1;
}

edited Jun 27, 2014 at 8:44

answered Jun 27, 2014 at 8:00

s.u.m.i.t

513 bronze badges

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

Comments

Nivas · Accepted Answer · 2014-06-26 13:29:10Z

1

In this loop in partition:

for (int n = i; i < j; n++)

You probably meant n<j than i<j. i never changesm so i<j is always true. n eventually becomes 9. a[9] does not exist, so the exception.

answered Jun 26, 2014 at 13:29

Nivas

18.4k4 gold badges65 silver badges76 bronze badges

3 Comments

suryansh Over a year ago

Now it is showing wrong output ,exception is removed.

Nivas Over a year ago

Exception is removed = your question is answered. Now you need to debug why it is not working :-) Please post any specific questions and we can help.

suryansh Over a year ago

Okk but question is updated now.If you can help please do.Effort is appreciated.

Jens · Accepted Answer · 2014-06-26 14:15:01Z

1

i is always lower than j bacause i anj doesn't change

for (int n = i; i < j; n++)

so you have an endless loop.

edited Jun 26, 2014 at 14:15

answered Jun 26, 2014 at 13:26

Jens

69.6k15 gold badges107 silver badges133 bronze badges

5 Comments

Erich Kitzmueller Over a year ago

No, because a[n] will cause an exception as soon as n>=a.size()

Jens Over a year ago

@ammoQ That is right. But n > a.size() because of the endless loop.

Jens Over a year ago

@user3728933 The question "why is my code not working" is off-topic.

suryansh Over a year ago

@Jenes Not Working Output is 1 3 5 4 6 7 2 8 9

Jens Over a year ago

Here you have a working implementation

Collectives™ on Stack Overflow

Quick Sort Algorithm showing Wrong Output

3 Answers 3

Comments

3 Comments

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

3 Comments

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related