c# quicksort algorithm doesnt proceed

Question

I have just worked on implementation of quicksort in c# but then I have faced a such a problem. When I am using my function

static void QS(int[] arr, int left, int right){
        int pivot = left;
        int temp;
        int i = left + 1;
        int j = left + 1;

        do {    
        if (arr [i] < arr [pivot]) {
                temp = arr [j];
                arr [j] = arr [i];
                arr [i] = temp;
                i++;
            }
            else{}
        j++;
        }while(j<=right);

            temp = arr [pivot];
            arr [pivot] = arr [i - 1];
            arr [i - 1] = temp;
}

For an array

int[] arr = { 12, 9, 19, 8, 7, 13, 10, 71, 18, 34, 90, 15, 3 };

I get the results like this: 9, 12, 19, 8, 7, 13, 10, 71, 18, 34, 90, 15, 3. Hours been spent on this I still can't quite understand why index i does not proceed. Maybe there are more problems than I think.

I omitted recursive calls to concentrate on fuction itself. I am using this pseudo-code:

Partiton(A,l,r)  
//[input corresponds to A[l…r]]  
p:=A[l]  
i:=l+1  
  for  
   j=l+1 to r  
    if A[j] < p  
    swap A[j] and A[i]  
    i:=i+1  
swap  A[l] and A[i‐1]

it was declared outside the function to see where index i fails to proceed, but i will remove it make code more clear — Vlad Vv
– Vlad Vv, Commented Mar 5, 2015 at 22:51
For one thing, quicksort is a recursive algorithm, and your code example does not recurse. — phoog
– phoog, Commented Mar 5, 2015 at 22:54
i omited recursive part of code to concentrate on function itself that produces wrong results even after first using — Vlad Vv
– Vlad Vv, Commented Mar 5, 2015 at 23:08

Karim O. · Accepted Answer · 2015-03-05 23:13:08Z

Several things:

Youre missing the comparisons(while loops) within the do while loop that move the index pointers, and the recursive calls that make quicksort actually work. Remember when you swap your values, increment i and decrement j. Second, for the values i and j, dont add 1 to those indexes as they could give you out of bounds errors, I assume you will be calling quicksort like so: quicksort(arr, 0, arr.Length - 1);. Finally, please choose your pivot as the median value as it yields much faster sorting time and results, rather than choosing the first value in the array.

Heres how I would write this:

   quicksort(arr[], begin, end)
   {
       pivot = (begin + end) / 2
       left = begin;
       right = end;
   while (left <= right)
   {
      while (arr[left] < pivot)
      {
          left++;
      }
      while (arr[right] > pivot)
      {
          right--;
      }
      if (left <= right)
      {
          swap(arr, left, right);
          left++;
          right--;
      }
  }
   //do your recursive call logic here
 }

Collectives™ on Stack Overflow

c# quicksort algorithm doesnt proceed

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related