test.c

test.c

contents ::

  list_adt.c
  list.c
  list.h
  mylib.c
  mylib.h
  quick.c
  realloc_1.c
  realloc_2.c
  test.c
  Makefile

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int rand();
int quick_sort(int *a, int n);
void merge_sort(int *newa, int *a, int n);
void pquicksort(int *a, int hi);
void quick(int *a, int n);

int main(){

  clock_t t1, t2;
  int length=20;

  int *a;
  int *b;
  int i;

/*    printf("Size?\n>"); */

/*    scanf("%d", &length); */

  a = malloc(length * sizeof a[0]);
  b = malloc(length * sizeof a[0]);

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

  t1 = clock();
  quick(a,length);
  t2 = clock();

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

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

  printf("\n");

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

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

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

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

  t1 = clock();
  merge_sort(b,a,length-1);
  t2 = clock();

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

  return 0;
}

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

void quick(int *a, int n){
  int i = -1;
  int j = n;
  int x = a[0];
  int temp;

  if(n<2){
    return;
  }

  while(1){
    do i++; while(a[i]<x);
    do j--; while(a[j]>x);

    if(i<j){
      temp = a[i];
      a[i] = a[j];
      a[j] = temp;
    } else
      break;
  }

  quick_sort(a, j+1);
  quick_sort(a+j+1, n-j-1);

}

int quick_sort(int *a, int n){

  if(n>1){
    int i = 0;
    int j = n;
    int x = a[n/2];
    int temp;

    while(1){
      while(a[i]<x) i++;
      while(a[j]>x) j--;

      if(i>j) break;

      temp = a[i];
      a[i] = a[j];
      a[j] = temp;
      i++;
      j--;

    }

    quick_sort(a, j);
    quick_sort(a+i, n-i);
  }
}

/*  Quick sort with pointers */
void pquicksort(int *a, int hi){
  if( hi > 0) {
    int left, right, median, temp;
    left=0;
    right=hi;
    median=*(a+(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, right);// divide and conquer
    pquicksort(a+left,  hi-left);
  }
}/*quicksort*/

void merge_sort(int *newa, int *a, int n){
  int insert=23;
  /*    merge(a, p, q, r);  */

  if(n<=insert){
    /* Insertion sort procedure */
    int guide=0;
    int i;
    int value;
    int j;

    for (i=0; i<=n; i++){
      value = a[i];

      if(a[i]<guide){
         for(j=i-1; j >=0 && a[j] > value; j--){
           a[j+1]=a[j];
         }
         a[j+1]=value;
      }
      if (value>guide) guide=value;
      /* End Insertion Sort procedure */
    }
  }else{
    /* divide */
    int q=n/2;
    int i;
    int s = 0;
    int j = q+1;
    merge_sort(newa,a,q);
    merge_sort(newa,a+q+1,n-q-1);

    /* and conquer */
    for(i=0;s<q+1;i++){
      if( j>n || a[s] <= a[j]) {
         newa[i]=a[s++];
      }else  if(a[s] >a[j]) {
         newa[i]=a[j++];
      }

    }
    while(j<=n){
      newa[i++]=a[j++];
    }
    for(i=0,s=0;i<=n;i++,s++){
      a[s]=newa[i];
    }
    /* End of Merge sort Procedure */
  }
}

James Little