c13-1.c

/* code: c13-1.c   (v1.18.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 ("%02d ", 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;
}

c13-2.c

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

/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;
  printf ("array: ");
  for (i = 0; i < n; i++) {
    printf ("%02d ", 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_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;
}

c13-3.c

/* code: c13-3.c   (v1.18.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 ("%02d ", v[i]);
  }
  printf ("\n");
}

/* ------------------------------------------ */
int int_compare (const void *va, const void *vb) {
  int a, b;
  a = *(int *) va;
  b = *(int *) vb;
  if (a < b) {
    return (-1);
  }
  else if (a > b) {
    return (1);
  }
  else {
    return (0);
  }
}

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

  print_array (array, 10);
  qsort (array, 10, sizeof (int), int_compare);
  print_array (array, 10);

  return 0;
}

c13-4.c

/* code: c13-4.c   (v1.18.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 ("%02d ", v[i]);
  }
  printf ("\n");
}

/* ------------------------------------------ */
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]
  = { 80, 40, 30, 20, 10, 00, 70, 90, 50, 60 };

  int array_temp[10];

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

  return 0;
}

q13-1.c

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

#define MAX 100000

/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;
  printf ("array: ");
  for (i = 0; i < n; i++) {
    printf ("%d ", 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 *array;

  array = malloc (sizeof (int) * MAX);

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

q13-2.c

/* code: q13-2.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

#define MAX 1000000

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

/* ------------------------------------------ */
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 *array;

  array = malloc (sizeof (int) * MAX);

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

  printf ("Quicksort (1st)\n");
  print_array (array, 30);
  quicksort (array, 0, MAX - 1);
  print_array (array, 30);

  printf ("\n");

  printf ("Quicksort (2nd)\n");
  print_array (array, 30);
  quicksort (array, 0, MAX - 1);
  print_array (array, 30);


  free (array);

  return 0;
}

q13-3.c

/* code: q13-3.c   (v1.18.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 ("%d ", 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 *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;
}

q13-4.c

/* code: q13-4.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#define MAX 100000

/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;
  printf ("array: ");
  for (i = 0; i < n; i++) {
    printf ("%d ", 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 int_compare (const void *va, const void *vb) {
  int a, b;
  a = *(int *) va;
  b = *(int *) vb;
  if (a < b) {
    return (-1);
  }
  else if (a > b) {
    return (1);
  }
  else {
    return (0);
  }
}

/* ------------------------------------------ */
int main () {
  int *array;

  array = malloc (sizeof (int) * MAX);

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

  print_array (array, 10);
  qsort (array, MAX, sizeof (int), int_compare);
  print_array (array, 10);

  free (array);

  return 0;
}

q13-5.c

/* code: q13-5.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* ------------------------------------------ */
int cmp_string (const void *p1, const void *p2) {
  return strcmp (*(char *const *) p1, *(char *const *) p2);
}

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

/* ------------------------------------------ */
int main () {
  char *array[7] = {
    "Sunday", "Monday", "Tuesday",
    "Wednesday", "Thursday", "Friday", "Saturday",
  };
  print_str_array (array, 7);
  qsort (array, 7, sizeof (char *), cmp_string);
  print_str_array (array, 7);
  return 0;
}