How can I avoid a stack overflow error with quicksorting algorithm implementation

Question

// If, like me, the goal is to use the algorithm in some other code (and not to code the algorithm itself), Arrays.sort (Documentation here) did the job! //

I keep getting this error :

Exception in thread "main" java.lang.StackOverflowError
at language.LanguageDetection.sort(LanguageDetection.java:140)
at language.LanguageDetection.sort(LanguageDetection.java:141)
at language.LanguageDetection.sort(LanguageDetection.java:141)

And this line :

at language.LanguageDetection.sort(LanguageDetection.java:141)

Fills the rest of the console output.

I am a beginner in java and I am trying to implement a quick sort algorithm in order to sort a text file containing all dictionary words, so I can then quickly search through it quickly.

I really don't know if this is the way to go or if there would be a more suitable sorting algorithm for this problem, but here is the code :

public static void sort(String[] unsorted, int startIndex, int endIndex)
{
 if(endIndex - startIndex <= 0) return; //Ends the recursion when unsorted array is of size 1
 String temp;

 char pivot = unsorted[endIndex].charAt(0);

 int j = startIndex;
 for(int i = startIndex; i < endIndex; i++)
 {
  if(unsorted[i].charAt(0) < pivot)
  {
   temp = unsorted[j];
   unsorted[j] = unsorted[i];
   unsorted[i] = temp;
   j++;
  }
 }
 temp = unsorted[j];
 unsorted[j] = unsorted[endIndex];
 unsorted[endIndex] = temp;

 sort(unsorted, startIndex, j - 1);
 sort(unsorted, j + 1, endIndex);

}

I don't want to have all the corrected version of the code, just some answers about, what I am coding wrong and if there is a better way of doing this.

Thanks in advance.

Compare you solution with this one vogella.com/tutorials/JavaAlgorithmsQuicksort/article.html and see what you can do. — Jorge Campos
– Jorge Campos, Commented Mar 21, 2017 at 2:37
Does it always cause stack overflow? - or work if the list is short, e.g. 10 items. — weston
– weston, Commented Mar 21, 2017 at 2:45
It does sound like you actually need the list to be sorted for some other purpose and that coding a sort algorithm isn't the end goal? So if DIY isn't the goal, just Arrays.sort it. — weston
– weston, Commented Mar 21, 2017 at 2:50
@weston No, it does not, I tried with a small file and it worked perfectly, maybe a quick sort algorithm is not the right choice or maybe I am implementing it wrong... I keep researching! — user7743022
– user7743022, Commented Mar 21, 2017 at 2:57
Well it will be limited by the stack. You can't sort millions of items like this without the blowing the stack. If you don't know what that is, look here: stackoverflow.com/questions/26158/… — weston
– weston, Commented Mar 21, 2017 at 3:03

Matt Timmermans · Accepted Answer · 2017-03-21 04:00:22Z

1

The simple solution:

Quicksort partitions the input array into two subarrays, and then sorts the subarrays. To sort the subarrays, first recurse to sort the smaller one, and then loop to sort the larger one.

Since each recursive call is <= half the size of its caller, the recursive depth is limited to log(N).

answered Mar 21, 2017 at 4:00

Matt Timmermans

60.9k3 gold badges57 silver badges106 bronze badges

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

Collectives™ on Stack Overflow

How can I avoid a stack overflow error with quicksorting algorithm implementation

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related