Advertisement
ruhul0

Quick Sort- Algorithm

Jun 13th, 2016
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.14 KB | None | 0 0
  1. #include <stdio.h>
  2. #include<stdlib.h>
  3. #include<time.h>
  4. #define size 20000
  5. void quickSort( int[], int, int);
  6. int partition( int[], int, int);
  7. int a[size];
  8. int main()
  9. {
  10.     int i;
  11.     clock_t begin,end;
  12.     double time_spent;
  13.     for(i=0;i<size;i++)
  14.     {
  15.         a[i]=rand()%100;
  16.     }
  17.     begin=clock();
  18.     quickSort( a, 0,size-1);
  19.     end=clock();
  20.     printf("\n\nSorted array is:  ");
  21.     time_spent=(double)(end-begin)/CLOCKS_PER_SEC;
  22.     printf("\nSorted array:\n");
  23.     for(i=0;i<size;i++)
  24.     {
  25.         printf("%d ",a[i]);
  26.     }
  27.     printf("\nTime Elapsed:%f\n",time_spent);
  28.  
  29. }
  30. void quickSort( int a[], int front, int rear)
  31. {
  32.    int j;
  33.  
  34.    if( front < rear )
  35.    {
  36.        j = partition( a, front, rear);
  37.        quickSort( a, front, j-1);
  38.        quickSort( a, j+1, rear);
  39.    }
  40.  
  41. }
  42.  
  43.  
  44.  
  45. int partition( int a[], int front, int rear) {
  46.    int x, i, j, temp;
  47.    x = a[front];
  48.    i = front; j = rear+1;
  49.  
  50.    while( 1)
  51.    {
  52.     do ++i;
  53.     while( a[i] <= x && i <= rear );
  54.     do --j;
  55.     while( a[j] > x );
  56.     if( i >= j )
  57.         break;
  58.     temp = a[i];
  59.     a[i] = a[j];
  60.     a[j] = temp;
  61.    }
  62.    temp = a[front];
  63.    a[front] = a[j];
  64.    a[j] = temp;
  65.    return j;
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement