Java sorting with quicksort algorithm

Question

I'm trying to code a quicksort program in java.here is my partition function

int partition(int[] array, int start, int end) 
{
    int last = end - 1;
    int first = start;
    int pivot = array[start];
    while (first < last)
    {
        while (first < last && pivot <= array[last])
            last = last - 1;
        array[first] = array[last];
        while (first < last && pivot > array[first])
            first = first + 1;
        array[last] = array[first];
    }
    array[first] = pivot;
    return first;
}

and that is my quicksort function

void quickSort(int array[], int start, int end) {
      int index = partition(array, start, end);
      if (start < index - 1)
            quickSort(array, start, end - 1);
      if (index < end)
            quickSort(array, index, end);}

But when I test the code in Junit it gives me error. I need to change quickSort or partition function. What can I do with that.

stack overflow error on line "quickSort(array, index, end);" — JayGatsby
– JayGatsby, Commented Nov 5, 2013 at 10:54
Interesting how you lost interest in updating your question with other vital information like how you call the method..(the contents of the array are relevant to your error and debugging it), and you lost interest, because now the deadline past you don't care anymore. I downvoted you 'cos you didn't even think to include a print statement, or show the other information. But since you lost interest in updating your question once the deadline passed, i'll tell you that if I could downvote you again, I would. — barlop
– barlop, Commented Nov 5, 2013 at 20:22
anybody showing a different algorithm for the purpose of answering the exercise given, is perhaps showing a clear misunderstanding of the objective of the exercise this person has been given. Obviously anybody can pull a quicksort algorithm off the internet, his lecturer knows that. The point is to find out why the particularly designed quicksort he was given fails, and to fix that. — barlop
– barlop, Commented Nov 5, 2013 at 20:30

Artem Moskalev · Accepted Answer · 2013-11-05 11:26:03Z

1

Here:

 if (start < index - 1)
                quickSort(array, start, end - 1);

Why do you call quickSort for lower partition from start, to end-1? Shouldnt it be:

  if (start < index - 1)
                    quickSort(array, start, index - 1);

And the upper part is from index+1 to end.

Moreover, it is better to check the limits like this before the partitioning and remove your if statements:

 if (end <= start) { return; }

edited Nov 5, 2013 at 11:26

answered Nov 5, 2013 at 10:43

Artem Moskalev

5,84811 gold badges39 silver badges55 bronze badges

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

11 Comments

JayGatsby Over a year ago

I changed these lines but still gives error on line ` quickSort(array, index, end); ` stack overflow error it says

Artem Moskalev Over a year ago

Did you check the if statement before the partitioning? remove those if statements before recursive calls.

Artem Moskalev Over a year ago

You should use quickSort(array, index+1, end) in 2nd statement. Have you changed the lower part? What kind of error does it give?

barlop Over a year ago

@user2955896 seriously man, can't you do print to console (sometihing like system.out.println) the index, the start, and the end, and then you will be able to see what is going on. It's call debugging. It's just basic intelligence to know that if you have a problem you TRY TO FIND IT. Ever heard of debugging. i'm downvoting your question. It's utterly absurd that you have not tried to debug or asked how.. Do you even know the meaning of the word I wonder.

JayGatsby Over a year ago

my mind has blown.can you explain it more clearly or write the code directly :( I'm beginner for java

|

Steve P. · Accepted Answer · 2013-11-05 11:18:52Z

0

To me, it just seems much less intuitive to write the functions like those above. Take this sample code that I just wrote (and tested) as an example, and see if you can understand it and use it to help you through your code. NB: This is slightly different than yours in that it picks a pivot at random.

void quicksort(int[] nums)
{
    if (nums.length > 1)
    {
          quicksort(nums, 0, nums.length);
    }
}

//[left,right)
private void quicksort(int[] nums, int left, int right)
{   
    if (left < right - 1)
    {
        int position = left;
        int pivot = pickPivot(left, right);

        if (pivot != right - 1)
            swap(nums, pivot, right-1);

        for (int i = left; i < right - 1; i++)
        {
            if (nums[i] <= nums[right-1])
            {
                swap(nums, position, i);
                position++;
            }
        }

        swap(nums, position, right-1);
        quicksort(nums, left, position);
        quicksort(nums, position + 1, right);
    }
}

//[left,right)
private int pickPivot(int left, int right)
{
     return rand.nextInt(right-left) + left; // rand is a Random object
}

private void swap(int[] nums, int start, int end)
{
    int temp = nums[end];
    nums[end] = nums[start];
    nums[start] = temp;
}

As others have said, it can be difficult to debug recursive functions. If you can't figure it out from here, I suggest using a debugger. Eclipse's debugger is pretty easy to use and very helpful. This may be frustrating and difficult to figure out, but the process is one that every programmer (should and) has to go through.

Once you think you have it figured out, use a testing function similar to this one to test it out (I would initially start off with a smaller size in case there are errors, this way it will be easier to debug):

void testQuickSort()
{
    for(int i = 0; i < 1000; i++)
    {
        int size = rand.nextInt(100)+1;
        int[] nums = new int[size];

        for (int j = 0; j < size; j++)
        {
            nums[j] = rand.nextInt(10);

            if (rand.nextBoolean())
            {
                nums[j] *= -1;
            }
        }

        quicksort(nums);
        assert sorted(nums) == true;
    }
}  

private boolean sorted(int[] array)
{
    for (int i = 0; i < array.length-1; i++)
    {
        if (array[i] > array[i+1])
            return false;
    }

    return true;
}

edited Nov 5, 2013 at 11:18

answered Nov 5, 2013 at 11:13

Steve P.

14.7k9 gold badges46 silver badges74 bronze badges

6 Comments

JayGatsby Over a year ago

thanks for your answer.but i can only use two functions(partition and quicksort) and the pivot is the first element of the array.I'm trying to understand your code right now :)

Steve P. Over a year ago

@user2955896 I wasn't trying to give you exactly what you want. I know what's wrong with your code and what your restrictions are. Not trying to be a jerk or anything, but you should try to work this out. Trust me, it will be to your benefit in the long run.

JayGatsby Over a year ago

Steve I agree with you, you are so right but I'm looking for a Greg right now

Steve P. Over a year ago

@user2955896 As in GGG? I think that's what I'm being. Sorry. :) Good luck! Hope you figure it out.

JayGatsby Over a year ago

2 hours left for deadline can you just give the exact code for once.I promise I will work hard in the long run :(

|

StanislavL · Accepted Answer · 2013-11-05 11:25:11Z

0

stack overflow error on line "quickSort(array, index, end);

When array is big enough recusion call too many times the same function overflowing stack.

Instead of recursion place pairs of indexes in a stack and call the quickSort() for top pair.

void quickSort(int array[], int start, int end) {
  int index = partition(array, start, end);
  if (start < index - 1)
//        quickSort(array, start, end - 1);
        push(start, end - 1);
  if (index < end)
//        quickSort(array, index, end);}
        push(index, end);

while(stack is not empty) {
    //get next pair and call quickSort
}

answered Nov 5, 2013 at 11:25

StanislavL

57.5k9 gold badges75 silver badges100 bronze badges

1 Comment

barlop Over a year ago

I think you can get a stack overflow / buffer overflow, if the base case of the recursive procedure never gets reached. So he just kept hitting the recursive case until the stack overflowed. I doubt he had a giant array so big it broke his method. And i'm sure his lecturer doesn't want people to change the design of his algorithm, rather to fix it given its design. Otherwise anybody could comment out bit sof his algorithm and replace it with something found online! The objective in an algorithms course is to test if you really understand well, the algorithm the lecturer has given.

Collectives™ on Stack Overflow

Java sorting with quicksort algorithm

3 Answers 3

11 Comments

6 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

11 Comments

6 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related