/*
Programmazione II - Esempio di codice
<![CDATA[
Example code: quicksort demonstration. (20000810 prelz@mi.infn.it)
*/
#include <stdio.h>
#include <stdlib.h>
#define ARRAY_SIZE 100
#define RANDOM_DEVICE "/dev/urandom"
int
main(int argc, char *argv[])
{
unsigned char numbers[ARRAY_SIZE];
FILE *rand_in;
unsigned int pseudorandom_seed;
int i;
/* Warning: /dev/urandom only exists on Linux. */
rand_in = fopen(RANDOM_DEVICE, "r");
if (rand_in == NULL)
{
fprintf(stderr,"%s: Error opening %s ",argv[0],RANDOM_DEVICE);
perror("");
exit(1);
}
/* Let's get a pseudorandom seed (will use it later) */
if (fread(&pseudorandom_seed, sizeof(pseudorandom_seed), 1, rand_in) < 1)
{
fprintf(stderr,"%s: Error reading from %s ",argv[0],RANDOM_DEVICE);
perror("");
exit(1);
}
/* Let's fill an array with 100 random "unsigned chars". */
/* That means numbers in the range 0-255. */
if (fread(numbers, sizeof(*numbers), ARRAY_SIZE, rand_in) < ARRAY_SIZE)
{
fprintf(stderr,"%s: Error reading from %s ",argv[0],RANDOM_DEVICE);
perror("");
exit(1);
}
/* We don't need /dev/urandom anymore. */
fclose(rand_in);
printf("Before ordering:\n");
for (i=0;i<ARRAY_SIZE;i++)
{
if (!(i%10)) printf("\n");
printf("[%3d] ", numbers[i]);
}
printf("\n\n");
/* Initialize pseudorandom number generator */
srand(pseudorandom_seed);
quicksort(numbers, 0, ARRAY_SIZE-1);
printf("After ordering:\n");
for (i=0;i<ARRAY_SIZE;i++)
{
if (!(i%10)) printf("\n");
printf("[%3d] ", numbers[i]);
}
printf("\n\n");
exit(0);
}
int
quicksort(unsigned char *array, int left_bound, int right_bound)
{
int partition_size;
unsigned char max,min,median,pick,swap;
int i,k;
partition_size = right_bound - left_bound + 1;
if (partition_size <= 1) return(0);
/* Choose a partition value with the "median-of-three" method. */
max = min = array[left_bound + rand()%partition_size];
pick = array[left_bound + rand()%partition_size];
if (pick > max) max = pick;
else if (pick < min) min = pick;
pick = array[left_bound + rand()%partition_size];
if (pick > max) median = max;
else if (pick < min) median = min;
else median = pick;
for (i = left_bound, k = right_bound; ; i++,k--)
{
while (array[i] < median) i++;
while (array[k] > median) k--;
/* Now stop if indexes crossed. This way we are sure that k is the
/* last element of the left partition. */
if (i>=k) break;
/* We found a pair that's out of order. Let's swap them. */
swap = array[i];
array[i] = array[k];
array[k] = swap;
}
/* Operate on the left and right sub-partitions. */
quicksort(array,left_bound,k);
quicksort(array,k+1,right_bound);
return(0);
}
]]></plaintext></span>