Quick sort code

[swissknife007]

void quick(int a[],int m,int n)
{
     int k,key,i,j;
     if(m < n)
     {      
            k=(m+n)/2;
            swap(a[m],a[k]);
            key=a[m];
            i=m+1;
            j=n;
            while(i<=j)
            {
                      while((i<=n)&&(a[i]<=key))
                      i++;
                      while((j>=m)&&(a[i]>key))
                      j--;
                      if(i<j)
                      swap(a[i],a[j]);
                      
                      
            }
            swap(a[m],a[j]);
            quick(a,m,j-1);
            quick(a,j+1,n);
     }
}

I am getting a segmentation problem in swap(a[m].a[k]);
Please explain.

[Narue]

I am getting a segmentation problem in swap(a[m].a[k]);
Please explain.

The simplest form of debugging is debug messages:

k=(m+n)/2;
printf("m:[%d] n:[%d]\n", m, n);
swap(a[m],a[k]);

Verify that your indices aren't out of bounds at any point during the algorithm, because that's the most likely cause of segmentation faults in the presence of an array.

[swissknife007]

The simplest form of debugging is debug messages:

k=(m+n)/2;
printf("m:[%d] n:[%d]\n", m, n);
swap(a[m],a[k]);

Verify that your indices aren't out of bounds at any point during the algorithm, because that's the most likely cause of segmentation faults in the presence of an array.

I did try that
the array was showing the correct bounds
but infinite times.
can't figure out why infinite times?

[Adak]

I have never understood the desire to swap out the pivot/key in Quicksort. It's not necessary.

Your version has no if statement before the recursive calls, to allow it to always choose the smaller sub array. With a recalcitrant data set, you might run out of stack space.

This is the version of Quicksort I like. Two caveats:

1) The index data type has to be a regular (signed) type of int, with unsigned int's it fails when the index briefly goes to a -1 value.

2) The hi that is originally passed to it must be the last valid index. If you pass in an array of 100 numbers, then the last valid index is 99, and you call Quicksort with 0, and 99, not 0 and 100.

If you time it, you'll see it's faster than most other versions of (non-optimized) Quicksort.

void quickSort(int *a, int lo, int hi) {
   int i, j, pivot,temp;
   if(lo == hi) return; 
   i=lo; 
   j=hi;
   pivot= a[(lo+hi)/2]; 

   /* Split the array into two parts */
   do {    
      while (a[i] < pivot) i++; 
      while (a[j] > pivot) j--;
      if (i<=j) { //without the = in there, it's an endless loop
         temp= a[i];
         a[i]= a[j];
         a[j]=temp;
         i++;
         j--;
      }
   }while (i<=j);
    
   if (lo < j) quickSort(a, lo, j);
   if (i < hi) quickSort(a, i, hi);
}