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