--- /dev/null
+# Makefile de ejemplo para C++
+#
+# Creado: jue abr 15 15:34:19 ART 2004
+#
+# Copyleft 2004 - Leandro Lucarella, Bajo licencia GPL [http://www.gnu.org/]
+#
+
+# CONFIGURACION
+################
+
+# Nombre del ejecutable.
+TARGETS = s_ext bufford_test
+
+# Opciones para el compilador C.
+CFLAGS = -Wall -ggdb -ansi -pedantic -DDEBUG
+
+# Opciones para el compilador C++.
+CXXFLAGS = $(CFLAGS) -fno-inline
+
+# REGLAS
+#########
+
+.PHONY: all clean
+
+all: $(TARGETS)
+
+bufford_test: bufford.o bufford_test.o
+
+clean:
+ @$(RM) -fv *.o $(TARGETS)
+
--- /dev/null
+
+#include "bufford.h"
+#include <malloc.h>
+#include <string.h>
+#include <assert.h>
+
+#define LT(b, x, y) (b->cmp(x, y) < 0)
+#define GT(b, x, y) (b->cmp(x, y) > 0)
+#define EQ(b, x, y) (b->cmp(x, y) == 0)
+#define NE(b, x, y) (b->cmp(x, y) != 0)
+#define LE(b, x, y) (b->cmp(x, y) <= 0)
+#define GE(b, x, y) (b->cmp(x, y) >= 0)
+
+static BUFFORD_NODE* bufford_node_new(void* data, size_t reg_size);
+
+static void bufford_node_delete(BUFFORD_NODE* node);
+
+static void bufford_clear_node_recursive(BUFFORD_NODE* node);
+
+static void bufford_insert_node(BUFFORD* buff, BUFFORD_NODE* new_node);
+
+BUFFORD_NODE* bufford_node_new(void* data, size_t reg_size)
+{
+ BUFFORD_NODE* n = malloc(sizeof(BUFFORD_NODE));
+ if (!n) return 0;
+ assert(data);
+ /* hago una copia del dato */
+ n->data = malloc(reg_size);
+ if (n->data) {
+ memcpy(n->data, data, reg_size);
+ } else {
+ free(n);
+ return 0;
+ }
+ n->right = 0;
+ n->left = 0;
+ return n;
+}
+
+void bufford_node_delete(BUFFORD_NODE* node)
+{
+ assert(node);
+ free(node);
+}
+
+void bufford_clear_node_recursive(BUFFORD_NODE* node)
+{
+ assert(node);
+ assert(node->data);
+ if (node->left) bufford_clear_node_recursive(node->left);
+ if (node->right) bufford_clear_node_recursive(node->right);
+ free(node->data);
+ bufford_node_delete(node);
+}
+
+void bufford_insert_node(BUFFORD* buff, BUFFORD_NODE* new_node)
+{
+ assert(buff);
+ assert(new_node);
+ if (buff->root) { /* no está vacío */
+ BUFFORD_NODE* curr = buff->root;
+ /* tiene algo */
+ while (1) {
+ if (LT(buff, new_node->data, curr->data)) {
+ if (curr->left) { /* hay más, paso al próximo */
+ curr = curr->left;
+ continue;
+ }
+ /* no hay más, lo inserto */
+ curr->left = new_node;
+ return;
+ }
+ if (GT(buff, new_node->data, curr->data)) {
+ if (curr->right) { /* hay más, paso al próximo */
+ curr = curr->right;
+ continue;
+ }
+ /* no hay más, lo inserto */
+ curr->right = new_node;
+ return;
+ }
+ /* es igual! => error */
+ assert(NE(buff, new_node->data, curr->data));
+ return;
+ }
+ }
+ /* está vacío */
+ buff->root = new_node;
+}
+
+BUFFORD* bufford_new(size_t size, size_t reg_size, CMP_FUNC cmp)
+{
+ BUFFORD* b = malloc(sizeof(BUFFORD));
+ if (!b) return 0;
+ assert(cmp);
+ assert(reg_size > 0);
+ assert(size > reg_size);
+ b->cmp = cmp;
+ b->size = 0;
+ b->root = 0;
+ b->max_size = size / reg_size;
+ b->reg_size = reg_size;
+ return b;
+}
+
+void bufford_delete(BUFFORD* buff)
+{
+ assert(buff);
+ bufford_clear(buff);
+ free(buff);
+}
+
+void bufford_clear(BUFFORD* buff)
+{
+ assert(buff);
+ if (buff->root) bufford_clear_node_recursive(buff->root);
+ buff->root = 0;
+}
+
+int bufford_full(BUFFORD* buff)
+{
+ assert(buff);
+ return buff->size == buff->max_size;
+}
+
+int bufford_empty(BUFFORD* buff)
+{
+ assert(buff);
+ return buff->size == 0;
+}
+
+int bufford_push(BUFFORD* buff, void* data)
+{
+ BUFFORD_NODE* new_node;
+ assert(buff);
+ assert(data);
+ if (buff->size == buff->max_size) return 0; /* ERROR, está lleno */
+ new_node = bufford_node_new(data, buff->reg_size);
+ if (!new_node) return 0; /* ERROR, no hay memoria */
+ if (buff->root) { /* no está vacío */
+ BUFFORD_NODE* curr = buff->root;
+ /* tiene algo */
+ while (1) {
+ if (LT(buff, data, curr->data)) {
+ if (curr->left) { /* hay más, paso al próximo */
+ curr = curr->left;
+ continue;
+ }
+ /* no hay más, lo inserto */
+ curr->left = new_node;
+ buff->size++;
+ return 1; /* OK */
+ }
+ if (GT(buff, data, curr->data)) {
+ if (curr->right) { /* hay más, paso al próximo */
+ curr = curr->right;
+ continue;
+ }
+ /* no hay más, lo inserto */
+ curr->right = new_node;
+ buff->size++;
+ return 1; /* OK */
+ }
+ /* es igual! => error */
+ free(new_node);
+ assert(NE(buff, data, curr->data));
+ return 0; /* ERROR, dato duplicado */
+ }
+ }
+ /* está vacío */
+ buff->root = new_node;
+ buff->size++;
+ return 1; /* OK */
+}
+
+void* bufford_pop(BUFFORD* buff, void* min)
+{
+ /* nodo iterador */
+ BUFFORD_NODE* curr = buff->root;
+ /* nodo previo al iterador */
+ BUFFORD_NODE* prev = 0;
+ /* nodo con el dato más pequeño encontrado hasta ahora */
+ BUFFORD_NODE* curr_min = 0;
+ /* padre del nodo con el dato más pequeño encontrado hasta ahora */
+ BUFFORD_NODE* padre = 0;
+ /* valor mínimo encontrado, si se encontró */
+ void* min_found = 0;
+ assert(buff);
+ assert(min);
+ /* buscamos el mínimo nodo mayor que 'min' */
+ while (curr) {
+ if (GT(buff, curr->data, min)) { /* actual mayor que buscado */
+ /* guardo y paso al de la izquierda */
+ curr_min = curr;
+ padre = prev;
+ prev = curr;
+ curr = curr->left;
+ } else { /* actual no es mayor que buscado, paso a derecha */
+ prev = curr;
+ curr = curr->right;
+ }
+ }
+ /* si encontramos uno, lo sacamos del árbol */
+ if (curr_min) {
+ BUFFORD_NODE* link; /* nodo al cual enganchar con el padre */
+ BUFFORD_NODE* orphan = 0; /* nodo huerfano */
+ if (curr_min->left) {
+ link = curr_min->left;
+ orphan = curr_min->right;
+ } else {
+ link = curr_min->right;
+ }
+ if (padre) { /* si tiene padre (no es el raíz) */
+ if (padre->left == curr_min) { /* si es el de la izq */
+ padre->left = link; /* enganchamos */
+ } else { /* si no, es el de la derecha */
+ padre->right = link; /* enganchamos */
+ }
+ } else { /* si es el raíz */
+ buff->root = link; /* ponemos el nuevo raíz */
+ }
+ if (orphan) { /* si quedó un huerfano, lo insertamos */
+ bufford_insert_node(buff, orphan);
+ }
+ min_found = curr_min->data;
+ bufford_node_delete(curr_min);
+ buff->size--;
+ }
+ return min_found;
+}
+
+void* bufford_pop_min(BUFFORD* buff)
+{
+ /* nodo iterador */
+ BUFFORD_NODE* curr = buff->root;
+ /* nodo previo al iterador */
+ BUFFORD_NODE* prev = 0;
+ /* valor mínimo encontrado, si se encontró */
+ void* min_found = 0;
+ assert(buff);
+ if (!curr) return 0; /* si no hay nodos, no hay nada que hacer */
+ /* buscamos el mínimo nodo */
+ while (curr->left) {
+ prev = curr;
+ curr = curr->left;
+ }
+ /* lo sacamos del árbol */
+ if (prev) { /* si tiene padre (no es el raíz) */
+ /* le cuelgo de la izquierda el hijo de la derecha, sabemos que a
+ * izquierda no tiene nada.*/
+ prev->left = curr->right;
+ } else { /* si es el raíz */
+ buff->root = curr->right; /* ponemos el nuevo raíz */
+ }
+ min_found = curr->data;
+ bufford_node_delete(curr);
+ buff->size--;
+ return min_found;
+}
+
+void* bufford_get_min(BUFFORD* buff)
+{
+ /* nodo iterador */
+ BUFFORD_NODE* curr = buff->root;
+ assert(buff);
+ if (!curr) return 0; /* si no hay nodos, no hay nada que hacer */
+ /* buscamos el mínimo nodo */
+ while (curr->left) curr = curr->left;
+ return curr->data;
+}
+
+void* bufford_get_next(BUFFORD* buff, void* min)
+{
+ /* nodo iterador */
+ BUFFORD_NODE* curr = buff->root;
+ /* nodo con el dato más pequeño encontrado hasta ahora */
+ BUFFORD_NODE* curr_min = 0;
+ assert(buff);
+ assert(min);
+ /* buscamos el mínimo nodo mayor que 'min' */
+ while (curr) {
+ if (GT(buff, curr->data, min)) { /* actual mayor que buscado */
+ /* guardo y paso al de la izquierda */
+ curr_min = curr;
+ curr = curr->left;
+ } else curr = curr->right; /* paso a la derecha */
+ }
+ if (curr_min) return curr_min->data;
+ return 0;
+}
+
--- /dev/null
+
+#include <stdlib.h>
+
+typedef int (*CMP_FUNC)(void*, void*);
+
+typedef struct _BUFFORD_NODE
+{
+ void* data;
+ struct _BUFFORD_NODE* left;
+ struct _BUFFORD_NODE* right;
+}
+BUFFORD_NODE;
+
+typedef struct
+{
+ CMP_FUNC cmp;
+ BUFFORD_NODE* root;
+ size_t size;
+ size_t max_size;
+ size_t reg_size;
+}
+BUFFORD;
+
+BUFFORD* bufford_new(size_t size, size_t reg_size, CMP_FUNC cmp);
+
+void bufford_delete(BUFFORD* buff);
+
+void bufford_clear(BUFFORD* buff);
+
+int bufford_full(BUFFORD* buff);
+
+int bufford_empty(BUFFORD* buff);
+
+int bufford_push(BUFFORD* buff, void* data);
+
+void* bufford_pop(BUFFORD* buff, void* min);
+
+void* bufford_pop_min(BUFFORD* buff);
+
+void* bufford_get_min(BUFFORD* buff);
+
+void* bufford_get_next(BUFFORD* buff, void* min);
+
--- /dev/null
+2
+456
+7
+3
+23
+4
+6
+34
+5678
+56
+89
+26
+624
+45
+282762
+22
+77
+99
+21
--- /dev/null
+
+#include "bufford.h"
+#include <stdio.h>
+
+/*
+typedef struct
+{
+ int id;
+ int estado;
+ int nrofac;
+}
+RECORD;
+*/
+
+int cmp(void* x, void* y)
+{
+ int xx = *(int*)x;
+ int yy = *(int*)y;
+ if (xx > yy) return 1;
+ if (xx < yy) return -1;
+ return 0;
+}
+
+void buffer_dump(BUFFORD* b)
+{
+ int* c;
+ printf("Buffer: ");
+ for (c = bufford_get_min(b); c; c = bufford_get_next(b, c))
+ printf("%i ", *c);
+ printf("\n");
+}
+
+int main(int argc, char* argv[])
+{
+ FILE* fp;
+ BUFFORD* b = bufford_new(sizeof(int) * 8, sizeof(int), &cmp);
+ if (!b) return 1;
+ fp = fopen(argv[1], "r");
+ while (1) {
+ int reg;
+ fscanf(fp, "%i", ®);
+ if (feof(fp)) break;
+ if (reg == 0) continue;
+ if (!bufford_push(b, ®)) { /* no hay más lugar */
+ int new_reg;
+ int de_nuevo = 1;
+ printf("No se pudo insertar el valor %i, el buffer está lleno!\n", reg);
+ buffer_dump(b);
+ while (de_nuevo) {
+ int* poped;
+ printf("Debe sacar algún valor: ");
+ scanf("%i", &new_reg);
+ if ((poped = bufford_pop(b, &new_reg))) {
+ printf("Se sacó el valor %i con éxito!\n", *poped);
+ free(poped);
+ if (!bufford_push(b, ®)) { /* no hay más lugar */
+ printf("Hubo un error FEO!\n");
+ return -1;
+ }
+ de_nuevo = 0;
+ } else {
+ printf("No hay ningún valor menor a %i en el buffer!\n", new_reg);
+ }
+ }
+ }
+ printf("Se insertó el valor %i con éxito!\n", reg);
+ }
+ printf("Fin!!!\n");
+ buffer_dump(b);
+ /* vacío el buffer */
+ {
+ int* c;
+ int x;
+ for (c = bufford_pop_min(b); c; c = bufford_pop(b, &x)) {
+ x = *c;
+ free(c);
+ printf("Se sacó el valor %i con éxito!\n", x);
+ buffer_dump(b);
+ }
+ }
+ bufford_delete(b);
+ return 0;
+}
+
--- /dev/null
+program Comparacion_De_Algoritmos_De_Ordenamiento;
+
+uses
+ CRT, DOS;
+
+const
+ MAX_APE = 15;
+ RETARDO = 50;
+ VERSION = '1.2.8';
+
+type
+ APELLIDO = string[MAX_APE];
+ DOCUMENTO = longint;
+ PERSONA = record
+ ap: APELLIDO;
+ dni: DOCUMENTO;
+ end;
+ TABLA = array[1..1000] of PERSONA;
+
+(*********************************************************)
+
+ procedure CargarArchivo( var datos: TABLA; var ar: text; tam: integer );
+
+ var
+ i: integer;
+
+ begin
+ for i:= 1 to tam do
+ begin
+ writeln( ar, datos[i].ap );
+ writeln( ar, datos[i].dni );
+ writeln( ar );
+ end;
+ end; { procedure CargarArchivo }
+
+(*********************************************************)
+
+ procedure Retardar( centenas: longint );
+
+ var
+ i: integer;
+
+ begin
+ for i:= 1 to centenas * 100 do ;
+ end; { procedure Retardar }
+
+(*********************************************************)
+(*********************************************************)
+
+ procedure MenuEvaluar( var datos: TABLA; var arch: text );
+
+ type
+ HORA = record
+ h,
+ m,
+ s,
+ c: longint;
+ end;
+ ORDEN = ( CRECIENTE, DECRECIENTE );
+ MEDICION = record
+ Comp,
+ Int,
+ Tiem: longint;
+ end;
+ var
+ bs, bsm, shs, rs, ss, is, sls, slsm, qs: MEDICION;
+
+ (*********************************************************)
+
+ procedure CrearInforme( ord: ORDEN );
+
+ (*********************************************************)
+
+ procedure InfMetodo( var info: text; metodo: string; sort: MEDICION );
+
+ begin
+ writeln( info );
+ writeln( info, metodo, ':' );
+ writeln( info, ' Comparaciones: ', sort.Comp: 1 );
+ writeln( info, ' Intercambios: ', sort.Int div 3: 1, ' (', sort.Int: 1, ' asignaciones)' );
+ writeln( info, ' Tiempo (seg): ', sort.Tiem / 100: 2: 2 );
+ end; { procedure InfMetodo }
+
+ (*********************************************************)
+
+ var { procedure CrearInforme }
+ info: text;
+
+ begin
+ assign( info, 'INFORME.TXT' );
+ rewrite( info );
+ writeln( info );
+ if ord = DECRECIENTE then
+ begin
+ writeln( info, 'INFORME: Orden Decreciente.' );
+ writeln( info, '======= ~~~~~ ~~~~~~~~~~~' );
+ end
+ else
+ begin
+ writeln( info, 'INFORME: Orden Creciente.' );
+ writeln( info, '======= ~~~~~ ~~~~~~~~~' );
+ end;
+ writeln( info );
+ InfMetodo( info, 'Bubble Sort', bs );
+ InfMetodo( info, 'Bubble Sort Mejorado', bsm );
+ InfMetodo( info, 'Shake Sort', shs );
+ InfMetodo( info, 'Ripple Sort', rs );
+ InfMetodo( info, 'Selection Sort', ss );
+ InfMetodo( info, 'Insertion Sort', is );
+ InfMetodo( info, 'Shell''s Sort', sls );
+ InfMetodo( info, 'Shell''s Sort Mejorado', slsm );
+ InfMetodo( info, 'Quick Sort', qs );
+ writeln( info );
+ writeln( info );
+ writeln( info, 'NOTA: La cantidad de intercambios medida se tom¢ a partir de la cantidad de' );
+ writeln( info, '==== asignaciones, ya que en el Insertion Sort no hay intercambios. De esta' );
+ writeln( info, ' manera, un intercambio equivales a 3 asignaciones.' );
+ close( info );
+ end; { procedure CrearInforme }
+
+ (*********************************************************)
+
+ procedure NoExisteArch;
+
+ begin
+ clrscr;
+ gotoxy( 20, 10 );
+ textcolor( LightMagenta + Blink );
+ writeln( 'ERROR: No existe el archivo a evaluar!' );
+ textcolor( LightGray );
+ writeln;
+ writeln( ' Creelo seleccionando la opci¢n 1 del Men£ Principal.' );
+ delay( 4000 );
+ end; { procedure NoExisteArch }
+
+ (*********************************************************)
+
+ function ExisteArchivo( nombre: String ): boolean;
+
+ { funcion extrida de la ayuda del Turbo Pascal 7 }
+
+ var
+ arch: text;
+
+ begin
+ {$I-}
+ Assign( arch, nombre );
+ FileMode := 0; { Solo lectura }
+ Reset( arch );
+ Close( arch );
+ {$I+}
+ ExisteArchivo := (IOResult = 0) and (nombre <> '');
+ end; { function ExisteArchivo }
+
+ (*********************************************************)
+
+ procedure CargarTabla( var ar: text; var datos: TABLA; tam: integer );
+
+ var
+ i: integer;
+ void: string[2];
+
+ begin
+ for i:= 1 to tam do
+ begin
+ readln( ar, datos[i].ap );
+ readln( ar, datos[i].dni );
+ readln( ar, void );
+ end;
+ end; { procedure CargarTabla }
+
+ (*********************************************************)
+
+ procedure Intercambiar( var a, b: PERSONA; var int: longint );
+
+ var
+ aux: PERSONA;
+
+ begin
+ int := int + 1;
+ Retardar( RETARDO );
+ aux := a;
+ int := int + 1;
+ Retardar( RETARDO );
+ a := b;
+ int := int + 1;
+ Retardar( RETARDO );
+ b := aux;
+ end; { procedure Intercambiar }
+
+ (*********************************************************)
+
+ procedure GetHora( var hor: HORA );
+
+ var
+ h, m, s, c: word;
+
+ begin
+ gettime( h, m, s, c );
+ hor.h := h;
+ hor.m := m;
+ hor.s := s;
+ hor.c := c;
+ end; { procedure GetHora }
+
+ (*********************************************************)
+
+ function GetTiempo( h1, h2: HORA ): longint;
+
+ var
+ t: longint;
+ aux: HORA;
+
+ begin
+ if h1.h <> h2.h then { pone al menor como h2 y al mayor como h1 }
+ begin
+ if h1.h < h2.h then
+ begin
+ aux := h1;
+ h1 := h2;
+ h2 := aux;
+ end
+ end
+ else if h1.m <> h2.m then
+ begin
+ if h1.m < h2.m then
+ begin
+ aux := h1;
+ h1 := h2;
+ h2 := aux;
+ end
+ end
+ else if h1.s <> h2.s then
+ begin
+ if h1.s < h2.s then
+ begin
+ aux := h1;
+ h1 := h2;
+ h2 := aux;
+ end
+ end
+ else if h1.c <> h2.c then
+ if h1.c < h2.c then
+ begin
+ aux := h1;
+ h1 := h2;
+ h2 := aux;
+ end;
+ t := ( ( ( h1.h - h2.h ) * 60 + ( h1.m - h2.m ) ) * 60 + ( h1.s - h2.s ) ) * 100 + ( h1.c - h2.c );
+ GetTiempo := t;
+ end; { function GetTiempo }
+
+ (*********************************************************)
+
+ procedure EvaluarCre( var datos: TABLA; var arch: text );
+
+ (*********************************************************)
+
+ procedure BubbleSort( var arch: text; var datos: TABLA; tam: integer; var m: MEDICION );
+
+ var
+ i, j: integer;
+ h1, h2: HORA;
+
+ begin
+ GetHora( h1 );
+ m.Comp := 0;
+ m.Int := 0;
+ reset( arch );
+ CargarTabla( arch, datos, 1000 );
+ close( arch );
+ for i := tam - 1 downto 1 do
+ begin
+ for j := tam - 1 downto 1 do
+ begin
+ m.Comp := m.Comp + 1;
+ Retardar( RETARDO );
+ if datos[j].ap > datos[j+1].ap then
+ Intercambiar( datos[j], datos[j+1], m.Int);
+ end;
+ end;
+ GetHora( h2 );
+ m.Tiem := GetTiempo( h1, h2 );
+ end; { procedure BubbleSort }
+
+ (*********************************************************)
+
+ procedure BubbleSortMej( var arch: text; var datos: TABLA; tam: integer; var m: MEDICION );
+
+ var
+ huboint: boolean;
+ i, n: integer;
+ h1, h2: HORA;
+
+ begin
+ GetHora( h1 );
+ m.Comp := 0;
+ m.Int := 0;
+ n := 1;
+ reset( arch );
+ CargarTabla( arch, datos, 1000 );
+ close( arch );
+ huboint := true;
+ while huboint do
+ begin
+ huboint := false;
+ for i := tam - 1 downto n do
+ begin
+ m.Comp := m.Comp + 1;
+ Retardar( RETARDO );
+ if datos[i].ap > datos[i+1].ap then
+ begin
+ Intercambiar( datos[i], datos[i+1], m.Int);
+ huboint := true;
+ end;
+ end;
+ n := n + 1;
+ end;
+ GetHora( h2 );
+ m.Tiem := GetTiempo( h1, h2 );
+ end; { procedure BubbleSortMej }
+
+ (*********************************************************)
+
+ procedure ShakeSort( var arch: text; var datos: TABLA; tam: integer; var m: MEDICION );
+ var
+ h1, h2: HORA;
+ i, d, j, tmp: integer;
+
+ begin
+ GetHora( h1 );
+ m.Comp := 0;
+ m.Int := 0;
+ reset( arch );
+ CargarTabla( arch, datos, 1000 );
+ close( arch );
+ i := 2;
+ d := tam;
+ tmp := tam;
+ repeat
+ for j := d downto i do
+ begin
+ m.Comp := m.Comp + 1;
+ Retardar( RETARDO );
+ if datos[j].ap < datos[j-1].ap then
+ begin
+ Intercambiar( datos[j], datos[j-1], m.Int );
+ tmp := j;
+ end;
+ end;
+ i := tmp + 1;
+ for j := i to d do
+ begin
+ m.Comp := m.Comp + 1;
+ Retardar( RETARDO );
+ if datos[j].ap < datos[j-1].ap then
+ begin
+ Intercambiar( datos[j], datos[j-1], m.Int );
+ tmp := j;
+ end;
+ end;
+ d := tmp - 1;
+ until i >= d;
+ GetHora( h2 );
+ m.Tiem := GetTiempo( h1, h2 );
+ end; { procedure ShakeSort }
+
+ (*********************************************************)
+
+ procedure RippleSort( var arch: text; var datos: TABLA; tam: integer; var m: MEDICION );
+ var
+ h1, h2: HORA;
+ i, j: integer;
+
+ begin
+ GetHora( h1 );
+ m.Comp := 0;
+ m.Int := 0;
+ reset( arch );
+ CargarTabla( arch, datos, 1000 );
+ close( arch );
+ for i := 1 to tam do
+ begin
+ for j := i + 1 to tam do
+ begin
+ m.Comp := m.Comp + 1;
+ Retardar( RETARDO );
+ if datos[i].ap > datos[j].ap then Intercambiar( datos[i], datos[j], m.Int );
+ end;
+ end;
+ GetHora( h2 );
+ m.Tiem := GetTiempo( h1, h2 );
+ end; { procedure RippleSort }
+
+ (*********************************************************)
+
+ procedure SelectionSort( var arch: text; var datos: TABLA; tam: integer; var m: MEDICION );
+ var
+ i, sel, n: integer;
+ hubosel: boolean;
+ h1, h2: HORA;
+
+ begin
+ GetHora( h1 );
+ m.Comp := 0;
+ m.Int := 0;
+ reset( arch );
+ CargarTabla( arch, datos, 1000 );
+ close( arch );
+ for n := 1 to tam - 1 do
+ begin
+ hubosel := false;
+ sel := n;
+ for i := n + 1 to tam do
+ begin
+ m.Comp := m.Comp + 1;
+ Retardar( RETARDO );
+ if datos[sel].ap > datos[i].ap then
+ begin
+ sel := i;
+ hubosel := true;
+ end;
+ end;
+ if hubosel then Intercambiar( datos[n], datos[sel], m.Int);
+ end;
+ GetHora( h2 );
+ m.Tiem := GetTiempo( h1, h2 );
+ end; { procedure SelectionSort }
+
+ (*********************************************************)
+
+ procedure InsertionSort( var arch: text; var datos: TABLA; tam: integer; var m: MEDICION );
+ var
+ h1, h2: HORA;
+ i, j, k: integer;
+ tmp: PERSONA;
+ terminar: boolean;
+
+ begin
+ GetHora( h1 );
+ m.Comp := 0;
+ m.Int := 0;
+ reset( arch );
+ CargarTabla( arch, datos, 1000 );
+ close( arch );
+ for i := 2 to tam do
+ begin
+ m.Int := m.Int + 1;
+ Retardar( RETARDO );
+ tmp := datos[i];
+ j := i - 1;
+ terminar := false;
+ while ( j >= 1 ) and ( not terminar ) do
+ begin
+ m.Comp := m.Comp + 1;
+ Retardar( RETARDO );
+ if ( tmp.ap < datos[j].ap ) then
+ begin
+ m.Int := m.Int + 1;
+ Retardar( RETARDO );
+ datos[j+1] := datos[j];
+ j := j - 1;
+ end
+ else terminar := true;
+ end;
+ m.Int := m.Int + 1;
+ Retardar( RETARDO );
+ datos[j+1] := tmp;
+ end;
+ GetHora( h2 );
+ m.Tiem := GetTiempo( h1, h2 );
+ end; { procedure InsertionSort }
+
+ (*********************************************************)
+
+ procedure ShellSort( var arch: text; var datos: TABLA; tam: integer; var m: MEDICION );
+ var
+ h1, h2: HORA;
+ hueco, i, j: integer;
+ huboint: boolean;
+
+ begin
+ GetHora( h1 );
+ m.Comp := 0;
+ m.Int := 0;
+ reset( arch );
+ CargarTabla( arch, datos, 1000 );
+ close( arch );
+ hueco := tam;
+ while hueco > 1 do
+ begin
+ hueco := hueco div 2;
+ huboint := true;
+ while huboint do
+ begin
+ huboint := false;
+ for i := 1 to tam - hueco do
+ begin
+ j := i + hueco;
+ m.Comp := m.Comp + 1;
+ Retardar( RETARDO );
+ if ( datos[i].ap > datos[j].ap ) then
+ begin
+ Intercambiar( datos[i], datos[j], m.Int );
+ huboint := true;
+ end;
+ end;
+ end;
+ end;
+ GetHora( h2 );
+ m.Tiem := GetTiempo( h1, h2 );
+ end; { procedure ShellSort }
+
+ (*********************************************************)
+
+ procedure ShellSortMej( var arch: text; var datos: TABLA; tam: integer; var m: MEDICION );
+
+ (*********************************************************)
+
+ procedure Shell( var datos: TABLA; hueco, i: integer; var comp, int: longint );
+ var
+ j: integer;
+
+ begin
+ j := i + hueco;
+ comp := comp + 1;
+ Retardar( RETARDO );
+ if ( datos[i].ap > datos[j].ap ) then
+ begin
+ Intercambiar( datos[i], datos[j], int );
+ if (i - hueco) > 0 then
+ Shell( datos, hueco, i - hueco, comp, int );
+ end;
+ end; { procedure Shell }
+
+ (*********************************************************)
+
+ var { procedure ShellSortMej }
+ h1, h2: HORA;
+ hueco, i, j: integer;
+
+ begin
+ GetHora( h1 );
+ m.Comp := 0;
+ m.Int := 0;
+ reset( arch );
+ CargarTabla( arch, datos, 1000 );
+ close( arch );
+ hueco := tam;
+ while hueco > 1 do
+ begin
+ hueco := hueco div 2;
+ for i := 1 to tam - hueco do
+ begin
+ j := i + hueco;
+ m.Comp := m.Comp + 1;
+ Retardar( RETARDO );
+ if ( datos[i].ap > datos[j].ap ) then
+ begin
+ Intercambiar( datos[i], datos[j], m.Int );
+ if (i - hueco) > 0 then
+ Shell( datos, hueco, i - hueco, m.Comp, m.Int );
+ end;
+ end;
+ end;
+ GetHora( h2 );
+ m.Tiem := GetTiempo( h1, h2 );
+ end; { procedure ShellSortMej }
+
+ (*********************************************************)
+
+ procedure QuickSort( var arch: text; var datos: TABLA; tam: integer; var m: MEDICION );
+
+ (*********************************************************)
+
+ procedure QSort( var datos: TABLA; min, max: integer; var comp, int: longint );
+
+ var
+ i, j: integer;
+ sel: PERSONA;
+ flag: boolean;
+
+ begin
+ sel := datos[( min + max ) div 2];
+ i := min;
+ j := max;
+ repeat
+ comp := comp + 1;
+ Retardar( RETARDO );
+ flag := false;
+ while datos[i].ap < sel.ap do
+ begin
+ if flag then begin
+ comp := comp + 1;
+ Retardar( RETARDO );
+ end
+ else flag := true;
+ i := i + 1;
+ end;
+ comp := comp + 1;
+ Retardar( RETARDO );
+ flag := false;
+ while datos[j].ap > sel.ap do
+ begin
+ if flag then begin
+ comp := comp + 1;
+ Retardar( RETARDO );
+ end
+ else flag := true;
+ j := j - 1;
+ end;
+ if i <= j then
+ begin
+ if i < j then Intercambiar( datos[i], datos[j], int );
+ i := i + 1;
+ j := j - 1;
+ end;
+ until i > j;
+ if min < j then QSort( datos, min, j, comp, int);
+ if i < max then QSort( datos, i, max, comp, int);
+ end; { procedure QSort }
+
+ (*********************************************************)
+
+ var
+ h1, h2: HORA;
+
+ begin { procedure QuickSort }
+ GetHora( h1 );
+ m.Comp := 0;
+ m.Int := 0;
+ reset( arch );
+ CargarTabla( arch, datos, 1000 );
+ close( arch );
+ QSort( datos, 1, 1000, m.Comp, m.Int );
+ GetHora( h2 );
+ m.Tiem := GetTiempo( h1, h2 );
+ end; { procedure QuickSort }
+
+ (*********************************************************)
+
+ begin { procedure EvaluarCre }
+ if ExisteArchivo( 'DATOS.TXT' ) then
+ begin
+ BubbleSort( arch, datos, 1000, bs );
+ BubbleSortMej( arch, datos, 1000, bsm );
+ ShakeSort( arch, datos, 1000, shs );
+ RippleSort( arch, datos, 1000, rs );
+ SelectionSort( arch, datos, 1000, ss );
+ InsertionSort( arch, datos, 1000, is );
+ ShellSort( arch, datos, 1000, sls );
+ ShellSortMej( arch, datos, 1000, slsm );
+ QuickSort( arch, datos, 1000, qs );
+ CrearInforme( CRECIENTE );
+ end
+ else
+ NoExisteArch;
+ end; { procedure EvaluarCre }
+
+ (*********************************************************)
+
+ procedure EvaluarDec( var datos: TABLA; var arch: text );
+
+ (*********************************************************)
+
+ procedure BubbleSort( var arch: text; var datos: TABLA; tam: integer; var m: MEDICION );
+
+ var
+ i, j: integer;
+ h1, h2: HORA;
+
+ begin
+ GetHora( h1 );
+ m.Comp := 0;
+ m.Int := 0;
+ reset( arch );
+ CargarTabla( arch, datos, 1000 );
+ close( arch );
+ for i := tam - 1 downto 1 do
+ begin
+ for j := tam - 1 downto 1 do
+ begin
+ m.Comp := m.Comp + 1;
+ Retardar( RETARDO );
+ if datos[j].ap < datos[j+1].ap then
+ Intercambiar( datos[j], datos[j+1], m.Int);
+ end;
+ end;
+ GetHora( h2 );
+ m.Tiem := GetTiempo( h1, h2 );
+ end; { procedure BubbleSort }
+
+ (*********************************************************)
+
+ procedure BubbleSortMej( var arch: text; var datos: TABLA; tam: integer; var m: MEDICION );
+
+ var
+ huboint: boolean;
+ i, n: integer;
+ h1, h2: HORA;
+
+ begin
+ GetHora( h1 );
+ m.Comp := 0;
+ m.Int := 0;
+ n := 1;
+ reset( arch );
+ CargarTabla( arch, datos, 1000 );
+ close( arch );
+ huboint := true;
+ while huboint do
+ begin
+ huboint := false;
+ for i := tam - 1 downto n do
+ begin
+ m.Comp := m.Comp + 1;
+ Retardar( RETARDO );
+ if datos[i].ap < datos[i+1].ap then
+ begin
+ Intercambiar( datos[i], datos[i+1], m.Int);
+ huboint := true;
+ end;
+ end;
+ n := n + 1;
+ end;
+ GetHora( h2 );
+ m.Tiem := GetTiempo( h1, h2 );
+ end; { procedure BubbleSortMej }
+
+ (*********************************************************)
+
+ procedure ShakeSort( var arch: text; var datos: TABLA; tam: integer; var m: MEDICION );
+ var
+ h1, h2: HORA;
+ i, d, j, tmp: integer;
+
+ begin
+ GetHora( h1 );
+ m.Comp := 0;
+ m.Int := 0;
+ reset( arch );
+ CargarTabla( arch, datos, 1000 );
+ close( arch );
+ i := 2;
+ d := tam;
+ tmp := tam;
+ repeat
+ for j := d downto i do
+ begin
+ m.Comp := m.Comp + 1;
+ Retardar( RETARDO );
+ if datos[j].ap > datos[j-1].ap then
+ begin
+ Intercambiar( datos[j], datos[j-1], m.Int );
+ tmp := j;
+ end;
+ end;
+ i := tmp + 1;
+ for j := i to d do
+ begin
+ m.Comp := m.Comp + 1;
+ Retardar( RETARDO );
+ if datos[j].ap > datos[j-1].ap then
+ begin
+ Intercambiar( datos[j], datos[j-1], m.Int );
+ tmp := j;
+ end;
+ end;
+ d := tmp - 1;
+ until i >= d;
+ GetHora( h2 );
+ m.Tiem := GetTiempo( h1, h2 );
+ end; { procedure ShakeSort }
+
+ (*********************************************************)
+
+ procedure RippleSort( var arch: text; var datos: TABLA; tam: integer; var m: MEDICION );
+ var
+ h1, h2: HORA;
+ i, j: integer;
+
+ begin
+ GetHora( h1 );
+ m.Comp := 0;
+ m.Int := 0;
+ reset( arch );
+ CargarTabla( arch, datos, 1000 );
+ close( arch );
+ for i := 1 to tam do
+ begin
+ for j := i + 1 to tam do
+ begin
+ m.Comp := m.Comp + 1;
+ Retardar( RETARDO );
+ if datos[i].ap < datos[j].ap then Intercambiar( datos[i], datos[j], m.Int );
+ end;
+ end;
+ GetHora( h2 );
+ m.Tiem := GetTiempo( h1, h2 );
+ end; { procedure RippleSort }
+
+ (*********************************************************)
+
+ procedure SelectionSort( var arch: text; var datos: TABLA; tam: integer; var m: MEDICION );
+ var
+ i, sel, n: integer;
+ hubosel: boolean;
+ h1, h2: HORA;
+
+ begin
+ GetHora( h1 );
+ m.Comp := 0;
+ m.Int := 0;
+ reset( arch );
+ CargarTabla( arch, datos, 1000 );
+ close( arch );
+ for n := 1 to tam - 1 do
+ begin
+ hubosel := false;
+ sel := n;
+ for i := n + 1 to tam do
+ begin
+ m.Comp := m.Comp + 1;
+ Retardar( RETARDO );
+ if datos[sel].ap < datos[i].ap then
+ begin
+ sel := i;
+ hubosel := true;
+ end;
+ end;
+ if hubosel then Intercambiar( datos[n], datos[sel], m.Int);
+ end;
+ GetHora( h2 );
+ m.Tiem := GetTiempo( h1, h2 );
+ end; { procedure SelectionSort }
+
+ (*********************************************************)
+
+ procedure InsertionSort( var arch: text; var datos: TABLA; tam: integer; var m: MEDICION );
+ var
+ h1, h2: HORA;
+ i, j, k: integer;
+ tmp: PERSONA;
+ terminar: boolean;
+
+ begin
+ GetHora( h1 );
+ m.Comp := 0;
+ m.Int := 0;
+ reset( arch );
+ CargarTabla( arch, datos, 1000 );
+ close( arch );
+ for i := 2 to tam do
+ begin
+ m.Int := m.Int + 1;
+ Retardar( RETARDO );
+ tmp := datos[i];
+ j := i - 1;
+ terminar := false;
+ while ( j >= 1 ) and ( not terminar ) do
+ begin
+ m.Comp := m.Comp + 1;
+ Retardar( RETARDO );
+ if ( tmp.ap > datos[j].ap ) then
+ begin
+ m.Int := m.Int + 1;
+ Retardar( RETARDO );
+ datos[j+1] := datos[j];
+ j := j - 1;
+ end
+ else terminar := true;
+ end;
+ m.Int := m.Int + 1;
+ Retardar( RETARDO );
+ datos[j+1] := tmp;
+ end;
+ GetHora( h2 );
+ m.Tiem := GetTiempo( h1, h2 );
+ end; { procedure InsertionSort }
+
+ (*********************************************************)
+
+ procedure ShellSort( var arch: text; var datos: TABLA; tam: integer; var m: MEDICION );
+ var
+ h1, h2: HORA;
+ hueco, i, j: integer;
+ huboint: boolean;
+
+ begin
+ GetHora( h1 );
+ m.Comp := 0;
+ m.Int := 0;
+ reset( arch );
+ CargarTabla( arch, datos, 1000 );
+ close( arch );
+ hueco := tam;
+ while hueco > 1 do
+ begin
+ hueco := hueco div 2;
+ huboint := true;
+ while huboint do
+ begin
+ huboint := false;
+ for i := 1 to tam - hueco do
+ begin
+ j := i + hueco;
+ m.Comp := m.Comp + 1;
+ Retardar( RETARDO );
+ if ( datos[i].ap < datos[j].ap ) then
+ begin
+ Intercambiar( datos[i], datos[j], m.Int );
+ huboint := true;
+ end;
+ end;
+ end;
+ end;
+ GetHora( h2 );
+ m.Tiem := GetTiempo( h1, h2 );
+ end; { procedure ShellSort }
+
+ (*********************************************************)
+
+ procedure ShellSortMej( var arch: text; var datos: TABLA; tam: integer; var m: MEDICION );
+
+ (*********************************************************)
+
+ procedure Shell( var datos: TABLA; hueco, i: integer;
+ var comp: longint; var int: longint );
+ var
+ j: integer;
+
+ begin
+ j := i + hueco;
+ comp := comp + 1;
+ Retardar( RETARDO );
+ if ( datos[i].ap < datos[j].ap ) then
+ begin
+ Intercambiar( datos[i], datos[j], int );
+ if (i - hueco) > 0 then
+ Shell( datos, hueco, i - hueco, comp, int );
+ end;
+ end; { procedure Shell }
+
+ (*********************************************************)
+
+ var { procedure ShellSortMej }
+ h1, h2: HORA;
+ hueco, i, j: integer;
+
+ begin
+ GetHora( h1 );
+ m.Comp := 0;
+ m.Int := 0;
+ reset( arch );
+ CargarTabla( arch, datos, 1000 );
+ close( arch );
+ hueco := tam;
+ while hueco > 1 do
+ begin
+ hueco := hueco div 2;
+ for i := 1 to tam - hueco do
+ begin
+ j := i + hueco;
+ m.Comp := m.Comp + 1;
+ Retardar( RETARDO );
+ if ( datos[i].ap < datos[j].ap ) then
+ begin
+ Intercambiar( datos[i], datos[j], m.Int );
+ if (i - hueco) > 0 then
+ Shell( datos, hueco, i - hueco, m.Comp, m.Int );
+ end;
+ end;
+ end;
+ GetHora( h2 );
+ m.Tiem := GetTiempo( h1, h2 );
+ end; { procedure ShellSortMej }
+
+ (*********************************************************)
+
+ procedure QuickSort( var arch: text; var datos: TABLA; tam: integer; var m: MEDICION );
+
+ procedure QSort( var datos: TABLA; min, max: integer;
+ var comp: longint; var int: longint );
+
+ var
+ i, j: integer;
+ sel: PERSONA;
+ flag: boolean;
+
+ begin
+ sel := datos[( min + max ) div 2];
+ i := min;
+ j := max;
+ repeat
+ comp := comp + 1;
+ Retardar( RETARDO );
+ flag := false;
+ while datos[i].ap > sel.ap do
+ begin
+ if flag then begin
+ comp := comp + 1;
+ Retardar( RETARDO );
+ end
+ else flag := true;
+ i := i + 1;
+ end;
+ comp := comp + 1;
+ Retardar( RETARDO );
+ flag := false;
+ while datos[j].ap < sel.ap do
+ begin
+ if flag then begin
+ comp := comp + 1;
+ Retardar( RETARDO );
+ end
+ else flag := true;
+ j := j - 1;
+ end;
+ if i <= j then
+ begin
+ if i < j then Intercambiar( datos[i], datos[j], int );
+ i := i + 1;
+ j := j - 1;
+ end;
+ until i > j;
+ if min < j then QSort( datos, min, j, comp, int);
+ if i < max then QSort( datos, i, max, comp, int);
+ end; { procedure QSort }
+
+ (*********************************************************)
+
+ var
+ h1, h2: HORA;
+
+ begin { procedure QuickSort }
+ GetHora( h1 );
+ m.Comp := 0;
+ m.Int := 0;
+ reset( arch );
+ CargarTabla( arch, datos, 1000 );
+ close( arch );
+ QSort( datos, 1, 1000, m.Comp, m.Int );
+ GetHora( h2 );
+ m.Tiem := GetTiempo( h1, h2 );
+ end; { procedure QuickSort }
+
+ (*********************************************************)
+
+ begin { procedure EvaluarDec }
+ if ExisteArchivo( 'DATOS.TXT' ) then
+ begin
+ BubbleSort( arch, datos, 1000, bs );
+ BubbleSortMej( arch, datos, 1000, bsm );
+ ShakeSort( arch, datos, 1000, shs );
+ RippleSort( arch, datos, 1000, rs );
+ SelectionSort( arch, datos, 1000, ss );
+ InsertionSort( arch, datos, 1000, is );
+ ShellSort( arch, datos, 1000, sls );
+ ShellSortMej( arch, datos, 1000, slsm );
+ QuickSort( arch, datos, 1000, qs );
+ CrearInforme( DECRECIENTE );
+ end
+ else
+ NoExisteArch;
+ end; { procedure EvaluarDec }
+
+ (*********************************************************)
+
+ var { procedure MenuEvaluar }
+ tecla: char;
+
+ begin
+ clrscr;
+ textcolor( Yellow );
+ gotoxy( 19, 3 );
+ writeln( 'COMPARACION DE ALGORITMOS DE ORDENAMIENTO' );
+ gotoxy( 19, 4 );
+ writeln( '~~~~~~~~~~~ ~~ ~~~~~~~~~~ ~~ ~~~~~~~~~~~~' );
+ textcolor( LightCyan );
+ gotoxy( 1, 7 );
+ writeln( ' Evaluar Algoritmos:' );
+ writeln( ' ------- ----------' );
+ textcolor( LightGray );
+ writeln;
+ writeln;
+ writeln( ' 1.- Ordenando en forma creciente.' );
+ writeln( ' 2.- Ordenando en forma decreciente.' );
+ writeln( ' 0.- Men£ Anterior.' );
+ gotoxy( 1, 20 );
+ textcolor( White );
+ write( ' Ingrese su opci¢n: ' );
+ textcolor( Yellow );
+ tecla := readkey;
+ while ( ( tecla < '1' ) or ( tecla > '2' ) ) and ( tecla <> '0' ) do
+ begin
+ textcolor( White );
+ gotoxy( 1, 20 );
+ write( ' Ingrese su opci¢n (1, 2 o 0): ' );
+ textcolor( Yellow );
+ tecla := readkey;
+ end;
+ case tecla of
+ '1': if ExisteArchivo( 'DATOS.TXT' ) then EvaluarCre( datos, arch )
+ else NoExisteArch;
+ '2': if ExisteArchivo( 'DATOS.TXT' ) then EvaluarDec( datos, arch )
+ else NoExisteArch;
+ '0': ;
+ end;
+ end;
+
+(*********************************************************)
+(*********************************************************)
+
+ procedure MenuGenerar( var arch: text );
+
+ type
+ TIPO_LETRA = ( TL_VOCAL, TL_CONSO );
+ TIPO_VOCAL = ( TV_AEIOU, TV_EI );
+ INDICADOR = ( I_NADA, I_ESB, I_ESC, I_ESF, I_ESG, I_ESL, I_ESM, I_ESN, I_ESQ, I_ESQU, I_ESR, I_EST );
+
+ (*********************************************************)
+
+ function GetRNDApellido( max, min: integer ): APELLIDO;
+
+ (*********************************************************)
+
+ function GetVocal( tipo: TIPO_VOCAL ): char;
+
+ var
+ valor: integer;
+
+ begin
+ if tipo = TV_AEIOU then valor := random( 16 )
+ else valor := random( 6 ) + 5;
+ case valor of
+ 0..4: GetVocal := 'A';
+ 5..7: GetVocal := 'E';
+ 8..10: GetVocal := 'I';
+ 11..13: GetVocal := 'O';
+ 14..15: GetVocal := 'U';
+ end;
+ end; { function GetVocal }
+
+ (*********************************************************)
+
+ procedure GetRNDVocal( var indic: INDICADOR; var proxl: TIPO_LETRA; var vocal: char );
+
+ var
+ valor: integer;
+
+ begin
+ case indic of
+ I_ESQ:
+ begin
+ vocal := 'U';
+ indic := I_ESQU;
+ proxl := TL_VOCAL;
+ end;
+ I_ESQU:
+ begin
+ vocal := GetVocal( TV_EI );
+ indic := I_NADA;
+ proxl := TL_CONSO;
+ end;
+ else
+ begin
+ vocal := GetVocal( TV_AEIOU );
+ indic := I_NADA;
+ if random( 40 ) = 0 then proxl := TL_VOCAL
+ else proxl := TL_CONSO;
+ end;
+ end;
+ end; { procedure GetRNDVocal }
+
+ (*********************************************************)
+
+ procedure GetRNDConsonante( var indic: INDICADOR; var proxl: TIPO_LETRA; var conso: char );
+
+ var
+ valor: integer;
+
+ begin
+ proxl := TL_VOCAL;
+ indic := I_NADA;
+
+ case indic of
+ I_ESF, I_ESR, I_ESG, I_EST: conso := 'R';
+ I_ESB: case random( 2 ) of
+ 0: conso := 'R';
+ 1: conso := 'L';
+ end;
+ I_ESC: case random( 4 ) of
+ 0: conso := 'C';
+ 1: conso := 'H';
+ 2: conso := 'R';
+ 3: conso := 'L';
+ end;
+ I_ESL: case random( 6 ) of
+ 0: conso := 'T';
+ 1..5: conso := 'L';
+ end;
+ I_ESM: case random( 3 ) of
+ 0: conso := 'P';
+ 1: conso := 'B';
+ 2: conso := 'L';
+ end;
+ I_ESN: case random( 3 ) of
+ 0: conso := 'R';
+ 1: conso := 'V';
+ 2: conso := 'C';
+ end;
+ else case random( 55 ) of
+ 0..3: begin
+ conso := 'B';
+ if random( 10 ) = 0 then begin
+ indic := I_ESB;
+ proxl := TL_CONSO;
+ end;
+ end;
+ 4..7: begin
+ conso := 'C';
+ if random( 5 ) = 0 then begin
+ indic := I_ESC;
+ proxl := TL_CONSO;
+ end;
+ end;
+ 8..11: conso := 'D';
+ 12..14: begin
+ conso := 'F';
+ if random( 10 ) = 0 then begin
+ indic := I_ESF;
+ proxl := TL_CONSO;
+ end;
+ end;
+ 15..17: begin
+ conso := 'G';
+ if random( 5 ) = 0 then
+ begin
+ indic := I_ESG;
+ if random( 4 ) = 0 then proxl := TL_CONSO;
+ end;
+ end;
+ 18..19: conso := 'H';
+ 20..22: conso := 'J';
+ 23..24: conso := 'K';
+ 25..27: begin
+ conso := 'L';
+ if random( 15 ) = 0 then
+ begin
+ indic := I_ESL;
+ proxl := TL_CONSO;
+ end;
+ end;
+ 28..30: begin
+ conso := 'M';
+ if random( 5 ) = 0 then
+ begin
+ indic := I_ESM;
+ proxl := TL_CONSO;
+ end;
+ end;
+ 31..33: begin
+ conso := 'N';
+ if random( 5 ) = 0 then
+ begin
+ indic := I_ESN;
+ proxl := TL_CONSO;
+ end;
+ end;
+ 34..36: conso := 'P';
+ 37..38: begin
+ conso := 'Q';
+ indic := I_ESQ;
+ end;
+ 39..41: begin
+ conso := 'R';
+ if random( 3 ) = 0 then
+ begin
+ indic := I_ESR;
+ proxl := TL_CONSO;
+ end;
+ end;
+ 42..44: conso := 'S';
+ 45..47: begin
+ conso := 'T';
+ if random( 10 ) = 0 then
+ begin
+ indic := I_EST;
+ proxl := TL_CONSO;
+ end;
+ end;
+ 48..50: conso := 'V';
+ 51: conso := 'W';
+ 52: conso := 'X';
+ 53: conso := 'Y';
+ 54: conso := 'Z';
+ end; { case random( 55 ) of }
+
+ end; { case indic of }
+ end; { procedure GetRNDConsonante }
+
+ (*********************************************************)
+
+ var { function GetRNDApellido }
+ tam, i: integer;
+ aux: char;
+ apel: APELLIDO;
+ indic: INDICADOR;
+ proxl: TIPO_LETRA;
+
+ begin
+ if max > MAX_APE then max := MAX_APE;
+ tam := random( max + 1 ) + min;
+ indic := I_NADA;
+ apel := '';
+ if random( 5 ) = 0 then proxl := TL_VOCAL
+ else proxl := TL_CONSO;
+ for i := 1 to tam do
+ begin
+ if proxl = TL_CONSO then GetRNDConsonante( indic, proxl, aux )
+ else GetRNDVocal( indic, proxl, aux );
+ apel := apel + aux;
+ end;
+ GetRNDApellido := apel;
+ end; { function GetRNDApellido }
+
+ (*********************************************************)
+
+ function GetRNDLetra( min, max: char ): char;
+
+ begin
+ GetRNDLetra := chr( random( ord( max ) - ord( min ) + 1 ) + ord( min ) );
+ end;
+
+ (*********************************************************)
+
+ procedure GetOrdApellidos( var ar: text; cant: integer );
+
+ var
+ mil: boolean;
+ letra, letra1: char;
+ i, j, veces: integer;
+ dni: DOCUMENTO;
+ ap, ape, apel: APELLIDO;
+
+ begin
+ mil := false;
+ if cant = 1000 then mil := true;
+ dni := 10000000 + (random( 15000 ) * 100);
+ ap := '';
+ ape := '';
+ apel := '';
+ for letra := 'A' to 'Z' do
+ begin
+ ap := letra;
+ for letra1 := 'A' to 'Z' do
+ begin
+ if mil then
+ case letra of
+ 'A', 'B', 'C', 'E', 'L', 'M', 'N', 'O', 'P', 'R', 'S', 'T':
+ case letra1 of
+ 'A', 'B', 'C', 'E', 'L', 'M', 'N', 'O', 'P', 'R', 'S', 'T', 'Z': veces := 2;
+ else veces := 1;
+ end;
+ else case letra1 of
+ 'A', 'B', 'C', 'E', 'L', 'M', 'N', 'O', 'P', 'R', 'S', 'T': veces := 2;
+ else veces := 1;
+ end;
+ end
+ else
+ case letra of
+ 'A', 'B', 'C', 'D', 'E', 'F', 'I', 'L', 'M', 'N', 'O', 'P', 'R', 'S', 'T', 'V':
+ case letra1 of
+ 'D', 'F', 'G', 'H', 'I', 'J', 'K', 'U', 'V': veces := 2;
+ else veces := 1;
+ end;
+ else case letra1 of
+ 'D', 'F', 'G', 'H', 'I', 'J', 'K', 'U': veces := 2;
+ else veces := 1;
+ end;
+ end;
+ ape := ap + letra1;
+ for j := 1 to veces do
+ begin
+ if j = 1 then apel := ape + GetRNDLetra( 'A', 'M' ) + GetRNDApellido( 6, 1 )
+ else apel := ape + GetRNDLetra( 'N', 'Z' ) + GetRNDApellido( 6, 1 );
+ dni := dni + random( 50000 ) + 1;
+ writeln( ar, apel );
+ apel := '';
+ end;
+
+ ape := '';
+
+ end; { for letra1 := 'A' to 'Z' do }
+
+ ap := '';
+
+ end; { for letra := 'A' to 'Z' do }
+
+ end; { procedure GetOrdApellidos }
+
+ (*********************************************************)
+
+ procedure GetInvOrdApellidos( var ar: text; cant: integer );
+
+ var
+ mil: boolean;
+ letra, letra1: char;
+ i, j, veces: integer;
+ dni: DOCUMENTO;
+ ap, ape, apel: APELLIDO;
+
+ begin
+ mil := false;
+ if cant = 1000 then mil := true;
+ dni := 34000000 + (random( 15000 ) * 100);
+ ap := '';
+ ape := '';
+ apel := '';
+ for letra := 'Z' downto 'A' do
+ begin
+ ap := letra;
+ for letra1 := 'Z' downto 'A' do
+ begin
+ if mil then
+ case letra of
+ 'A', 'B', 'C', 'E', 'L', 'M', 'N', 'O', 'P', 'R', 'S', 'T':
+ case letra1 of
+ 'A', 'B', 'C', 'E', 'L', 'M', 'N', 'O', 'P', 'R', 'S', 'T', 'Z': veces := 2;
+ else veces := 1;
+ end;
+ else case letra1 of
+ 'A', 'B', 'C', 'E', 'L', 'M', 'N', 'O', 'P', 'R', 'S', 'T': veces := 2;
+ else veces := 1;
+ end;
+ end
+ else
+ case letra of
+ 'A', 'B', 'C', 'D', 'E', 'F', 'I', 'L', 'M', 'N', 'O', 'P', 'R', 'S', 'T', 'V':
+ case letra1 of
+ 'D', 'F', 'G', 'H', 'I', 'J', 'K', 'U', 'V': veces := 2;
+ else veces := 1;
+ end;
+ else case letra1 of
+ 'D', 'F', 'G', 'H', 'I', 'J', 'K', 'U': veces := 2;
+ else veces := 1;
+ end;
+ end;
+ ape := ap + letra1;
+ for j := 1 to veces do
+ begin
+ if j <> 1 then apel := ape + GetRNDLetra( 'A', 'M' ) + GetRNDApellido( 6, 1 )
+ else apel := ape + GetRNDLetra( 'N', 'Z' ) + GetRNDApellido( 6, 1 );
+ dni := dni - random( 40000 ) - 1;
+ writeln( ar, apel );
+ apel := '';
+ end;
+
+ ape := '';
+
+ end; { for letra1 := 'A' to 'Z' do }
+
+ ap := '';
+
+ end; { for letra := 'A' to 'Z' do }
+
+ end; { GetInvOrdApellidos }
+
+
+ (*********************************************************)
+
+ procedure GenerarRND( var arch: text; n: longint; reabrir: boolean );
+
+ var
+ i: integer;
+ ap: APELLIDO;
+
+ begin
+ if reabrir then rewrite( arch );
+
+ for i := 1 to n do
+ begin
+ ap := GetRNDApellido( 30, 4 );
+ writeln( arch, ap );
+ end;
+ if reabrir then close( arch );
+ end; { procedure GenerarRND }
+
+ (*********************************************************)
+
+ procedure GenerarOrd( var arch: text; n: integer; reabrir: boolean );
+
+ begin
+ if reabrir then rewrite( arch );
+ GetOrdApellidos( arch, n );
+ if reabrir then close( arch );
+ end;
+
+ (*********************************************************)
+
+ procedure GenerarOrdDec( var arch: text; n: integer; reabrir: boolean );
+
+ begin
+ if reabrir then rewrite( arch );
+ GetInvOrdApellidos( arch, n );
+ if reabrir then close( arch );
+ end;
+
+ (*********************************************************)
+
+ procedure Generar90Ord( var arch: text );
+
+ begin
+ rewrite( arch );
+ GenerarOrd( arch, 900, false );
+ GenerarRND( arch, 100, false );
+ close( arch );
+ end;
+
+ (*********************************************************)
+
+ procedure Generar90OrdDec( var arch: text );
+
+ begin
+ rewrite( arch );
+ GenerarOrdDec( arch, 900, false );
+ GenerarRND( arch, 100, false );
+ close( arch );
+ end;
+
+ (*********************************************************)
+
+ var { procedure MenuGenerar }
+ tecla: char;
+
+ begin
+ clrscr;
+ textcolor( Yellow );
+ gotoxy( 19, 3 );
+ writeln( 'COMPARACION DE ALGORITMOS DE ORDENAMIENTO' );
+ gotoxy( 19, 4 );
+ writeln( '~~~~~~~~~~~ ~~ ~~~~~~~~~~ ~~ ~~~~~~~~~~~~' );
+ textcolor( LightCyan );
+ gotoxy( 1, 7 );
+ writeln( ' Generar Archivo (''DATOS.TXT''):' );
+ writeln( ' ------- ------- -------------' );
+ textcolor( LightGray );
+ writeln;
+ writeln;
+ writeln( ' 1.- Con datos desordenados.' );
+ writeln( ' 2.- Con datos en orden creciente (APELLIDO, DNI).' );
+ writeln( ' 3.- Con datos en orden decreciente (APELLIDO, DNI).' );
+ writeln( ' 4.- Con 90% datos en orden creciente (APELLIDO, DNI) + 10% desordenado.' );
+ writeln( ' 5.- Con 90% datos en orden decreciente (APELLIDO, DNI) + 10% desordenado.' );
+ writeln( ' 0.- Men£ Anterior.' );
+ gotoxy( 1, 20 );
+ textcolor( White );
+ write( ' Ingrese su opci¢n: ' );
+ textcolor( Yellow );
+ tecla := readkey;
+ while ( ( tecla < '1' ) or ( tecla > '5' ) ) and ( tecla <> '0' ) do
+ begin
+ textcolor( White );
+ gotoxy( 1, 20 );
+ write( ' Ingrese su opci¢n (1 a 5 o 0): ' );
+ textcolor( Yellow );
+ tecla := readkey;
+ end;
+ case tecla of
+ '1': GenerarRND( arch, 1000000, true );
+ '2': GenerarOrd( arch, 1000, true );
+ '3': GenerarOrdDec( arch, 1000, true );
+ '4': Generar90Ord( arch );
+ '5': Generar90OrdDec( arch );
+ '0': ;
+ end;
+ end; { procedure MenuGenerar }
+
+(*********************************************************)
+
+ procedure PantallaSalida;
+
+ begin
+ writeln;
+ NormVideo;
+ clrscr;
+ writeln;
+ textcolor( white );
+ writeln( ' COMPARACION DE ALGORITMOS DE ORDENAMIENTO versi¢n ', VERSION, ' <-o-o-> Luca - Soft' );
+ NormVideo;
+ writeln( ' Desarrollado por Leandro Lucarella para la Facultad de Ingenier¡a de la' );
+ writeln( ' Universidad de Buenos Aires. Consultas, sugerencias y/o reprobaciones a:' );
+ writeln;
+ textcolor( LightMagenta );
+ write( ' lluca@cnba.uba.ar' );
+ NormVideo;
+ write( ' o ' );
+ textcolor( LightMagenta );
+ writeln( 'lluca@geocities.com' );
+ NormVideo;
+ writeln;
+ writeln( ' (c) 1999 - Todos los derechos reservados.' );
+ delay( 750 );
+ end;
+
+(*********************************************************)
+
+var { programa }
+ datos: TABLA;
+ arch: text;
+ tecla: char;
+ salir: boolean;
+
+begin
+ randomize;
+ assign( arch, 'DATOS.TXT' );
+ salir := false;
+ textbackground( Blue );
+
+ while not salir do
+ begin
+ clrscr;
+ textcolor( Yellow );
+ gotoxy( 19, 3 );
+ writeln( 'COMPARACION DE ALGORITMOS DE ORDENAMIENTO' );
+ gotoxy( 19, 4 );
+ writeln( '~~~~~~~~~~~ ~~ ~~~~~~~~~~ ~~ ~~~~~~~~~~~~' );
+ gotoxy( 1, 7 );
+ textcolor( LightCyan );
+ writeln( ' Men£ Principal:' );
+ writeln( ' ---- ---------' );
+ textcolor( LightGray );
+ writeln;
+ writeln;
+ writeln( ' 1.- Generar Archivo (''DATOS.TXT'').' );
+ writeln( ' 2.- Evaluar Algoritmos.' );
+ writeln( ' 0.- Salir.' );
+ gotoxy( 1, 20 );
+ textcolor( White );
+ write( ' Ingrese su opci¢n: ' );
+ textcolor( Yellow );
+ tecla := readkey;
+ while ( ( tecla < '1' ) or ( tecla > '2' ) ) and ( tecla <> '0' ) do
+ begin
+ textcolor( White );
+ gotoxy( 1, 20 );
+ write( ' Ingrese su opci¢n (1, 2 o 0): ' );
+ textcolor( Yellow );
+ tecla := readkey;
+ end;
+ case tecla of
+ '1': MenuGenerar( arch );
+ '2': MenuEvaluar( datos, arch );
+ '0': salir := true;
+ end;
+ end;
+ PantallaSalida;
+end.
\ No newline at end of file
--- /dev/null
+/* Filename: extsort.cpp
+
+ Programmer: Br. David Carlson
+
+ Date: April 18, 2003
+
+ This program does a case-insensitive sort of the text file that the user supplies
+ when prompted by the program. It is assumed that each line of the file contains a
+ word and is no more than 31 characters in length. No attempt is made to order in any
+ way words that are identical except for capitalization. (For example, there is no
+ guarantee what order the sort will place the words MacIntosh and Macintosh since
+ they are seen as identical. Duplicate words such as these are kept in the file.)
+ The output data is placed back under the original file name.
+
+ Tested with:
+ Microsoft Visual C++ 6.0
+ Microsoft Visual C++ .NET
+ This program will not work as is with g++ under Linux due to its use of items such as
+ the constant _MAX_PATH as well as the functions _itoa, and stricmp.
+*/
+
+#include "extsort.h"
+#include <sstream>
+
+void _itoa(int n, char* ext, int size)
+{
+ std::ostringstream oss;
+ oss << n;
+ strncpy(ext, oss.str().c_str(), size);
+}
+
+int main(void)
+ {
+ PathType FileName;
+ fstream DataFile;
+ int NumRuns;
+
+ cout << "Enter the name of the text file to be sorted: ";
+ cin.getline(FileName, _MAX_PATH);
+
+ DataFile.open(FileName, ios::in);
+ if (DataFile.fail())
+ Error("Could not open the file named ", FileName);
+
+ // Copy sections of the data file into sorted runs.
+ NumRuns = MakeSortedRuns(DataFile, FileName);
+ DataFile.close();
+
+ // Merge the sorted runs until all of the data is in one sorted file (under the original FileName).
+ HandleMerges(NumRuns, FileName);
+
+ return 0;
+ }
+
+
+/* Given: DataFile A text file stream already opened for input.
+ FileName The name of this text file (as a char array string).
+ Task: To copy data from this file stream into sorted files (runs).
+ Return: DataFile The modified file stream is trivially modified by reading from it.
+ In the function name the number of runs is returned.
+ The sorted runs themselves are created and stored under the file names:
+ ExtSortTemp.0, ExtSortTemp.1, etc.
+*/
+int MakeSortedRuns(fstream & DataFile, PathType FileName)
+ {
+ fstream OutFile;
+ StringType Word, Extension;
+ PathType OutFileName;
+ int NumWords, k, NumFiles = 0;
+ BufType Buffer;
+ bool MoreData;
+
+ // Repeatedly fill one buffer and quicksort it, writing the buffer out to a temp file.
+ DataFile.getline(Word, MaxString);
+ if (DataFile.fail())
+ MoreData = false;
+ else
+ MoreData = true;
+
+ while (MoreData)
+ {
+ // Fill one buffer.
+ NumWords = FillBuffer(DataFile, Buffer, MoreData, Word);
+ QuickSort(Buffer, 0, NumWords - 1);
+
+ // Construct the temp file name.
+ strcpy(OutFileName, "ExtSortTemp.");
+ _itoa(NumFiles, Extension, 10); // Convert the int in NumFiles to a char array string.
+ strcat(OutFileName, Extension);
+
+ OutFile.open(OutFileName, ios::out);
+ if (OutFile.fail())
+ Error("Could not open the file named ", OutFileName);
+
+ for (k = 0; k < NumWords; k++)
+ OutFile << Buffer[k] << endl;
+
+ #ifdef DEBUG
+ OutFile.seekp(0, ios_base::end);
+ cout << "Tamaño del archivo '" << OutFileName << "': " << OutFile.tellp() / 1024 << " KB\n";
+ #endif
+ OutFile.close();
+ NumFiles++;
+ }
+
+ return NumFiles;
+ }
+
+
+/* Given: NumFiles Number of sorted runs (files) to be merged.
+ FileName The name of the text file to contain the merged data.
+ Indirectly this function is also given the sorted runs, which are assumed to be
+ files named ExtSortTemp.0, ExtSortTemp.1, etc.
+ Task: To merge the data from these sorted runs into one combined, sorted file with
+ the name given by FileName.
+ Return: Nothing directly, but the file named by FileName is modified (by being sorted).
+*/
+void HandleMerges(int NumFiles, PathType FileName)
+ {
+ StringType Extension;
+ PathType OutFileName, InFileName1, InFileName2;
+ int k, NumPairs, Count;
+ bool Odd;
+
+ // Repeatedly merge 2 runs, writing data to a new temp file (but write last one to original file).
+ if (NumFiles == 0) // No data is present, so there is no work to do.
+ return;
+ else if (NumFiles == 1)
+ {
+ // Remove original file and rename the temp file using name of the original.
+ remove(FileName);
+ rename("ExtSortTemp.0", FileName);
+
+ #ifdef DEBUG
+ cout << "Renaming ExtSortTemp.0 as " << FileName << endl;
+ #endif
+
+ return; // The sort is finished.
+ }
+ else if (NumFiles == 2)
+ {
+ // Merge the 2 sorted temp files into original file.
+ Merge("ExtSortTemp.0", "ExtSortTemp.1", FileName);
+ remove("ExtSortTemp.0");
+ remove("ExtSortTemp.1");
+ return; // The sort is finished.
+ }
+ else // We have 3 or more files.
+ {
+ // Merge temp files, 2 at a time, until only 2 remain, then proceed as in last case.
+ while (NumFiles > 2)
+ {
+ // Merge ExtSortTemp.0 and ExtSortTemp.1 into ExtSortTempA.0,
+ // merge ExtSortTemp.2 and ExtSortTemp.3 into ExtSortTempA.1, etc.
+ NumPairs = NumFiles / 2;
+ for (k = 0, Count = 0; k < NumPairs; k++)
+ {
+ strcpy(InFileName1 , "ExtSortTemp.");
+ _itoa(Count++, Extension, 10);
+ strcat(InFileName1, Extension);
+ strcpy(InFileName2 , "ExtSortTemp.");
+ _itoa(Count++, Extension, 10);
+ strcat(InFileName2, Extension);
+ strcpy(OutFileName , "ExtSortTempA.");
+ _itoa(k, Extension, 10);
+ strcat(OutFileName, Extension);
+ Merge(InFileName1, InFileName2, OutFileName);
+ }
+ // If the number of files is odd, just rename the last one.
+ if (2 * NumPairs < NumFiles)
+ {
+ Odd = true;
+ strcpy(InFileName1 , "ExtSortTemp.");
+ _itoa(Count, Extension, 10);
+ strcat(InFileName1, Extension);
+ strcpy(OutFileName , "ExtSortTempA.");
+ _itoa(NumPairs, Extension, 10);
+ strcat(OutFileName, Extension);
+ rename(InFileName1, OutFileName);
+
+ #ifdef DEBUG
+ cout << "Renaming " << InFileName1 << " as " << OutFileName << endl;
+ #endif
+ }
+ else
+ Odd = false;
+
+ // Remove the temp files from before the merge.
+ for (k = 0; k < NumFiles; k++)
+ {
+ strcpy(InFileName1 , "ExtSortTemp.");
+ _itoa(k, Extension, 10);
+ strcat(InFileName1, Extension);
+ remove(InFileName1);
+ }
+
+ // Get the new number of sorted files.
+ NumFiles = NumPairs;
+ if (Odd)
+ NumFiles++;
+
+ // If number of ExtSortTempA files is now 2, merge them with output to original file and return.
+ if (NumFiles == 2)
+ {
+ Merge("ExtSortTempA.0", "ExtSortTempA.1", FileName);
+ remove("ExtSortTempA.0");
+ remove("ExtSortTempA.1");
+ return; // The sort is finished.
+ }
+
+ // Otherwise, merge pairs of files as above, but start at the top end so as to
+ // incorporate any small remainder file. Note that we now merge from the
+ // ExtSortTempA files into ExtSortTemp files.
+ NumPairs = NumFiles / 2;
+ for (k = 0, Count = NumFiles - 1; k < NumPairs; k++)
+ {
+ strcpy(InFileName1 , "ExtSortTempA.");
+ _itoa(Count--, Extension, 10);
+ strcat(InFileName1, Extension);
+ strcpy(InFileName2 , "ExtSortTempA.");
+ _itoa(Count--, Extension, 10);
+ strcat(InFileName2, Extension);
+ strcpy(OutFileName , "ExtSortTemp.");
+ _itoa(k, Extension, 10);
+ strcat(OutFileName, Extension);
+ Merge(InFileName1, InFileName2, OutFileName);
+ }
+ // If the number of files is odd, just rename the last one.
+ if (2 * NumPairs < NumFiles)
+ {
+ Odd = true;
+ strcpy(InFileName1 , "ExtSortTempA.");
+ _itoa(0, Extension, 10);
+ strcat(InFileName1, Extension);
+ strcpy(OutFileName , "ExtSortTemp.");
+ _itoa(NumPairs, Extension, 10);
+ strcat(OutFileName, Extension);
+ rename(InFileName1, OutFileName);
+
+ #ifdef DEBUG
+ cout << "Renaming " << InFileName1 << " as " << OutFileName << endl;
+ #endif
+ }
+ else
+ Odd = false;
+
+ // Remove the temp files from before the merge.
+ for (k = 0; k < NumFiles; k++)
+ {
+ strcpy(InFileName1 , "ExtSortTempA.");
+ _itoa(k, Extension, 10);
+ strcat(InFileName1, Extension);
+ remove(InFileName1);
+ }
+
+ // Get the new number of sorted files.
+ NumFiles = NumPairs;
+ if (Odd)
+ NumFiles++;
+
+ // If number of ExtSortTemp files is now 2, merge them with output to original file and return.
+ if (NumFiles == 2)
+ {
+ Merge("ExtSortTemp.0", "ExtSortTemp.1", FileName);
+ remove("ExtSortTemp.0");
+ remove("ExtSortTemp.1");
+ return; // The sort is finished.
+ }
+ }
+ }
+ }
+
+
+/* Given: InFile Text file stream already opened for input.
+ MoreData Indicates if there is more data from InFile to place into Buffer.
+ At the very least this indicates if there is an unused item in NextWord.
+ NextWord If MoreData is true, then NextWord contains an unprocessed word from
+ InFile that has yet to be placed into Buffer.
+ Task: If MoreData is true, this function places as much data as possible from InFile into
+ Buffer. This data includes NextWord and then as much new data as possible from InFile.
+ The Buffer will be filled if there is enough data to do so.
+ Return: In the function name is returned the number of words placed into Buffer.
+ InFile The modified file stream.
+ Buffer Contains the data that has been copied in from InFile.
+ MoreData Indicates if NextWord contains a word that has not yet been placed into Buffer.
+ NextWord If MoreData is true, this contains the next word from InFile that has
+ not yet been placed into Buffer.
+*/
+int FillBuffer(fstream & InFile, BufType Buffer, bool & MoreData, StringType NextWord)
+ {
+ int k = 0;
+
+ while (MoreData && (k < BufSize))
+ {
+ strcpy(Buffer[k], NextWord);
+ InFile.getline(NextWord, MaxString);
+ if (InFile.fail())
+ MoreData = false;
+ else
+ MoreData = true;
+ k++;
+ }
+
+ return k;
+ }
+
+
+/* Given: InFileName1 The name of the first text file to be merged.
+ InFileName2 The name of the second text file to be merged.
+ OutFileName The name of the file in which to place the merged data.
+ Task: To merge the sorted text files named InFileName1 and InFileName2 into one
+ named by OutFileName.
+ Return: Nothing directly, but the text file named by OutFileName is created and filled
+ with the sorted data from InFileName1 and InFileName2.
+*/
+void Merge(StringType InFileName1, StringType InFileName2, StringType OutFileName)
+ {
+ fstream InFile1, InFile2, OutFile;
+ BufType Buffer1, Buffer2, Buffer3;
+ bool HaveData1, HaveData2, MoreData1, MoreData2;
+ StringType NextWord1, NextWord2;
+ int k, Result, NumWords1, NumWords2, Index1, Index2, Index3 = 0;
+
+ InFile1.open(InFileName1, ios::in);
+ if (InFile1.fail())
+ Error("Could not open the file named ", InFileName1);
+
+ InFile2.open(InFileName2, ios::in);
+ if (InFile2.fail())
+ Error("Could not open the file named ", InFileName2);
+
+ OutFile.open(OutFileName, ios::out);
+ if (OutFile.fail())
+ Error("Could not open the file named ", OutFileName);
+
+ #ifdef DEBUG
+ cout << "Merging " << InFileName1 << " and " << InFileName2 << " to " << OutFileName << endl;
+ #endif
+
+ // Try to fill a buffer from InFile1.
+ InFile1.getline(NextWord1, MaxString);
+ if (InFile1.fail())
+ MoreData1 = false;
+ else
+ {
+ MoreData1 = true;
+ NumWords1 = FillBuffer(InFile1, Buffer1, MoreData1, NextWord1);
+ }
+
+ // Try to fill a buffer from InFile2.
+ InFile2.getline(NextWord2, MaxString);
+ if (InFile2.fail())
+ MoreData2 = false;
+ else
+ {
+ MoreData2 = true;
+ NumWords2 = FillBuffer(InFile2, Buffer2, MoreData2, NextWord2);
+ }
+
+ Index1 = 0;
+ Index2 = 0;
+ // Each HaveData boolean indicates if we have more unmerged data. This data could be in
+ // the corresponding NextWord variable, the corresponding Buffer, or both.
+ HaveData1 = MoreData1 || (Index1 < NumWords1);
+ HaveData2 = MoreData2 || (Index2 < NumWords2);
+
+ while (HaveData1 && HaveData2)
+ {
+ if (Index1 == NumWords1)
+ {
+ NumWords1 = FillBuffer(InFile1, Buffer1, MoreData1, NextWord1);
+ if (NumWords1 == 0)
+ break; // We are out of data from InFile1.
+ else
+ Index1 = 0;
+ }
+ if (Index2 == NumWords2)
+ {
+ NumWords2 = FillBuffer(InFile2, Buffer2, MoreData2, NextWord2);
+ if (NumWords2 == 0)
+ break; // We are out of data from InFile2.
+ else
+ Index2 = 0;
+ }
+
+ Result = strcmp(Buffer1[Index1], Buffer2[Index2]); // case insensitive compare
+
+ if (Result == 0) // Copy both data items.
+ {
+ Copy(Buffer1[Index1], Buffer3, Index3, OutFile);
+ Copy(Buffer2[Index2], Buffer3, Index3, OutFile);
+ Index1++;
+ Index2++;
+ }
+ else if (Result < 0) // Copy the first data item.
+ {
+ Copy(Buffer1[Index1], Buffer3, Index3, OutFile);
+ Index1++;
+ }
+ else // Result > 0, so copy the second data item.
+ {
+ Copy(Buffer2[Index2], Buffer3, Index3, OutFile);
+ Index2++;
+ }
+
+ HaveData1 = MoreData1 || (Index1 < NumWords1);
+ HaveData2 = MoreData2 || (Index2 < NumWords2);
+ }
+
+ // Handle remaining data in either file.
+ while (HaveData1)
+ {
+ if (Index1 == NumWords1)
+ {
+ NumWords1 = FillBuffer(InFile1, Buffer1, MoreData1, NextWord1);
+ if (NumWords1 == 0)
+ break; // We are out of data from InFile1.
+ else
+ Index1 = 0;
+ }
+
+ Copy(Buffer1[Index1], Buffer3, Index3, OutFile);
+ Index1++;
+ HaveData1 = MoreData1 || (Index1 < NumWords1);
+ }
+
+ while (HaveData2)
+ {
+ if (Index2 == NumWords2)
+ {
+ NumWords2 = FillBuffer(InFile2, Buffer2, MoreData2, NextWord2);
+ if (NumWords2 == 0)
+ break; // We are out of data from InFile2.
+ else
+ Index2 = 0;
+ }
+
+ Copy(Buffer2[Index2], Buffer3, Index3, OutFile);
+ Index2++;
+ HaveData2 = MoreData2 || (Index2 < NumWords2);
+ }
+
+ // Flush any remaining data from the output buffer.
+ for (k = 0; k < Index3; k++)
+ OutFile << Buffer3[k] << endl;
+
+ #ifdef DEBUG
+ OutFile.seekp(0, ios_base::end);
+ cout << "Tamaño del archivo '" << OutFileName << "': " << OutFile.tellp() / 1024 << " KB\n";
+ #endif
+ InFile1.close();
+ InFile2.close();
+ OutFile.close();
+ }
+
+
+/* Given: Word One word of data to be placed into Buffer.
+ Buffer A buffer that may already contain words.
+ Index The first unused index in Buffer.
+ OutFile A text file stream already opened for output.
+ Task: To place Word into Buffer. If the Buffer is full, the data
+ already in it is first written out to OutFile, then Word
+ is placed into Buffer as the only item present.
+ Return: Buffer The updated buffer.
+ Index The updated index of the first unused location in Buffer.
+ OutFile The possibly updated file stream.
+*/
+void Copy(StringType Word, BufType Buffer, int & Index, fstream & OutFile)
+ {
+ int k;
+
+ if (Index == BufSize) // There is no room in Buffer, so first write the Buffer data to OutFile.
+ {
+ for (k = 0; k < BufSize; k++)
+ OutFile << Buffer[k] << endl;
+ Index = 0;
+ }
+
+ strcpy(Buffer[Index], Word);
+ Index++;
+ }
+
+
+/* Given: First A char array string.
+ Second Another char array string.
+ Task: To swap these values.
+ Return: First Updated string.
+ Second Updated string.
+*/
+inline void Swap(StringType First, StringType Second)
+ {
+ StringType Temp;
+
+ strcpy(Temp, First);
+ strcpy(First, Second);
+ strcpy(Second, Temp);
+ }
+
+
+/* Given: Buf Array of char array strings
+ Lower An index into the array.
+ Upper An index into the array.
+ Task: To quicksort the section of the array from index Lower to Upper.
+ Return: Buf The sorted array.
+*/
+void QuickSort(BufType Buf, int Lower, int Upper)
+ {
+ int PivotIndex;
+
+ if (Lower < Upper)
+ {
+ PivotIndex = Partition(Buf, Lower, Upper);
+ QuickSort(Buf, Lower, PivotIndex - 1); // sort left side
+ QuickSort(Buf, PivotIndex + 1, Upper); // sort right side
+ }
+ }
+
+
+/* Given: Buf Array of char array strings.
+ Lower An index into the array.
+ Upper An index into the array.
+ Assume: Lower < Upper
+ Task: To partition the section of Buf between index Lower and
+ index Upper so that everything to the left of the returned
+ index is less or equal to the pivot item, which is Buf[Lower],
+ everything to the right of the returned index is greater
+ than the pivot item, and the pivot item itself is located
+ at the returned index.
+ Return: Buf The partitioned array.
+ In the function name this returns the index of the pivot value.
+*/
+int Partition(BufType Buf, int Lower, int Upper)
+ {
+ int Left, Right;
+ StringType Pivot;
+
+ strcpy(Pivot, Buf[Lower]);
+ Left = Lower;
+ Right = Upper;
+
+ while (Left < Right)
+ {
+ // Scan from left, skipping items that belong there. Use case-insensitive compare.
+ while ((strcmp(Buf[Left], Pivot) <= 0) && (Left < Upper))
+ Left++;
+ // Scan from right, skipping items that belong there. Use case-insensitive compare.
+ while (strcmp(Buf[Right], Pivot) > 0)
+ Right--;
+ if (Left < Right)
+ Swap(Buf[Left], Buf[Right]);
+ }
+
+ strcpy(Buf[Lower], Buf[Right]);
+ strcpy(Buf[Right], Pivot);
+ return Right; // return the pivot index
+ }
+
+
+
+/* Given: MsgA, MsgB Two messages (string objects) to display.
+ Task: Display MsgA and MsgB, then exit the program.
+ Return: Nothing to the program, but does return an error code of 1 to the operating system.
+*/
+void Error(const string & MsgA, const string & MsgB)
+ {
+ cerr << "Error: " << MsgA << MsgB << endl;
+ exit(1);
+ }
+
--- /dev/null
+/* Filename: extsort.h
+
+ Programmer: Br. David Carlson
+
+ Date: April 18, 2003
+
+ This header file sets up the constants, types, and function prototypes used by the
+ ExtSort program.
+*/
+
+#include <iostream>
+#include <fstream>
+#include <string>
+using namespace std;
+
+
+// Comment off the following line if you do not want to see debugging information.
+//#define DEBUG
+
+enum { MaxString = 32, BufSize = 2048, _MAX_PATH = 64 };
+
+
+typedef char StringType[MaxString];
+
+typedef StringType BufType[BufSize]; // A buffer will hold 2048 strings, for a total of 64K bytes.
+
+typedef char PathType[_MAX_PATH];
+
+
+void Error(const string & Msg);
+
+void Error(const string & MsgA, const string & MsgB);
+
+int MakeSortedRuns(fstream & DataFile, PathType FileName);
+
+bool LessThan(StringType First, StringType Second);
+
+void QuickSort(BufType Buf, int Lower, int Upper);
+
+void Swap(StringType First, StringType Second);
+
+int Partition(BufType Buf, int Lower, int Upper);
+
+void Merge(StringType InFileName1, StringType InFileName2, StringType OutFileName);
+
+int FillBuffer(fstream & InFile, BufType Buffer, bool & HaveData, StringType NextWord);
+
+void Copy(StringType Word, BufType Buffer, int & Index, fstream & OutFile);
+
+void HandleMerges(int NumFiles, PathType FileName);
+
--- /dev/null
+/* external sort */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+/****************************
+ * implementation dependent *
+ ****************************/
+
+/* template for workfiles (8.3 format) */
+#define FNAME "_sort%03d.dat"
+#define LNAME 13
+
+/* comparison operators */
+#define compLT(x,y) (x < y)
+#define compGT(x,y) (x > y)
+
+/* define the record to be sorted here */
+#define LRECL 100
+typedef int keyType;
+typedef struct recTypeTag {
+ keyType key; /* sort key for record */
+ #if LRECL
+ char data[LRECL-sizeof(keyType)]; /* other fields */
+ #endif
+} recType;
+
+/******************************
+ * implementation independent *
+ ******************************/
+
+typedef enum {false, true} bool;
+
+typedef struct tmpFileTag {
+ FILE *fp; /* file pointer */
+ char name[LNAME]; /* filename */
+ recType rec; /* last record read */
+ int dummy; /* number of dummy runs */
+ bool eof; /* end-of-file flag */
+ bool eor; /* end-of-run flag */
+ bool valid; /* true if rec is valid */
+ int fib; /* ideal fibonacci number */
+} tmpFileType;
+
+static tmpFileType **file; /* array of file info for tmp files */
+static int nTmpFiles; /* number of tmp files */
+static char *ifName; /* input filename */
+static char *ofName; /* output filename */
+
+static int level; /* level of runs */
+static int nNodes; /* number of nodes for selection tree */
+
+void deleteTmpFiles(void) {
+ int i;
+
+ /* delete merge files and free resources */
+ if (file) {
+ for (i = 0; i < nTmpFiles; i++) {
+ if (file[i]) {
+ if (file[i]->fp) fclose(file[i]->fp);
+ if (*file[i]->name) remove(file[i]->name);
+ free (file[i]);
+ }
+ }
+ free (file);
+ }
+}
+
+void termTmpFiles(int rc) {
+
+ /* cleanup files */
+ remove(ofName);
+ if (rc == 0) {
+ int fileT;
+
+ /* file[T] contains results */
+ fileT = nTmpFiles - 1;
+ fclose(file[fileT]->fp); file[fileT]->fp = NULL;
+ if (rename(file[fileT]->name, ofName)) {
+ perror("io1");
+ deleteTmpFiles();
+ exit(1);
+ }
+ *file[fileT]->name = 0;
+ }
+ deleteTmpFiles();
+}
+
+void cleanExit(int rc) {
+
+ /* cleanup tmp files and exit */
+ termTmpFiles(rc);
+ exit(rc);
+}
+
+void *safeMalloc(size_t size) {
+ void *p;
+
+ /* safely allocate memory and initialize to zero */
+ if ((p = calloc(1, size)) == NULL) {
+ printf("error: malloc failed, size = %d\n", size);
+ cleanExit(1);
+ }
+ return p;
+}
+
+void initTmpFiles(void) {
+ int i;
+ tmpFileType *fileInfo;
+
+ /* initialize merge files */
+ if (nTmpFiles < 3) nTmpFiles = 3;
+ file = safeMalloc(nTmpFiles * sizeof(tmpFileType*));
+ fileInfo = safeMalloc(nTmpFiles * sizeof(tmpFileType));
+ for (i = 0; i < nTmpFiles; i++) {
+ file[i] = fileInfo + i;
+ sprintf(file[i]->name, FNAME, i);
+ if ((file[i]->fp = fopen(file[i]->name, "w+b")) == NULL) {
+ perror("io2");
+ cleanExit(1);
+ }
+ }
+}
+
+recType *readRec(void) {
+
+ typedef struct iNodeTag { /* internal node */
+ struct iNodeTag *parent;/* parent of internal node */
+ struct eNodeTag *loser; /* external loser */
+ } iNodeType;
+
+ typedef struct eNodeTag { /* external node */
+ struct iNodeTag *parent;/* parent of external node */
+ recType rec; /* input record */
+ int run; /* run number */
+ bool valid; /* input record is valid */
+ } eNodeType;
+
+ typedef struct nodeTag {
+ iNodeType i; /* internal node */
+ eNodeType e; /* external node */
+ } nodeType;
+
+ static nodeType *node; /* array of selection tree nodes */
+ static eNodeType *win; /* new winner */
+ static FILE *ifp; /* input file */
+ static bool eof; /* true if end-of-file, input */
+ static int maxRun; /* maximum run number */
+ static int curRun; /* current run number */
+ iNodeType *p; /* pointer to internal nodes */
+ static bool lastKeyValid; /* true if lastKey is valid */
+ static keyType lastKey; /* last key written */
+
+ /* read next record using replacement selection */
+
+ /* check for first call */
+ if (node == NULL) {
+ int i;
+
+ if (nNodes < 2) nNodes = 2;
+ node = safeMalloc(nNodes * sizeof(nodeType));
+ for (i = 0; i < nNodes; i++) {
+ node[i].i.loser = &node[i].e;
+ node[i].i.parent = &node[i/2].i;
+ node[i].e.parent = &node[(nNodes + i)/2].i;
+ node[i].e.run = 0;
+ node[i].e.valid = false;
+ }
+ win = &node[0].e;
+ lastKeyValid = false;
+
+ if ((ifp = fopen(ifName, "rb")) == NULL) {
+ printf("error: file %s, unable to open\n", ifName);
+ cleanExit(1);
+ }
+ }
+
+ while (1) {
+
+ /* replace previous winner with new record */
+ if (!eof) {
+ if (fread(&win->rec, sizeof(recType), 1, ifp) == 1) {
+ if ((!lastKeyValid || compLT(win->rec.key, lastKey))
+ && (++win->run > maxRun))
+ maxRun = win->run;
+ win->valid = true;
+ } else if (feof(ifp)) {
+ fclose(ifp);
+ eof = true;
+ win->valid = false;
+ win->run = maxRun + 1;
+ } else {
+ perror("io4");
+ cleanExit(1);
+ }
+ } else {
+ win->valid = false;
+ win->run = maxRun + 1;
+ }
+
+ /* adjust loser and winner pointers */
+ p = win->parent;
+ do {
+ bool swap;
+ swap = false;
+ if (p->loser->run < win->run) {
+ swap = true;
+ } else if (p->loser->run == win->run) {
+ if (p->loser->valid && win->valid) {
+ if (compLT(p->loser->rec.key, win->rec.key))
+ swap = true;
+ } else {
+ swap = true;
+ }
+ }
+ if (swap) {
+ /* p should be winner */
+ eNodeType *t;
+
+ t = p->loser;
+ p->loser = win;
+ win = t;
+ }
+ p = p->parent;
+ } while (p != &node[0].i);
+
+ /* end of run? */
+ if (win->run != curRun) {
+ /* win->run = curRun + 1 */
+ if (win->run > maxRun) {
+ /* end of output */
+ free(node);
+ return NULL;
+ }
+ curRun = win->run;
+ }
+
+ /* output top of tree */
+ if (win->run) {
+ lastKey = win->rec.key;
+ lastKeyValid = true;
+ return &win->rec;
+ }
+ }
+}
+
+void makeRuns(void) {
+ recType *win; /* winner */
+ int fileT; /* last file */
+ int fileP; /* next to last file */
+ int j; /* selects file[j] */
+
+
+ /* Make initial runs using replacement selection.
+ * Runs are written using a Fibonacci distintbution.
+ */
+
+ /* initialize file structures */
+ fileT = nTmpFiles - 1;
+ fileP = fileT - 1;
+ for (j = 0; j < fileT; j++) {
+ file[j]->fib = 1;
+ file[j]->dummy = 1;
+ }
+ file[fileT]->fib = 0;
+ file[fileT]->dummy = 0;
+
+ level = 1;
+ j = 0;
+
+
+ win = readRec();
+ while (win) {
+ bool anyrun;
+
+ anyrun = false;
+ for (j = 0; win && j <= fileP; j++) {
+ bool run;
+
+ run = false;
+ if (file[j]->valid) {
+ if (!compLT(win->key, file[j]->rec.key)) {
+ /* append to an existing run */
+ run = true;
+ } else if (file[j]->dummy) {
+ /* start a new run */
+ file[j]->dummy--;
+ run = true;
+ }
+ } else {
+ /* first run in file */
+ file[j]->dummy--;
+ run = true;
+ }
+
+ if (run) {
+ anyrun = true;
+
+ /* flush run */
+ while(1) {
+ if (fwrite(win, sizeof(recType), 1, file[j]->fp) != 1) {
+ perror("io3");
+ cleanExit(1);
+ }
+ file[j]->rec.key = win->key;
+ file[j]->valid = true;
+ if ((win = readRec()) == NULL) break;
+ if (compLT(win->key, file[j]->rec.key)) break;
+ }
+ }
+ }
+
+ /* if no room for runs, up a level */
+ if (!anyrun) {
+ int t;
+ level++;
+ t = file[0]->fib;
+ for (j = 0; j <= fileP; j++) {
+ file[j]->dummy = t + file[j+1]->fib - file[j]->fib;
+ file[j]->fib = t + file[j+1]->fib;
+ }
+ }
+ }
+}
+
+void rewindFile(int j) {
+ /* rewind file[j] and read in first record */
+ file[j]->eor = false;
+ file[j]->eof = false;
+ rewind(file[j]->fp);
+ if (fread(&file[j]->rec, sizeof(recType), 1, file[j]->fp) != 1) {
+ if (feof(file[j]->fp)) {
+ file[j]->eor = true;
+ file[j]->eof = true;
+ } else {
+ perror("io5");
+ cleanExit(1);
+ }
+ }
+}
+
+void mergeSort(void) {
+ int fileT;
+ int fileP;
+ int j;
+ tmpFileType *tfile;
+
+ /* polyphase merge sort */
+
+ fileT = nTmpFiles - 1;
+ fileP = fileT - 1;
+
+ /* prime the files */
+ for (j = 0; j < fileT; j++) {
+ rewindFile(j);
+ }
+
+ /* each pass through loop merges one run */
+ while (level) {
+ while(1) {
+ bool allDummies;
+ bool anyRuns;
+
+ /* scan for runs */
+ allDummies = true;
+ anyRuns = false;
+ for (j = 0; j <= fileP; j++) {
+ if (!file[j]->dummy) {
+ allDummies = false;
+ if (!file[j]->eof) anyRuns = true;
+ }
+ }
+
+ if (anyRuns) {
+ int k;
+ keyType lastKey;
+
+ /* merge 1 run file[0]..file[P] --> file[T] */
+
+ while(1) {
+ /* each pass thru loop writes 1 record to file[fileT] */
+
+ /* find smallest key */
+ k = -1;
+ for (j = 0; j <= fileP; j++) {
+ if (file[j]->eor) continue;
+ if (file[j]->dummy) continue;
+ if (k < 0 ||
+ (k != j && compGT(file[k]->rec.key, file[j]->rec.key)))
+ k = j;
+ }
+ if (k < 0) break;
+
+ /* write record[k] to file[fileT] */
+ if (fwrite(&file[k]->rec, sizeof(recType), 1,
+ file[fileT]->fp) != 1) {
+ perror("io6");
+ cleanExit(1);
+ }
+
+ /* replace record[k] */
+ lastKey = file[k]->rec.key;
+ if (fread(&file[k]->rec, sizeof(recType), 1,
+ file[k]->fp) == 1) {
+ /* check for end of run on file[s] */
+ if (compLT(file[k]->rec.key, lastKey))
+ file[k]->eor = true;
+ } else if (feof(file[k]->fp)) {
+ file[k]->eof = true;
+ file[k]->eor = true;
+ } else {
+ perror("io7");
+ cleanExit(1);
+ }
+ }
+
+ /* fixup dummies */
+ for (j = 0; j <= fileP; j++) {
+ if (file[j]->dummy) file[j]->dummy--;
+ if (!file[j]->eof) file[j]->eor = false;
+ }
+
+ } else if (allDummies) {
+ for (j = 0; j <= fileP; j++)
+ file[j]->dummy--;
+ file[fileT]->dummy++;
+ }
+
+ /* end of run */
+ if (file[fileP]->eof && !file[fileP]->dummy) {
+ /* completed a fibonocci-level */
+ level--;
+ if (!level) {
+ /* we're done, file[fileT] contains data */
+ return;
+ }
+
+ /* fileP is exhausted, reopen as new */
+ fclose(file[fileP]->fp);
+ if ((file[fileP]->fp = fopen(file[fileP]->name, "w+b"))
+ == NULL) {
+ perror("io8");
+ cleanExit(1);
+ }
+ file[fileP]->eof = false;
+ file[fileP]->eor = false;
+
+ rewindFile(fileT);
+
+ /* f[0],f[1]...,f[fileT] <-- f[fileT],f[0]...,f[T-1] */
+ tfile = file[fileT];
+ memmove(file + 1, file, fileT * sizeof(tmpFileType*));
+ file[0] = tfile;
+
+ /* start new runs */
+ for (j = 0; j <= fileP; j++)
+ if (!file[j]->eof) file[j]->eor = false;
+ }
+ }
+
+ }
+}
+
+
+void extSort(void) {
+ initTmpFiles();
+ makeRuns();
+ mergeSort();
+ termTmpFiles(0);
+}
+
+int main(int argc, char *argv[]) {
+
+ /* command-line:
+ *
+ * ext ifName ofName nTmpFiles nNodes
+ *
+ * ext in.dat out.dat 5 2000
+ * reads in.dat, sorts using 5 files and 2000 nodes, output to out.dat
+ */
+ if (argc != 5) {
+ printf("%s ifName ofName nTmpFiles nNodes\n", argv[0]);
+ cleanExit(1);
+ }
+
+ ifName = argv[1];
+ ofName = argv[2];
+ nTmpFiles = atoi(argv[3]);
+ nNodes = atoi(argv[4]);
+
+ printf("extSort: nFiles=%d, nNodes=%d, lrecl=%d\n",
+ nTmpFiles, nNodes, sizeof(recType));
+
+ extSort();
+
+ return 0;
+}
projects / z.facultad / 75.06 / emufs.git / commitdiff