Quicksort. Exception in thread "main" java.lang.StackOverflowError

Question

Good day! I have here a Java program that does the quicksort. It reads a file then sorts the first 10,000 words in it. I followed the pseudocode of Thomas Cormen in his Introduction to Algorithms, Second Ed.

import java.io.*;
import java.util.*;

public class SortingAnalysis {

    public static int partition(String[] A, int p, int r) {
        String x = A[r];
        int i = p-1;
        for (int j=p; j < r-1; j++) {
            int comparison = A[j].compareTo(x);
            if (comparison<=0) {
                i=i+1;
                A[i] = A[j];
            }       
        }
        A[i+1] = A[r];
        return i+1;
    }

    public static void quickSort(String[] a, int p, int r) {
        if (p < r) {
            int q = partition(a, p, r);
            quickSort(a, p, q-1);
            quickSort(a, q+1, r);
        }
    }

    public static void main(String[] args) {
        final int NO_OF_WORDS = 10000;
        try {
            Scanner file = new Scanner(new File(args[0]));
            String[] words = new String[NO_OF_WORDS];
            int i = 0;
            while(file.hasNext() && i < NO_OF_WORDS) {
                words[i] = file.next();
                i++;
            }
            long start = System.currentTimeMillis();
            quickSort(words, 0, words.length-1);
            long end = System.currentTimeMillis();
            System.out.println("Sorted Words: ");
            for(int j = 0; j < words.length; j++) {
                System.out.println(words[j]);
            }
            System.out.print("Running time: " + (end - start) + "ms");

        }
        catch(SecurityException securityException) {
            System.err.println("Error");
            System.exit(1);
        }
        catch(FileNotFoundException fileNotFoundException) {
            System.err.println("Error");
            System.exit(1);
        }
    }
}

However, when I run the code, the console says
Exception in thread "main" java.lang.StackOverflowError at SortingAnalysis.partition and quickSort

I thought that the error was just because of the large size (ie, 10000) so I decreased it to 100 instead. However, it still doesn't sort the first 100 words from a file, rather, it displays the 100th word 100 times.
Please help me fix the code. I'm new in Java and I need help from you guys. Thank you very much!

EDIT: I now edited my code. It doesn't have an error now even when the NO_OF_WORDS reaches 10000. The problem is it halts the wrong sequence.

I did not check all, but this if ((comparison==0)&&(comparison<0)) does not look right. — Flavio
– Flavio, Commented Jul 9, 2012 at 7:21
For starters, your if statement inside your partition method can never be true (comparison==0)&&(comparison<0). && is AND - did you perhaps want OR instead? (comparison==0)||(comparison<0) or more succinctly (comparison<=0) — Rob Trickey
– Rob Trickey, Commented Jul 9, 2012 at 7:21
Another problem is for (int j=p; j > r-1; j++). The loop will never be entered. — Daniel Fischer
– Daniel Fischer, Commented Jul 9, 2012 at 7:24
Hello Flavio, Robert, and Daniel! I now edited my code. Thanks guys! Silly me. But it still doesn't sort the words right. But regardless of the NO_OF_WORDS, it has no error. :) — First Lady
– First Lady, Commented Jul 9, 2012 at 7:30
A Stackoverflow error would be caused by a too deep recursion, you got that right (you can somewhat mitigate this by increasing max stack size though). Your partitioning code seems a little bit fishy to me, you might wanna look into that. — Cubic
– Cubic, Commented Jul 9, 2012 at 7:32

Keppil · Accepted Answer · 2012-07-09 07:57:03Z

2

You have two problems:

the loop in partition() should run to j <= r - 1, you are jumping out early.

You are not swapping elements. Try the following code:

public static int partition(String[] A, int p, int r) {
   String x = A[r];
   int i = p - 1;
   for (int j = p; j <= r - 1; j++) {
       int comparison = A[j].compareTo(x);
       if (comparison <= 0) {
           i = i + 1;
           swap(A, i, j);
       }
   }
   swap(A, i + 1, r);
   return i + 1;
}

public static void swap(String[] a, int i, int j) {
   String temp = a[i];
   a[i] = a[j];
   a[j] = temp;    
}

answered Jul 9, 2012 at 7:57

Keppil

46.3k9 gold badges101 silver badges121 bronze badges

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

1 Comment

First Lady Over a year ago

Thank you very much, Keppil for providing the swap method! It now runs properly. Thank you!

alain.janinm · Accepted Answer · 2012-07-09 08:27:31Z

Looking at the Quicksort algo of wikipedia, the partition algo is the following :

// left is the index of the leftmost element of the array
// right is the index of the rightmost element of the array (inclusive)
//   number of elements in subarray = right-left+1
function partition(array, 'left', 'right', 'pivotIndex')
  'pivotValue' := array['pivotIndex']
  swap array['pivotIndex'] and array['right']  // Move pivot to end
  'storeIndex' := 'left'
  for 'i' from 'left' to 'right' - 1  // left ≤ i < right
      if array['i'] < 'pivotValue'
          swap array['i'] and array['storeIndex']
          'storeIndex' := 'storeIndex' + 1
  swap array['storeIndex'] and array['right']  // Move pivot to its final place
  return 'storeIndex'

In your method you don't use the pivotIndex value, you base your pivotValue on the right index. You need to add this parameter to your method.

Following the wiki algo it should be like this :

public static int partition(String[] A, int p, int r, int pivotIdx) {
    String x = A[pivotIdx];
    String tmp = A[pivotIdx];
    A[pivotIdx] = A[r];
    A[r]=tmp;
    int i = p;
    for (int j=p; j < r; j++) {
        int comparison = A[j].compareTo(x);
        if (comparison<=0) {
            tmp=A[i];
            A[i] = A[j];
            A[j]=tmp;
            i++;
        }       
    }
    tmp=A[i];
    A[i] = A[r];
    A[r]=tmp;
    return i;
}

Collectives™ on Stack Overflow

Quicksort. Exception in thread "main" java.lang.StackOverflowError

2 Answers 2

1 Comment

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Related