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