From: Leandro Lucarella Date: Fri, 28 May 2004 20:31:12 +0000 (+0000) Subject: Subo cosas de external sort con las que estoy trabajando. Todavia no hay nada utiliza... X-Git-Tag: svn_import_r684~140 X-Git-Url: https://git.llucax.com/z.facultad/75.06/emufs.git/commitdiff_plain/a666806d9361a2876a07941b8d2bb5c973e1557e?ds=inline Subo cosas de external sort con las que estoy trabajando. Todavia no hay nada utilizable pero lo que hay anda y al parecer bien. --- diff --git a/emufs/external_sort/Makefile b/emufs/external_sort/Makefile new file mode 100644 index 0000000..4f6fad7 --- /dev/null +++ b/emufs/external_sort/Makefile @@ -0,0 +1,31 @@ +# 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) + diff --git a/emufs/external_sort/bufford.c b/emufs/external_sort/bufford.c new file mode 100644 index 0000000..8fea2cb --- /dev/null +++ b/emufs/external_sort/bufford.c @@ -0,0 +1,291 @@ + +#include "bufford.h" +#include +#include +#include + +#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; +} + diff --git a/emufs/external_sort/bufford.h b/emufs/external_sort/bufford.h new file mode 100644 index 0000000..47ffec9 --- /dev/null +++ b/emufs/external_sort/bufford.h @@ -0,0 +1,43 @@ + +#include + +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); + diff --git a/emufs/external_sort/bufford.txt b/emufs/external_sort/bufford.txt new file mode 100644 index 0000000..4efb0fb --- /dev/null +++ b/emufs/external_sort/bufford.txt @@ -0,0 +1,19 @@ +2 +456 +7 +3 +23 +4 +6 +34 +5678 +56 +89 +26 +624 +45 +282762 +22 +77 +99 +21 diff --git a/emufs/external_sort/bufford_test.c b/emufs/external_sort/bufford_test.c new file mode 100644 index 0000000..f92916a --- /dev/null +++ b/emufs/external_sort/bufford_test.c @@ -0,0 +1,84 @@ + +#include "bufford.h" +#include + +/* +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; +} + diff --git a/emufs/external_sort/comp.pas b/emufs/external_sort/comp.pas new file mode 100644 index 0000000..f7911bd --- /dev/null +++ b/emufs/external_sort/comp.pas @@ -0,0 +1,1658 @@ +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 diff --git a/emufs/external_sort/extsort.cpp b/emufs/external_sort/extsort.cpp new file mode 100644 index 0000000..7b295ec --- /dev/null +++ b/emufs/external_sort/extsort.cpp @@ -0,0 +1,569 @@ +/* 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 + +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); + } + diff --git a/emufs/external_sort/extsort.h b/emufs/external_sort/extsort.h new file mode 100644 index 0000000..8001bbd --- /dev/null +++ b/emufs/external_sort/extsort.h @@ -0,0 +1,51 @@ +/* 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 +#include +#include +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); + diff --git a/emufs/external_sort/s_ext.c b/emufs/external_sort/s_ext.c new file mode 100644 index 0000000..fc48d82 --- /dev/null +++ b/emufs/external_sort/s_ext.c @@ -0,0 +1,498 @@ +/* external sort */ + +#include +#include +#include + +/**************************** + * 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; +}