infinite loop in quicksort java

Question

I try to realize an algorithm of quicksort, but when I run my code, it gives me an infinite loop, I don't understand, where I make mistake in partition method in my code:

public static int partition(int[] a, int p, int r)
{
    int x = a[p];
    int i = p;
    int j = r + 1;
    while(true)
    {
        while(a[i] < x) 
        {
            i++;
            if (i == r) break;
        }
        while(x > a[j]) 
        {
            j--;
            if (j == p) break;
        }
        if (i >= j) break;

        int tmp = a[i];
        a[i] = a[j];
        tmp = a[i];
    }

    int exch = a[p];
    a[p] = a[j];
    exch = a[p];

    return j;
}

the input data for this code:

private static int[] array;
private static Scanner sc = new Scanner(System.in);
public static void main(String[] args){
    int n, m;
    n = sc.nextInt();
    array = new int[n+1];
    int i,j;
    for (i = 0; i != array.length-1; i++)
        array[i] = sc.nextInt();


    for (j = 0; j !=array.length-1; i++)
        System.out.print(array[j]);
    quickSort(array,0,array.length);

}

Answer 1

You are implementing the Cormen Algorithms version of the Quicksort algorithm. His version goes like this (no mention of copyright infrangiment, this is found with a simple Google search):

Your version misses almost all of it. Just for example on your first two lines:

int x = a[p]; //Should be a[r]
int i = p; //Should be p-1

Check again every single step of the algorithm and only AFTER you really understood how the agorithm works retry to write the correct function.

Also your quicksort function should be recursive, which I hope you know what it means.

HINT: There are 2 functions, one recursive (quickSort) and one with only one for loop (partition).

---

EDIT: I took the wrong quicksort algorithm from the book, sorry for that. The correct one, the one you are using, is as follows:

Still you are implementing it with some very basic errors. Here are the most evident ones:

• You are using a while loop instead of a do-until (do-while in Java) loop, which are very different.

• You are mixing the two algorithms, swapping (wrongly as my first comment pointed out) two times the values when in the Hoare-Partition is only done once.

• You don't need the if (i >= j) break; and the if (i == r) break; loop end condition because, for construction of the algorithm, they can never happen (either if you use a[i] < x as breaking condition or a[i] >= x as permitting condition). This shows that you didn't fully understand how the algorithm works.

• int i = p; //Should be p-1 is still wrong.

Again, check every single step of the algorithm and correct it, you are on your way! :)

UPDATE: I've tried the Hoare Partition with the corrections above and the output with the input int[] a = {13,19,9,5,12,8,7,4,11,2,6,21}; after every swap is (btw this is the answer to (a) question in the book):

[6, 19, 9, 5, 12, 8, 7, 4, 11, 2, 13, 21]
[6, 13, 9, 5, 12, 8, 7, 4, 11, 2, 19, 21]
[6, 2, 9, 5, 12, 8, 7, 4, 11, 13, 19, 21]
[4, 2, 9, 5, 12, 8, 7, 6, 11, 13, 19, 21]
[4, 2, 6, 5, 12, 8, 7, 9, 11, 13, 19, 21]
[4, 2, 5, 6, 12, 8, 7, 9, 11, 13, 19, 21]
[2, 4, 5, 6, 12, 8, 7, 9, 11, 13, 19, 21]
[2, 4, 5, 6, 11, 8, 7, 9, 12, 13, 19, 21]
[2, 4, 5, 6, 9, 8, 7, 11, 12, 13, 19, 21]
[2, 4, 5, 6, 7, 8, 9, 11, 12, 13, 19, 21]

This was solely to check if the algorithm works (maybe a print error could have caused the infinite loop).

Answer 2

The basics of quick sort try this it may solve your problem.

              if (i <= j) {
              tmp = a[i];
              a[i] = a[j];
              a[j] = tmp;
              i++;
              j--;}


           **int exch = a[p];
            a[p] = a[j];
            a[p] = exch;**

Edited your code. i will suggest you to use for-loop.

 public static int partition(int[] a, int p, int r)
    {
        int x = a[p];
        int i = p;
        int j = r + 1;
        while(true)
        {
            while(a[i] < x) 
            {
                i++;
                if (i == r) break;
            }
            while(x > a[j]) 
            {
                j--;
                if (j == p) break;
            }
     if (i <= j) {
          tmp = a[i];
          a[i] = a[j];
          a[j] = tmp;
          i++;
          j--;}

        **int exch = a[p];
        a[p] = a[j];
        a[p] = exch;**

        return j;
    }

Answer 3

Try

a[j] = exch;

instead of

exch = a[p];

and identical bug -- thanks to @Namer and @Zhuinden -- in your code:

int tmp = a[i];
a[i] = a[j];
tmp = a[i];

Thanks to @DeepanshuBedi, Quicksort in Java - Tutorial has a description of the algorithm. It has

i++;
j--;

after the swap in the loop.

In addition, the function is expected to be recursive:

if (low < j)
  quicksort(low, j);
if (i < high)
  quicksort(i, high); 

instead of your second swap.

I suggest you to copy the code from that page -- your code doesn't look to me as quicksort.