Thread: is my C++ quicksort implementation correct?

  1. #1
    Registered User
    Join Date
    Nov 2010
    Posts
    44

    is my C++ quicksort implementation correct?

    hi can you please tell me if this is correct?

    Code:
    void quickSort(int A[], int left, int right){
        
    	int i = left, j = right, pivot = A[left];
    
    	while(i<=j){
    
    		while(i!=(right + 1) && A[i]<=pivot) i++;
    		while(A[j]>pivot) j--;
    		if(j>i){
    			swap(A[i],A[j]);
    			j--;
    			i++;
    		}
    
    	}
    	swap(A[left],A[j]);
    	if(left<j)
    	quickSort(A,left,j-1);
    	if(right>i)
    	quickSort(A,i,right);
    
    	
    }
    im not sure about this part

    Code:
     while(i!=(right + 1) && A[i]<=pivot) i++;
    i put i!=(right + 1)

    because for input

    3,9,3,8,4

    the i will check values from index = 5, 6 of the array which do not exist at all,

    but i dont need to check the same thing for j since at most the index of j will be the same of the pivot's index
    Last edited by nik; 04-05-2011 at 11:24 AM.

  2. #2
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    With the very first pivot A[0] you get:
    3,3,9,8,4

    after the first iteration so I think the partitioning is correct.

    One thing that you are wrong about though is that you can also stop the loop if this part is false:
    while(i!=(right + 1) && A[i]<=pivot) i++;

    It's a case that happens frequently in your sample array. In order to test the other part of the condition, you should create a test case that is always true for that. Then the only way you'd stop the loop is if i!=(right + 1) is false.

    2,1,-1,-2,0,-3

    Still, I don't see a problem. You'd get -3,1,-1,-2,0,2 after the first iteration.

  3. #3
    Registered User
    Join Date
    Nov 2010
    Posts
    44
    hi whiteflags thanks for your answer

    "One thing that you are wrong about though is that you can also stop the loop if this part is false:
    while(i!=(right + 1) && A[i]<=pivot) i++;
    "
    when you say that it's wrong you mean that I should use an OR instead of AND?

  4. #4
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    You were wrong when you said this:
    the i will check values from index = 5, 6 of the array which do not exist at all,
    The range the while loop will scan is at most i=0 to 4, and it stops when i==5.

    But I went on to explain that you can also stop if A[i]<=pivot is false (That happens), so it isn't as though only i!=(right+1) matters. I created a case test where it didn't matter because it would always be true, thus we are only testing if the loop stops when i==5.

    AND is correct.

    I encourage you to check my work, but I see nothing wrong here.

  5. #5
    Registered User
    Join Date
    Nov 2010
    Posts
    44
    oh now I see, you're right...

    thanks for helping me out

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. problems with quicksort!
    By coni in forum C Programming
    Replies: 3
    Last Post: 10-03-2009, 02:29 AM
  2. Help needed to perform quicksort on list
    By lazyme in forum C++ Programming
    Replies: 8
    Last Post: 05-15-2009, 02:38 AM
  3. Linux for GNU/Linux is not correct?
    By password636 in forum Linux Programming
    Replies: 8
    Last Post: 03-31-2009, 08:30 PM
  4. Scalability problems with Quicksort
    By hbejkosa in forum C++ Programming
    Replies: 3
    Last Post: 12-26-2008, 11:26 PM
  5. Problems with Quicksort and Pointers
    By algatt in forum C Programming
    Replies: 3
    Last Post: 10-10-2007, 04:24 AM