ruhul0

Quick Sort- Algorithm

Jun 13th, 2016
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.15 KB | None | 0 0
  1. #include <stdio.h>
  2. #include<stdlib.h>
  3. #include<time.h>
  4. #define size 20000
  5. int a[size];
  6. void quickSort( int[], int, int);
  7. int partition( int[], int, int);
  8. void 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. int partition( int a[], int front, int rear) {
  43.    int x, i, j, temp;
  44.    x = a[front];
  45.    i = front; j = rear+1;
  46.  
  47.    while( 1)
  48.    {
  49.     do ++i;
  50.     while( a[i] <= x && i <= rear );
  51.     do --j;
  52.     while( a[j] > x );
  53.     if( i >= j )
  54.         break;
  55.     temp = a[i];
  56.     a[i] = a[j];
  57.     a[j] = temp;
  58.    }
  59.    temp = a[front];
  60.    a[front] = a[j];
  61.    a[j] = temp;
  62.    return j;
  63. }
Advertisement
Add Comment
Please, Sign In to add comment