Results 1 to 4 of 4

Thread: Quicksort

  1. #1
    berb12 is offline Member
    Join Date
    Nov 2011
    Posts
    21
    Rep Power
    0

    Default Quicksort

    Here is my quicksort method:
    Java Code:
    private static void myQuickSort(int []arr, int start, int end)
    	{
    		if (start>=end)
    		{
    			return;
    		}
    		else
    		{
    			int i = start-1, j = end+1;	    
    		    int pivot = arr[start + (end-start)/2];
    		    while (i <= j) 
    		    {
    		    	do{
    		    		i++;
    		    	} while(arr[i] < pivot);
    		      
    		        do{
    		    		j--;
    		    	} while(arr[j] > pivot);
    		        
    		        if (i<=j)
    		        {
    		        	int temp = arr[i];
    		    		arr[i] = arr[j];
    		   	   	    arr[j] = temp;
    					i++;
    					j--;
    		        }
    	
    		        if (start < j)
    		        	myQuickSort(arr,start, j);
    		    	if (i < end)
    		     		myQuickSort(arr, i, end);
    		    }
    
    		}
    		   
    	}
    I need to test the runningtime of this on randomly generated integer arrays with size 100, 1000, 10000, 100000, and 1000000 however when i get up to very large numbers I get a stack overflow, which is understandable because of the amount of recursion. What I am wondering is if there is a better way I can implement quicksort to not have this error for large arrays, I assume picking a different pivot(rather than the middle) may help. Thanks.

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,292
    Blog Entries
    7
    Rep Power
    24

    Default Re: Quicksort

    That's why I dislike the quicksort method so much; the pivot selection is critical in this process; the best pivot is the median of the values in the array; finding a median is a nasty process too (google is your friend); if I were you I'd use another sorting method (heap sort?) that doesn't suffer from those recursive steps.

    kind regards,

    Jos
    The only person who got everything done by Friday was Robinson Crusoe.

  3. #3
    berb12 is offline Member
    Join Date
    Nov 2011
    Posts
    21
    Rep Power
    0

    Default Re: Quicksort

    I wish I could but the project is to compare the runtime of heap sort merge sort and quick sort so I need to do quicksort

  4. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,292
    Blog Entries
    7
    Rep Power
    24

    Default Re: Quicksort

    Does increasing the maximum stack size help? (see "java -help")

    kind regards,

    Jos
    The only person who got everything done by Friday was Robinson Crusoe.

Similar Threads

  1. What is the problem (quicksort)?
    By TheElder777 in forum New To Java
    Replies: 1
    Last Post: 10-30-2012, 06:30 PM
  2. Quicksort median
    By louboulos in forum New To Java
    Replies: 6
    Last Post: 05-16-2012, 10:36 PM
  3. problem with quicksort
    By jvasilj1 in forum New To Java
    Replies: 2
    Last Post: 03-05-2009, 01:09 AM
  4. quicksort program
    By jvasilj1 in forum New To Java
    Replies: 5
    Last Post: 03-03-2009, 04:47 AM
  5. Quicksort
    By little_polarbear in forum New To Java
    Replies: 12
    Last Post: 07-12-2008, 09:20 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •