Stack Overflow in Java QuickSort on Array

Question

Does anyone have any idea why I would be getting a stack overflow on my quicksort in the following code?:

   private int[] concat( int[] less, int inxl, int pivot, int inxm, int[] more )
   {

      int[] concated = new int[ less.length ];

      for( int inx = 0; inx < inxl; inx++ )
      {

         concated[ inx ] = less[ inx ];

      }

      concated[ inxl ] = pivot;
      inxl++;

      for( int inx = 0; inx < inxm; inx++ )
      {

         concated[ inxl ] = more[ inx ];
         inxl++;

      }      

      return concated;

   }

   private int[] quickSort( int[] array )
   {

      if( array.length <= 1 )
         return array;

      int[] less = new int[ array.length ];
      int[] more = new int[ array.length ];
      int inxl = 0, inxm = 0;

      for( int inx = 1; inx < array.length; inx++ )
      {

         if( array[ inx ] < array[ 0 ] )
         {

            less[ inxl ] = array[ inx ];
            inxl++;

         }
         else
         {

            more[ inxm ] = array[ inx ];
            inxm++;

         }

      }

      return concat( quickSort( less ), inxl, array[ 0 ], inxm, quickSort( more ) );

   }

Any help would be greatly appreciated. I am revising for an interview and been a little rusty so time is of grave importance. Thanks upfront! :)

Sincerely, Piotr.

Paŭlo Ebermann · Accepted Answer · 2011-05-21 18:43:55Z

6

Your quickSort method's recursion is wrong. It should call itself with smaller arrays (or with some other parameter which gets smaller), not with arrays of the same length. This is why you get an endless recursion, which shows up as a StackOverflowError.

answered May 21, 2011 at 18:43

Paŭlo Ebermann

75k20 gold badges150 silver badges217 bronze badges

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

2 Comments

Piotr Over a year ago

i should've used an ArrayList! resizing the less and more arrays is awkward and expansive... unless you have any suggestions?

Paŭlo Ebermann Over a year ago

You could use an additional parameter to the recursive function which says which interval of the array is to be handled. (Then your temporary arrays for the next call need only be maximally this size.)

Hovercraft Full Of Eels · Accepted Answer · 2011-05-21 18:45:52Z

0

I wonder if you're recursing forever. Where do you shrink the array size within your quicksort method? Have you used println's on the array size to debut to see if it's getting smaller?

answered May 21, 2011 at 18:45

Hovercraft Full Of Eels

286k25 gold badges267 silver badges391 bronze badges

1 Comment

Hovercraft Full Of Eels Over a year ago

I'm a bit slow it seems... 1+ to Paulo for beating me to the punch! :)

Collectives™ on Stack Overflow

Stack Overflow in Java QuickSort on Array

2 Answers 2

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related