list.c

list.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 "mylib.h"
#include "list.h"

struct listrec {
  int size;
  int length;
  int *items;
};

list list_init(){
  list result = emalloc(sizeof *result);
  result->size = 2;
  result->length = 0;
  result->items = emalloc(result->size * sizeof result->items[0]);
  return result;
}

void list_append(list l, int i){
  if(l->length == l->size){
    l->size += l->size;
  }
  l->items = erealloc(l->items, l->size * sizeof l->items[0]);
  l->items[l->length++] = i;
}

void list_print(list l){
  int i;
  for(i=0; i<l->length; i++){
    printf("%d\n", l->items[i]);
  }
}

void list_sort(list l){
  /*   void *buffer_array = emalloc(l->length * sizeof l->items[0]); */
  quick_sort(l->items, l->length);
  /*    merge_sort(buffer_array, l->items, l->length-1);  */
  /*    free(buffer_array); */
}

void list_delete(list l){
  free(l->items);
}
static void quick_sort(int *a, int n){
  if(n>1){
    int x = a[n/2];
    int i = 0;
    int j = n-1;

    while(1){
      while(a[i]<x) i++;
      while(a[j]>x) j--;
      if(i<j){
         int temp = a[i];
         a[i] = a[j];
         a[j] = temp;
      } else break;
    }
    quick_sort(a, j);
    quick_sort(a+i, n-i);
  }

}
static 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