leomaster

quicksort

Jun 19th, 2021
618
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. enum { Q, P };
  2.  
  3. void quickSort( int[], int, int);
  4. int partition( int[], int, int);
  5.  
  6.  
  7. void quickSort( int a[], int l, int r, int F)
  8. {
  9.    int j;
  10.  
  11.    if( l < r )
  12.    {
  13.     // divide and conquer
  14.         j = partition( a, l, r);
  15.        quickSort( a, l, j-1);
  16.        quickSort( a, j+1, r);
  17.    }
  18.    
  19. }
  20.  
  21.  
  22.  
  23. int partition( int a[], int l, int r) {
  24.    int pivot, i, j, t;
  25.    pivot = a[l];
  26.    i = l; j = r+1;
  27.        
  28.    while( 1)
  29.    {
  30.     do ++i; while( a[i] <= pivot && i <= r );
  31.     do --j; while( a[j] > pivot );
  32.     if( i >= j ) break;
  33.     t = a[i]; a[i] = a[j]; a[j] = t;
  34.    }
  35.    t = a[l]; a[l] = a[j]; a[j] = t;
  36.    return j;
  37. }
  38.  
  39. void main()
  40. {
  41.     int a[] = { 7, 12, 1, -2, 0, 15, 4, 11, 9};
  42.  
  43.     int i;
  44.     printf("\n\nUnsorted array is:  ");
  45.     for(i = 0; i < 9; ++i)
  46.         printf(" %d ", a[i]);
  47.  
  48.     quickSort( a, 0, 8);
  49.  
  50.     printf("\n\nSorted array is:  ");
  51.     for(i = 0; i < 9; ++i)
  52.         printf(" %d ", a[i]);
  53.  
  54. }
  55.  
RAW Paste Data