ex11-1.c

/* code: ex11-1.c   (v1.20.00) */
#include <stdio.h>
#include <stdlib.h>

/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;
  printf ("array: ");
  for (i = 0; i < n; i++) {
    printf ("%d ", v[i]);
  }
  printf ("\n");
}

/* ------------------------------------------ */
int partition (int v[], int lower_bound, int upper_bound) {
  int a, down, up, temp;

  a = v[lower_bound];
  up = upper_bound;
  down = lower_bound;

  while (down < up) {
    while ((v[down] <= a) && (down < upper_bound)) {
      down++;
    }
    while (v[up] > a) {
      up--;
    }
    if (down < up) {
      temp = v[down];
      v[down] = v[up];
      v[up] = temp;
    }
  }
  v[lower_bound] = v[up];
  v[up] = a;
  return up;
}

/* ------------------------------------------ */
void quicksort (int v[], int left, int right) {
  int p;
  if (left >= right) {
    return;
  }
  p = partition (v, left, right);
  quicksort (v, left, p - 1);
  quicksort (v, p + 1, right);
}

/* ------------------------------------------ */
int main () {
  int array[10]
  = { 80, 40, 30, 20, 10, 00, 70, 90, 50, 60 };

  print_array (array, 10);
  quicksort (array, 0, 9);
  print_array (array, 10);

  return 0;
}

ex11-2.c

/* code: ex11-2.c   (v1.20.00) */
#include <stdio.h>
#include <stdlib.h>
#define MAX 10

/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;
  printf ("array: ");
  for (i = 0; i < n; i++) {
    printf ("%4d ", v[i]);
  }
  printf ("\n");
}

/* ------------------------------------------ */
void radix_sort (int a[], int n) {
  int i, max, exp;
  int temp[MAX];
  int bucket[10];

  max = 0;
  exp = 1;
  for (i = 0; i < n; i++) {
    if (a[i] > max) {
      max = a[i];
    }
  }
  while (max / exp > 0) {
    for (i = 0; i < 10; i++) {
      bucket[i] = 0;
    }
    for (i = 0; i < n; i++) {
      bucket[a[i] / exp % 10]++;
    }
    for (i = 1; i < 10; i++) {
      bucket[i] += bucket[i - 1];
    }
    for (i = n - 1; i >= 0; i--) {
      temp[--bucket[a[i] / exp % 10]] = a[i];
    }
    for (i = 0; i < n; i++) {
      a[i] = temp[i];
    }
    exp *= 10;
    print_array (a, n);
  }
}

/* ------------------------------------------ */
int main () {
  int array[MAX]
  = { 12, 19, 10, 28, 30, 01, 502, 16, 34, 177 };

  print_array (array, 10);
  radix_sort (array, 10);
  print_array (array, 10);

  return 0;
}

q11-1.c

/* code: q11-1.c   (v1.20.00) */
#include <stdio.h>
#include <stdlib.h>

/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;
  printf ("array: ");
  for (i = 0; i < n; i++) {
    printf ("%d ", v[i]);
  }
  printf ("\n");
}

/* ------------------------------------------ */
int partition (int v[], int lower_bound, int upper_bound) {
  int a, down, up, temp;

  a = v[lower_bound];
  up = upper_bound;
  down = lower_bound;

  while (down < up) {
    while ((v[down] <= a) && (down < upper_bound)) {
      down++;
    }
    while (v[up] > a) {
      up--;
    }
    if (down < up) {
      temp = v[down];
      v[down] = v[up];
      v[up] = temp;
    }
  }
  v[lower_bound] = v[up];
  v[up] = a;
  return up;
}

/* ------------------------------------------ */
void quicksort (int v[], int left, int right, int level) {
  int p;
  int i;
  if (left >= right) {
    return;
  }
  level++;
  p = partition (v, left, right);
  quicksort (v, left, p - 1, level);
  quicksort (v, p + 1, right, level);
  for (i = 0; i < level; i++) {
    printf ("*");
  }
  printf ("[pivot:%d left:%d right:%d]\n", p, left, right);
}

/* ------------------------------------------ */
int main () {
  int array[10]
  = { 30, 40, 80, 20, 10, 00, 70, 90, 50, 60 };

  print_array (array, 10);
  quicksort (array, 0, 9, 0);
  print_array (array, 10);

  return 0;
}

q11-2.c

/* code: q11-2.c   (v1.20.00) */
#include <stdio.h>
#include <stdlib.h>
#define STACK_SIZE 2048

/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;
  printf ("\n");
  for (i = 0; i < n; i++) {
    printf ("%02d ", v[i]);
  }
}

