quick.c

quick.c

contents ::

  address.c
  atquick_sort.c
  bits.c
  countspace.c
  ctof.c
  hextoint.c
  hist.c
  indexof.c
  itob.c
  linkage.c
  lzw.c
  maxval.c
  merge.c
  merge_sort.c
  peof.c
  pointer.c
  quick2.c
  quick.c
  quick_sort.c
  reverse.c
  rftoc.c
  rmultiblank.c
  rtabs.c
  squeeze.c
  structoo.c
  syscall.c
  tempfunc.c
  tfc.c
  word.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();
     tquicksort(a,0,length-1);
     t2= clock();

     printf("\nTail Recursion 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();
     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();
  pquicksort(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