/*By Vamei*/
/*swap the neighbors if out of order*/
void bubble_sort(int a[], int ac)
{
  /*use swap*/
  int i,j;
  int sign;
  for (j = 0; j < ac-1; j++) {
    sign = 0;
    for(i = ac-1; i > j; i--)
    {
      if(a[i-1] > a[i]) {
        sign = 1;
        swap(a+i, a+i-1);
      }
    }
    if (sign == 0) break;
  }
}

/*By Vamei*/
/*insert the next element 
 into the sorted part*/
void insert_sort(int a[], int ac)
{
  /*use swap*/
  int i,j;  
  for (j=1; j < ac; j++) 
  {
    i = j-1;
    while((i>=0) && (a[i+1] < a[i])) 
    {
      swap(a+i+1, a+i);
      i--;
    }
  }
}

/*By Vamei*/
/*find the smallest of the rest,
 then append to the sorted part*/
void select_sort(int a[], int ac) 
{
  /*use swap*/
  int i,j;
  int min_idx;
  for (j = 0; j < ac-1; j++) 
  {
    min_idx = j;
    for (i = j+1; i < ac; i++) 
    {
      if (a[i] < a[min_idx]) 
      {
        min_idx = i;
      }
    }
    swap(a+j, a+min_idx);
  }  
}

/*By Vamei*/
/*quickly sort the turtles at the tail of the array*/
void shell_sort(int a[], int ac)
{
  int step;
  int i,j;
  int nsub;
  int *sub;

  /* initialize step */
  step = 1;
  while(step < ac) step = 3*step + 1;

  /* when step becomes 1, it's equivalent to the bubble sort*/
  while(step > 1) {
    /* step will go down to 1 at most */
    step = step/3 + 1;
    for(i=0; i<step; i++) {
      /* pick an element every step, 
       and combine into a sub-array */
      nsub = (ac - i - 1)/step + 1;      
      sub = (int *) malloc(sizeof(int)*nsub);
      for(j=0; j<nsub; j++) {
        sub[j] = a[i+j*step]; 
      }
      /* sort the sub-array by bubble sorting. 
       It could be other sorting methods */
      bubble_sort(sub, nsub);
      /* put back the sub-array*/
      for(j=0; j<nsub; j++) {
        a[i+j*step] = sub[j];
      }
      /* free sub-array */
      free(sub);
    }  
  }
}

/*By Vamei*/
/*recursively merge two sorted arrays*/
void merge_sort(int *a, int ac)
{
  int i, j, k;  
  int ac1, ac2;
  int *ah1, *ah2;
  int *container;

  /*base case*/  
  if (ac <= 1) return;

  /*split the array into two*/
  ac1 = ac/2;
  ac2 = ac - ac1;
  ah1 = a + 0;
  ah2 = a + ac1;

  /*recursion*/
  merge_sort(ah1, ac1);
  merge_sort(ah2, ac2);
 
  /*merge*/
  i = 0;
  j = 0;
  k = 0;
  container = (int *) malloc(sizeof(int)*ac);
  while(i<ac1 && j<ac2) {
    if (ah1[i] <= ah2[j]) {
      container[k++] = ah1[i++];
    } 
    else {
      container[k++] = ah2[j++];
    }
  }
  while (i < ac1) {
    container[k++] = ah1[i++];
  }
  while (j < ac2) {
    container[k++] = ah2[j++];
  }

  /*copy back the sorted array*/
  for(i=0; i<ac; i++) {
    a[i] = container[i];
  }
  /*free space*/
  free(container);
}

/*By Vamei*/
/*select pivot, put elements (<= pivot) to the left*/
void quick_sort(int a[], int ac)
{
  /*use swap*/

  /* pivot is a position, 
    all the elements before pivot is smaller or equal to pvalue */
  int pivot;
  /* the position of the element to be tested against pivot */
  int sample;

  /* select a pvalue. 
    Median is supposed to be a good choice, but that will itself take time.
    here, the pvalue is selected in a very simple wayi: a[ac/2] */
  /* store pvalue at a[0] */
  swap(a+0, a+ac/2);
  pivot = 1; 

  /* test each element */
  for (sample=1; sample<ac; sample++) {
    if (a[sample] < a[0]) {
      swap(a+pivot, a+sample);
      pivot++;
    }
  }
  /* swap an element (which <= pvalue) with a[0] */
  swap(a+0,a+pivot-1);

  /* base case, if only two elements are in the array,
    the above pass has already sorted the array */
  if (ac<=2) return;
  else {
    /* recursion */
    quick_sort(a, pivot);
    quick_sort(a+pivot, ac-pivot);
  }
}

/* By Vamei 
  Use an big array to implement heap
  DECLARE: int heap[MAXSIZE] in calling function
  heap[0] : total nodes in the heap
  for a node i, its children are i*2 and i*2+1 (if exists)
  its parent is i/2 */

void insert(int new, int heap[]) 
{
  int childIdx, parentIdx;
  heap[0] = heap[0] + 1;
  heap[heap[0]] = new;
  
  /* recover heap property */
  percolate_up(heap);
}

static void percolate_up(int heap[]) {
  int lightIdx, parentIdx;
  lightIdx = heap[0];
  parentIdx = lightIdx/2;
  /* lightIdx is root? && swap? */
  while((parentIdx > 0) && (heap[lightIdx] < heap[parentIdx])) {
    /* swap */
    swap(heap + lightIdx, heap + parentIdx); 
    lightIdx = parentIdx;
    parentIdx = lightIdx/2;
  }
}


int delete_min(int heap[]) 
{
  int min;
  if (heap[0] < 1) {
    /* delete element from an empty heap */
    printf("Error: delete_min from an empty heap.");
    exit(1);
  }

  /* delete root 
    move the last leaf to the root */
  min = heap[1];
  swap(heap + 1, heap + heap[0]);
  heap[0] -= 1;

  /* recover heap property */
  percolate_down(heap);
 
  return min;
}

static void percolate_down(int heap[]) {
  int heavyIdx;
  int childIdx1, childIdx2, minIdx;
  int sign; /* state variable, 1: swap; 0: no swap */

  heavyIdx = 1;
  do {
    sign   = 0;
    childIdx1 = heavyIdx*2;
    childIdx2 = childIdx1 + 1;
    if (childIdx1 > heap[0]) {
      /* both children are null */
      break; 
    }
    else if (childIdx2 > heap[0]) {
      /* right children is null */
      minIdx = childIdx1;
    }
    else {
      minIdx = (heap[childIdx1] < heap[childIdx2]) ?
             childIdx1 : childIdx2;
    }

    if (heap[heavyIdx] > heap[minIdx]) {
      /* swap with child */
      swap(heap + heavyIdx, heap + minIdx);
      heavyIdx = minIdx;
      sign = 1;
    }
  } while(sign == 1);
}

/* By Vamei */
/* exchange the values pointed by pa and pb*/
void swap(int *pa, int *pb)
{
  int tmp;
  tmp = *pa;
  *pa = *pb;
  *pb = tmp;
}