quick.c

quick.c

contents ::

  quick.c
  quick_sort.s
  atquick_sort.s
  quick_sort.c
  atquick_sort.c

#include <stdio.h>
#include <sys/types.h>
#include <time.h>

//extern void quicksort(int *, int , int );
extern void aquicksort(int *, int , int );
int rand(void);
extern void atquicksort(int *, int, int);
//extern void atquicko(int *, int, int);
void pquicksort(int *a, int lo, int hi);
void tquicksort(int *a, int lo, int hi);

main(){
  clock_t t1, t2;
  int length = 2000;
  //int length = 2048285;

  int a[length];
  int i;

   for(i=0; i<length; i++){
     a[i]=rand();
   }

   t1= clock();
   atquicksort(a,0,length-1);
   t2= clock();

   printf("\nTail Recursion Quick Time: %ld mseconds\tLength: %d\n", (long)(t2-t1)/1000,length);
   // for(i=0; i<length; i++){
   // printf("%d\n",a[i]);
   // }
   /*
     for(i=0; i<length; i++){
     a[i]=rand();
     }

     t1= clock();
     pquicksort(a,0,length-1);
     t2= clock();

     printf("\nPointer Quick Time C: %ld mseconds\tLength: %d\n", (long)(t2-t1)/1000,length);

     //for(i=0; i<length; i++){
     //printf("%d\n",a[i]);
     //}
  */
   for(i=0; i<length; i++){
    a[i]=rand();
  }

  t1= clock();
  aquicksort(a,0,length-1);
  t2= clock();

  printf("\n Quick Time: %ld mseconds\t\tLength: %d\n", (long)(t2-t1)/1000,length);
  //  for(i=0; i<length; i++){
  // printf("%d\n",a[i]);
  // }
/*     for(i=0; i<length; i++){ */
/*      a[i]=rand(); */
/*    } */

/*    t1= clock(); */
/*    atquicko(a,0,length-1); */
/*    t2= clock(); */

/*    printf("\nAss2 Quick Time: %ld mseconds\t\tLength: %d\n", (long)(t2-t1)/1000,length); */

  //   for(i=0; i<length; i++){
  //printf("%d\n",a[i]);
  //}

/*    for(i=0; i<length; i++){ */
/*      a[i]=rand(); */
/*    } */

/*    t1= clock(); */
/*    pquicksort(a,0,length-1); */
/*    t2= clock(); */

/*    printf("\nPointer Quick Time C: %ld mseconds\tLength: %d\n", (long)(t2-t1)/1000,length); */
  return 0;
}

/* Quick sort with pointers updated for tail recursion */
void tquicksort(int *a, int lo, int hi){
  while( hi > lo ) {
    int left, right, median, temp;
    left=lo;
    right=hi;
    median=*(a+((lo+hi)/2));
    while(right >= left){

      while(*(a+left) < median) left++;

      while(*(a+right) > median) right--;
      if(left > right) break;

      temp=*(a+left);
      *(a+left)=*(a+right);
      *(a+right)=temp; //swap

      left++;
      right--;
    }


    tquicksort(a, lo, right);// divide and conquer
    lo=left;
  }
}/*quicksort*/

/*  Quick sort with pointers */
void pquicksort(int *a, int lo, int hi){
  if( hi > lo ) {
    int left, right, median, temp;
    left=lo;
    right=hi;
    median=*(a+((lo+hi)/2));
    while(right >= left){

      while(*(a+left) < median) left++;

      while(*(a+right) > median) right--;
      if(left > right) break;

      temp=*(a+left);
      *(a+left)=*(a+right);
      *(a+right)=temp; //swap

      left++;
      right--;
    }


    pquicksort(a, lo, right);// divide and conquer
    pquicksort(a, left,  hi);
  }
}/*quicksort*/

int rand(){
  static int rand_seed=10;
  rand_seed = rand_seed *1103515245+12345;
  return (unsigned int)(rand_seed / 65536) % 100;
}

James Little