Results 1 to 3 of 3
  1. #1
    patishi is offline Member
    Join Date
    Feb 2013
    Posts
    4
    Rep Power
    0

    Default A recursion issue with quickSort algorithm

    Hi. I implemented the QuickSort algorithm myself in a very innoccent and uneffiecient way,but i am doing this for learning and practicing. by the way,i know how this should by rightly implemented ,but i still want to try and make it my way which seems logic.
    after debugging this,it all seems to work just fine, but the problem is that when i want to print the new ordered list (see the main method) it just prints me the original unsorted one. the partition function is coming back to where is started from because of the recursion. how can i make it "save" all the steps? and return the ordered list?
    thx!

    this is the code:
    Java Code:
    public class MyQuickSort {
    	
    	public static int list[] = {6,5,3,1,8,7,2,4};
    	
    	public static boolean sorted = false;
    	
    	public static int[] addNumberToArray(int arr[],int num){
    		int newArr[] = new int[arr.length+1];
    		for(int i = 0;i<arr.length;i++){
    			newArr[i] = arr[i];
    		}
    		newArr[newArr.length-1] = num;
    		arr = newArr;
    		return arr;
    		
    	}
    	
    	
    	public static int[] partition(int arr[]){
    		
    		while(!sorted){
    			int pivotIndex = (int)(arr.length/2);
    			int left[] = new int[0];
    			int right[] = new int[0];
    		
    			for(int i = 0;i<arr.length;i++){
    				if(i==pivotIndex){
    					continue;
    				}
    				else if(arr[i]<=arr[pivotIndex]){
    					left = addNumberToArray(left,arr[i]);
    				}
    				else{
    					right = addNumberToArray(right,arr[i]);
    				}
    			}
    			int origPivot = arr[pivotIndex];
    			int k = 0;
    			while(k<left.length){
    				arr[k] = left[k];
    				k++;
    			}
    			arr[k] = origPivot;
    			k++;
    			while(k<arr.length){
    				arr[k] = right[arr.length-arr.length-(left.length+1)+k];
    				k++;
    			}
    			if(left.length>1){
    				partition(left);
    			}
    			if(right.length>1){
    				partition(right);
    			}
    			if(left.length<=1&&right.length<=1){
    				sorted = true;
    			}
    		}
    			return arr;
    
    	}
    
    
    
    	public static void main(String[] args) {
    		list = partition(list);
    		for(int i = 0;i<list.length;i++){
    			System.out.print(list[i]+" ");
    		}
    	
    
    	}
    
    }
    Last edited by JosAH; 02-12-2013 at 06:47 AM. Reason: added [code] ... [/code] tags

  2. #2
    patishi is offline Member
    Join Date
    Feb 2013
    Posts
    4
    Rep Power
    0

    Default Re: A recursion issue with quickSort algorithm

    and one more thing..why is my code look like this when i post? originally it is with Indentations

  3. #3
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,457
    Blog Entries
    7
    Rep Power
    20

    Default Re: A recursion issue with quickSort algorithm

    Quote Originally Posted by patishi View Post
    and one more thing..why is my code look like this when i post? originally it is with Indentations
    You have to put your code between [code] ... [/code] tags; I did it for you this time.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. Algorithm's execution time evaluation issue
    By EngineerVic in forum New To Java
    Replies: 7
    Last Post: 12-14-2012, 04:55 PM
  2. How to limit threads in a Java QuickSort algorithm.
    By roise_r in forum Threads and Synchronization
    Replies: 6
    Last Post: 06-02-2011, 07:53 PM
  3. Boggled by this, Fast QuickSort Algorithm
    By gcampton in forum New To Java
    Replies: 0
    Last Post: 12-08-2009, 03:07 PM
  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
  •