/* ------------------------------------------ */
int partition (int v[], int lower_bound, int upper_bound) {
  int a, down, up, temp;

  a = v[lower_bound];
  up = upper_bound;
  down = lower_bound;

  while (down < up) {
    while ((v[down] <= a) && (down < upper_bound)) {
      down++;
    }
    while (v[up] > a) {
      up--;
    }
    if (down < up) {
      temp = v[down];
      v[down] = v[up];
      v[up] = temp;
    }
  }
  v[lower_bound] = v[up];
  v[up] = a;
  return up;
}

/* ------------------------------------------ */
void quicksort_stack (int v[], int n) {
  int left, right, i, sptr;
  int stack_lower_bound[STACK_SIZE];
  int stack_upper_bound[STACK_SIZE];

  stack_lower_bound[0] = 0;
  stack_upper_bound[0] = n - 1;
  sptr = 1;

  while (sptr > 0) {
    sptr--;
    left = stack_lower_bound[sptr];
    right = stack_upper_bound[sptr];

    if (left >= right) {
      ;
    }
    else {
      i = partition (v, left, right);

      if ((i - left) < (right - i)) {
	stack_lower_bound[sptr] = i + 1;
	stack_upper_bound[sptr++] = right;
	stack_lower_bound[sptr] = left;
	stack_upper_bound[sptr++] = i - 1;
      }
      else {
	stack_lower_bound[sptr] = left;
	stack_upper_bound[sptr++] = i - 1;
	stack_lower_bound[sptr] = i + 1;
	stack_upper_bound[sptr++] = right;
      }
    }
  }
}


/* ------------------------------------------ */
int main () {
  int array[10]
  = { 80, 40, 30, 20, 10, 00, 70, 90, 50, 60 };

  print_array (array, 10);
  quicksort_stack (array, 10);
  print_array (array, 10);

  return 0;
}

q11-3.c

/* code: q11-3.c   (v1.20.00) */
#include <stdio.h>
#include <stdlib.h>

#define MAX 100000000

/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;
  printf ("array: ");
  for (i = 0; i < n; i++) {
    printf ("%8d ", v[i]);
  }
  printf ("\n");
}

/* ------------------------------------------ */
void rand_data (int v[], int n) {
  int i;
  for (i = 0; i < n; i++) {
    v[i] = rand () % (MAX / 10);
  }
}

/* ------------------------------------------ */
int partition (int v[], int lower_bound, int upper_bound) {
  int a, down, up, temp;

  a = v[lower_bound];
  up = upper_bound;
  down = lower_bound;

  while (down < up) {
    while ((v[down] <= a) && (down < upper_bound)) {
      down++;
    }
    while (v[up] > a) {
      up--;
    }
    if (down < up) {
      temp = v[down];
      v[down] = v[up];
      v[up] = temp;
    }
  }
  v[lower_bound] = v[up];
  v[up] = a;
  return up;
}

/* ------------------------------------------ */
void quicksort (int v[], int left, int right) {
  int p;
  if (left >= right) {
    return;
  }
  p = partition (v, left, right);
  quicksort (v, left, p - 1);
  quicksort (v, p + 1, right);
}

/* ------------------------------------------ */
int main (int argc, char **argv) {
  int *array;

  array = malloc (sizeof (int) * MAX);
  if (array == NULL) {
    printf ("ERROR: Can not allocate memory\n");
    exit (-1);
  }

  rand_data (array, MAX);
  printf ("array size: %d\n", MAX);
  fflush (stdout);

  print_array (array, 30);

  quicksort (array, 0, MAX - 1);

  print_array (array, 30);

  free (array);
  return 0;
}

q11-4.c

/* code: q11-4.c   (v1.20.00) */
#include <stdio.h>
#include <stdlib.h>

/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;
  printf ("\n");
  for (i = 0; i < n; i++) {
    printf ("%d ", v[i]);
  }
}

/* ------------------------------------------ */
void merge_sort (int v[], int lb, int ub, int v_temp[]) {
  int i, j, k, c;

  if (lb >= ub) {
    return;
  }
  c = (lb + ub) / 2;

  merge_sort (v, lb, c, v_temp);
  merge_sort (v, c + 1, ub, v_temp);

  for (i = lb; i <= c; i++) {
    v_temp[i] = v[i];
  }
  for (i = c + 1, j = ub; i <= ub; i++, j--) {
    v_temp[i] = v[j];
  }

  i = lb;
  j = ub;

  for (k = lb; k <= ub; k++) {
    if (v_temp[i] <= v_temp[j]) {
      v[k] = v_temp[i++];
    }
    else {
      v[k] = v_temp[j--];
    }
  }
}

/* ------------------------------------------ */
int main () {
  int array[10] = { 8, 4, 3, 2, 1, 0, 7, 9, 5, 6 };
  int array_temp[10];

  print_array (array, 10);
  merge_sort (array, 0, 9, array_temp);
  print_array (array, 10);

  return 0;
}