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
    13,368
    Blog Entries
    7
    Rep Power
    20

    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
    cenosillicaphobia: the fear for an empty beer glass

  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
    13,368
    Blog Entries
    7
    Rep Power
    20

    Default Re: Quicksort

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

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. What is the problem (quicksort)?
    By TheElder777 in forum New To Java
    Replies: 1
    Last Post: 10-30-2012, 05: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, 12:09 AM
  4. quicksort program
    By jvasilj1 in forum New To Java
    Replies: 5
    Last Post: 03-03-2009, 03: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
  •