/****************************************************************************
PROGRAMA:	quick.c
AUTOR:		Kiko
FECHA:		14.10.96
FINALIDAD:	quicksort
HISTORIA:
BIBLIOGRAFIA:	Algoritmos + Estructuras de Datos = Programas. N. Wirth.
MODO DE UTILIZACION:
****************************************************************************/
#include <stdlib.h>
#include <stdio.h>

#define N 1000				/* Tama¤o del vector a ordenar */
#define M 50				/* Tama¤o del registro (salvo la clave) */

typedef unsigned claves;
typedef struct {
	claves clave;
	char resto[M];
} items;

items v[N];

void inicializa(void);
void escribe(void);

/*::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::*/
void inicializa(void) {
	unsigned i;

	for(i = 0; i < N; i++) {
		v[i].clave = rand();
	}
}
/*::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::*/
void escribe(void) {
	unsigned i;

	for(i = 0; i < N; i++)
		printf("v[%u] = %i\n", i, v[i].clave);
}
/*::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::*/
void quicksort(unsigned iz, unsigned de) {
	register unsigned i, j;
	claves pivot;
	items temp;

	i = iz;
	j = de;
	pivot = v[(iz + de) / 2].clave;
	do {
		while (v[i].clave < pivot)
			i++;
		while (pivot < v[j].clave)
			j--;
		if (i <= j) {
			temp = v[i];	/* intercambiar v[i] y v[j] */
			v[i] = v[j];
			v[j] = temp;
			i++;
			j--;
		}
	} while (i <= j);
	if (iz < j)
		quicksort(iz, j);
	if (i < de)
		quicksort(i, de);
}
/*::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::*/
main() {
	inicializa();
	quicksort(0, N - 1);
	escribe();
   printf("Tama¤o de los items: %u bytes\n", sizeof(items));
	return;
}