Advertisement
Guest User

quicksort problem

a guest
Dec 8th, 2016
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.89 KB | None | 0 0
  1. #include <stdio.h>
  2.  
  3. void quickSort(int a[], int l, int r){
  4.     int k = partition(a, l, r);
  5.     if(r <= l){
  6.         return;
  7.     }
  8.     quickSort(a, l, k-1);
  9.     quickSort(a, k+1, r);
  10. }
  11.  
  12. int partition(int a[], int l, int r){
  13.     int i,j,k,v;
  14.     k = r;
  15.     v = a[k];
  16.     i = l;
  17.     j = r-1;
  18.     int hold = -1;
  19.    
  20.     while(1){
  21.         while(i < r && a[i] <= v){
  22.             i++;
  23.         }
  24.         while(j >= l && a[j] >= v){
  25.             j--;
  26.         }
  27.         if(i >= j){
  28.             break;
  29.         }else{
  30.             hold = a[i];
  31.             a[i] = a[j];
  32.             a[j] = hold;
  33.         }
  34.     }
  35.     hold = a[k];
  36.     a[k] = a[i];
  37.     a[i] = hold;
  38. //    
  39. //    printf("\n\n\n\n");
  40. //    
  41. //    for(int u = 0; u < 20; u++){
  42. //        printf("%d\n", a[u]);
  43. //    }
  44.    
  45.     printf("\n\n\n k: %d \n\n\n", i);
  46.    
  47.     return i;
  48. }
  49.  
  50. int main(){
  51.     //array that has to be sorted
  52.     int a[20];
  53.    
  54.     //filling the array with random numbers between 0 and 100 without doubling
  55.     for(int i = 0; i < 20; i++){
  56.         int z;
  57.         while(1){
  58.             z = rand();
  59.             int boolean = 0;
  60.             if(z < 0){
  61.                 z = (-1) * z;
  62.             }
  63.             if(z > 200){
  64.                 boolean = 1;
  65.             }
  66.             for(int j = 0; j <= i; j++){
  67.                 if(a[j] == z){
  68.                     boolean = 1;
  69.                 }
  70.             }
  71.             if(boolean == 0){
  72.                 break;
  73.             }
  74.         }
  75.         a[i] = z;
  76.     }
  77.    
  78.    
  79.    
  80.     //printing out the array to be able to check later
  81.     for(int j = 0; j < 20; j++){
  82.         printf("%d\n", a[j]);
  83.     }
  84.     printf("\nsorted array now:\n\n");
  85.    
  86.     //call quickSort
  87.     quickSort(a, 0, 19);
  88.    
  89.      printf("\n\n\n");
  90.    
  91.     //printing out sorted array
  92.     for(int j = 0; j < 20; j++){
  93.         printf("%d\n", a[j]);
  94.     }
  95.    
  96.     return 0;
  97. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement