--- /dev/null
+Program Estudio_Busquedas;\r
+\r
+{encabezado}\r
+\r
+uses Crt;\r
+\r
+{declaracion de constantes}\r
+\r
+const\r
+\r
+primera=1;\r
+ultima=100;\r
+ultimamas1=ultima+1;\r
+\r
+{declaracion de tipos}\r
+\r
+type\r
+ tipollave=integer;\r
+ subindices=primera..ultima; {subindices para el vector}\r
+ aumentado=primera..ultimamas1;\r
+ T_Consultas= 1..8; {son ocho consultas}\r
+ tipovector=array [subindices] of integer;\r
+ Array_of_arrays= array [T_consultas] of tipovector;\r
+ tipo_busq= array[T_consultas] of string;\r
+\r
+{declaracion de variables}\r
+\r
+var\r
+ vector:tipovector;\r
+ idx, clave: integer; {variable de indice}\r
+ caso: T_Consultas; {subindice de los arrays}\r
+ ref_vector: array_of_arrays;\r
+ {vector para almacen de vectores utilizados}\r
+\r
+ consultas: array[T_consultas] of integer;\r
+ {vector para almacen de consultas efectuadas}\r
+\r
+ busqueda: array[T_consultas] of integer;\r
+ {vector para almacen del valor a buscar}\r
+\r
+ Tipo_b: Tipo_busq;\r
+ {vector para almacen de tipo de consultas}\r
+ linea_t:string;\r
+ ciclo,x,i,a,b:integer; {a y b son variables 'comodin' arbitrariamente empleadas}\r
+ r,s,t:real;\r
+\r
+ grDriver: Integer;\r
+ grMode: Integer; {variables para el modo grafico}\r
+\r
+\r
+\r
+{---------------------------------------------------------------------}\r
+\r
+{seccion algorítmica}\r
+{procedimientos y funciones}\r
+\r
+\r
+{----------------------------------------------------------}\r
+{PROCEDIMIENTOS PARA VISUALIZACION EN PANTALLA}\r
+\r
+{-----------------------------------------------------------------}\r
+procedure Presentacion;\r
+\r
+var a,b:integer;\r
+\r
+begin\r
+\r
+ textbackground(White);\r
+ textcolor(Black);\r
+ for a:=9 to 15 do for b:=25 to 55 do begin gotoxy(b,a);\r
+ write(' ');\r
+ end;\r
+ gotoxy(31,10);write('METODOS DE BUSQUEDA');\r
+ gotoxy(31,12);write('-estudio simulado-');\r
+ gotoxy(34,14);write('72.40 C:7');\r
+ textcolor(black+blink);\r
+ gotoxy(25,17);write('Pulse una tecla para continuar');\r
+ textbackground(Cyan);\r
+ textcolor(black);\r
+ readkey;\r
+end;{fin del procedimiento}\r
+\r
+\r
+{-----------------------------------------------------------------}\r
+procedure Salida;\r
+\r
+var a,b:integer;\r
+\r
+begin\r
+\r
+ textbackground(cyan);\r
+ textcolor(black);\r
+ for a:=2 to 6 do for b:=25 to 55 do begin gotoxy(b,a);\r
+ write(' ');\r
+ end;\r
+ gotoxy(31,2);write('TRABAJO PRACTICO #3');\r
+ gotoxy(31,3);write('Creado por el Gr#06');\r
+ gotoxy(34,5);write('>NOV 1999');\r
+ textcolor(black+blink);\r
+\r
+ textcolor(black);\r
+ readkey;\r
+end;{fin del procedimiento}\r
+\r
+\r
+{----------------------------------------------------------}\r
+Procedure Imprime_en(a,b: integer;texto:string);\r
+ begin\r
+ gotoxy(a,b);\r
+ Writeln (texto);\r
+ end; {fin del procedimiento}\r
+\r
+\r
+{----------------------------------------------------------}\r
+Procedure Muestra_barra(color:byte;valor:real;fila:integer);\r
+\r
+ var a:integer;\r
+\r
+ begin\r
+\r
+ textbackground(color);\r
+ for a:=15 to round(valor*50+15) do imprime_en(a,fila,' ');\r
+\r
+ end;\r
+\r
+{----------------------------------------------------------}\r
+\r
+\r
+{----------------------------------------------------------}\r
+{Exportacion hacia archivo de texto}\r
+\r
+procedure Graba_en_Archivo( var Clave: integer;\r
+ var V100: tipovector;\r
+ n_cons: integer;\r
+ TipoB: string;\r
+ Proba: Integer);\r
+\r
+{encabezado}{proc}\r
+{declaracion de variables}\r
+\r
+var\r
+reporte : text; {archivo de salida con formato texto}\r
+a_salida,texto,linea, conv : string;\r
+ cont: integer;\r
+\r
+{seccion algorítmica}{proc}\r
+\r
+begin\r
+\r
+ str(Proba,conv); {conversion del numero de probadilidad}\r
+ a_salida:='C:\reporte'+conv+'.txt';\r
+ assign(reporte,a_salida);\r
+ {$I-} {deshabilita el control sobre los archivos}\r
+ append(reporte);\r
+ if not (ioresult=0) then rewrite(reporte); {abre el archivo}\r
+\r
+ texto:='';\r
+ for a:=1 to 10 do texto:='-'+texto;\r
+ writeln(reporte,texto); {linea divisoria}\r
+ texto:= 'BUSQUEDA ' + TipoB;\r
+ writeln(reporte, texto); {exhibe tipo de busqueda}\r
+ texto:='';\r
+ for a:=1 to 10 do texto:='-'+texto;\r
+ writeln(reporte,texto); {linea divisoria}\r
+ str(Clave,conv); {conversion del numero de ciclos}\r
+ texto:= 'NUMERO de CICLOS: '+ conv;\r
+ str(n_cons,conv);\r
+ writeln(reporte, texto); {informa cantidad de iteraciones}\r
+ texto:= 'CONSULTAS efectuadas: '+ conv;\r
+ writeln(reporte, texto); {cantidad de consultas efectuadas}\r
+ texto:= 'VECTOR obtenido';\r
+ writeln(reporte, texto); {informa cantidad de iteraciones}\r
+ writeln(reporte);\r
+\r
+ {informacion en pantalla}\r
+ textcolor(black);\r
+ Imprime_en(7,17,'Grabando Estadisticas en archivo');\r
+ textcolor(red);\r
+ for a:=5 to (Proba*2+5) do imprime_en(a,18,'.' );\r
+ textcolor(black);\r
+\r
+\r
+ for cont := 1 to high(V100) do\r
+\r
+ begin\r
+ imprime_en(5,17,'-');\r
+ imprime_en(5,17,'\');\r
+ imprime_en(5,17,'|');\r
+ imprime_en(5,17,'/');\r
+ imprime_en(5,17,'-');\r
+ imprime_en(5,17,'\');\r
+ imprime_en(5,17,'|');\r
+ imprime_en(5,17,'/');\r
+\r
+\r
+ str(V100[cont],conv); {conversion del contenido de los vectores}\r
+ texto:=' ';\r
+ for a:=1 to (7-length(conv)) do texto:=texto+' '; {separacion uniforme}\r
+ linea := linea + conv + texto; {concatena el vector}\r
+ if cont mod 10 = 0 then\r
+ begin\r
+ writeln(reporte, linea); {linea de exportacion hacia archivo} {imprime el vector}\r
+ linea := '';\r
+\r
+ end;\r
+ end;\r
+\r
+ writeln(reporte);\r
+ close(reporte);\r
+end; {fin del procedimiento}\r
+\r
+{----------------------------------------------------------}\r
+{PROCEDIMIENTOS PARA MANIPULACION Y CREACION DE VECTORES}\r
+{----------------------------------------------------------}\r
+{generacion aleatoria del vector}\r
+{este procedimiento se ejecuta cada vez que el programa es corrido, y carga el vector para muestrear las busquedas}\r
+\r
+procedure vectoraleatorio(dimension:integer;var aleatorio:tipovector);\r
+var i:integer;\r
+ begin\r
+ Randomize;\r
+ for i:=1 to dimension do aleatorio[i]:=trunc((random*65535)-32768);\r
+ end;{fin del procedimiento}\r
+\r
+{----------------------------------------------------------}\r
+{generacion aleatoria de los subindices}\r
+{los valores a,b,c continen las proporciones a emplearse para estimar la probabilidad de aparacion; "y" es un valor aleatorio\r
+(en el programa se usará la funcion random para cargar este vector); i,j,k son los "cortes en el vector", que determinarán\r
+los rangos deonde actuan las probabilidades}\r
+\r
+function subindice(y,a,b,c:real;i,j,k:integer):integer;\r
+ begin\r
+ if y<=a then subindice:=trunc((y*(i-1)/a)+1)\r
+ else if y<=b then subindice:=trunc((y*(j-i)-(a*j)+(b*i))/(b-a))\r
+ else subindice:=trunc((y*(k-j)-(b*k)+(c*j))/(c-b));\r
+ end;{fin de la funcion}\r
+\r
+{------------------------------------------------------------------}\r
+\r
+{----------------------------------------------------------}\r
+{obtencion del valor para el subindice}\r
+{esta funcion devuelve el valor para un indice de un vector}\r
+\r
+function valor(subindice:integer;vector:tipovector):integer;\r
+\r
+ begin\r
+ valor:=vector[subindice];\r
+ end;{fin de la funcion}\r
+\r
+{----------------------------------------------------------}\r
+{permutacion de probabilidades}\r
+{para una correcta evaluacion de los sistemas, es necesario contemplar todas las posibilidades}\r
+\r
+procedure perm(c:integer;var m,n,o:real);\r
+\r
+begin\r
+ m:=0;\r
+ n:=0;\r
+ o:=0; {el ultimo valor de ser simpre 1!!}\r
+\r
+\r
+ case c of\r
+1:\r
+ begin\r
+ m:=0.15;\r
+ n:=0.5;\r
+ o:=1; {el ultimo valor de ser simpre 1!!}\r
+ end;\r
+2:\r
+ begin\r
+ m:=0.5;\r
+ n:=0.15;\r
+ o:=1; {el ultimo valor de ser simpre 1!!}\r
+ end;\r
+3:\r
+ begin\r
+ m:=0.5;\r
+ n:=1; {el ultimo valor de ser simpre 1!!}\r
+ o:=0.15;\r
+ end;\r
+4:\r
+ begin\r
+ m:=0.15;\r
+ n:=1; {el ultimo valor de ser simpre 1!!}\r
+ o:=0.5;\r
+ end;\r
+5:\r
+ begin\r
+ m:=1;\r
+ n:=0.5; {el ultimo valor de ser simpre 1!!}\r
+ o:=0.15;\r
+ end;\r
+6:\r
+ begin\r
+ m:=1; {el ultimo valor de ser simpre 1!!}\r
+ n:=0.15;\r
+ o:=0.5;\r
+ end;\r
+end\r
+\r
+end;{fin del procedimiento}\r
+\r
+{---------------------------------------------------------------}\r
+{ordenado del vector}\r
+{utiliza para esto un procedimiento de iteracion, e incluye la posibilidad de ordenar un vector de culaquier dimension\r
+permitiendole gran flexibilidad }\r
+\r
+procedure ordenarvector(dimension:integer;vec1:tipovector;var vec2:tipovector);\r
+\r
+var\r
+j,k,ultimo:integer;\r
+\r
+begin\r
+ultimo:=1;\r
+k:=1;\r
+vec2[1]:=vec1[1];\r
+while ultimo<=dimension do\r
+ begin\r
+ if vec1[ultimo+1]>=vec2[ultimo]\r
+ then vec2[ultimo+1]:=vec1[ultimo+1]\r
+ else begin\r
+ j:= 1;\r
+ while vec1[ultimo+1]>=vec2[j] do inc(j);\r
+ for k:=ultimo+1 downto j do vec2[k]:=vec2[k-1];\r
+ vec2[j]:=vec1[ultimo+1];\r
+ end;\r
+ inc(ultimo);\r
+ end;\r
+end;{fin del procedimiento}\r
+ { }\r
+{---------------------------------------------------------------}\r
+{con este procedimiento, se carga un vector que va a contener y administrar todos los vectores empleados para la busqueda}\r
+\r
+Procedure Asignar_Referencia (var r_vector:array_of_arrays;vect:tipovector);\r
+ Var\r
+ Vect_o:tipovector;\r
+ begin\r
+ r_vector[1] := vect; {desordenado para busqueda basica}\r
+ r_vector[2] := vect; {desordenado para puesta al frente}\r
+ r_vector[3] := vect; {desordenado para trasposicion}\r
+ ordenarvector(ultima,vect,vect_o);\r
+ r_vector[4] := vect_o; {ordenado para busqueda optimizada}\r
+ r_vector[5] := vect_o; {ordenado para busqueda binaria}\r
+ r_vector[6] := vect_o; {ordenado para busqueda por saltos}\r
+ r_vector[7] := vect_o; {ordenado para interpolacion}\r
+ r_vector[8] := vect_o; {ordenado para interpolacion/sec}\r
+ end;{fin del procedimiento}\r
+\r
+\r
+{---------------------------------------------------------------}\r
+{con este procedimiento, se carga un vector que va a contener y administrar todos los vectores empleados para la busqueda}\r
+\r
+Procedure Tipo_Busqueda (var b_vector:tipo_busq );\r
+ begin\r
+ b_vector[1] := 'secuencial basica (exhibe el vector original)';\r
+ b_vector[2] := 'con puesta al frente';\r
+ b_vector[3] := 'con trasposicion';\r
+ b_vector[4] := 'optimizada';\r
+ b_vector[5] := 'binaria';\r
+ b_vector[6] := 'por saltos';\r
+ b_vector[7] := 'por interpolacion';\r
+ b_vector[8] := 'por interpolacion + secuencial';\r
+ end;{fin del procedimiento}\r
+\r
+\r
+{----------------------------------------------------------}\r
+{FUNCIONES DE BUSQUEDA}\r
+{-----------------------------------------------------------------}\r
+{busqueda secuencial basica}\r
+\r
+function SEQB (var a: tipovector; x:integer): integer;\r
+ var\r
+ i: integer;\r
+ begin\r
+for i:=1 to 100 do\r
+ if x=a[i] then\r
+ SEQB:= i;\r
+ exit;\r
+ end; {fin del procedimiento}\r
+\r
+{----------------------------------------------------------}\r
+{busqueda secuencial con traslado al frente del elemento}\r
+\r
+function MRU(var a:tipovector ; x:integer): integer;\r
+ var\r
+ i: integer; cambio: integer;\r
+ begin\r
+ for i:=1 to 100 do\r
+ if x=a[i] then\r
+ begin\r
+ cambio:=a[i];\r
+ a[i]:= a[1];\r
+ a[1]:=cambio;\r
+ MRU:= i;\r
+ exit;\r
+ end;\r
+ end; {fin del procedimiento}\r
+\r
+{----------------------------------------------------------}\r
+{busqueda secuencial con trasposicion al elemento anterior}\r
+\r
+function MFU(var a:tipovector; x:integer): integer;\r
+ var\r
+ i: integer; cambio: integer;\r
+ begin;\r
+ if x=a[1] then exit;\r
+ for i:=1 to 100 do\r
+ if x=a[i] then\r
+ begin;\r
+ cambio:=a[i];;\r
+ a[i]:=a[i-1];\r
+ a[i-1]:=cambio;\r
+ MFU:=i;\r
+ exit;\r
+ end;\r
+ end; {fin del procedimiento}\r
+\r
+{----------------------------------------------------------}\r
+{busqueda binaria - recursiva}\r
+\r
+function BINR(var a:tipovector;clave:integer;Min,Max,Ct:integer):integer;\r
+var\r
+ medio:integer;\r
+begin\r
+ inc(Ct);\r
+ medio:=(Min+Max) div 2;\r
+ if (Min <= Max) and (a[medio] <> clave) then\r
+ begin\r
+ if clave < a[medio]\r
+ then\r
+ begin\r
+ Max:=medio-1;\r
+ end\r
+ else\r
+ begin\r
+ Min:=medio+1;\r
+ end;\r
+ ct:=BINR(a,clave,Min,Max,ct);\r
+ end;\r
+BINR:=ct;\r
+end; {fin del procedimiento}\r
+\r
+{----------------------------------------------------------}\r
+{busqueda por saltos}\r
+\r
+function SALT (var a: tipovector; x,Min,Max,salto:integer): integer;\r
+ var\r
+ prop,i: integer;\r
+ begin\r
+prop:=round(Max/salto);\r
+for i:=Min to (prop) do\r
+ if x=a[i*salto] then\r
+ begin\r
+ SALT:=i;\r
+ exit;\r
+\r
+ end\r
+ else if x<a[i*salto] then\r
+ begin\r
+ Min:=i*salto-salto;\r
+ Max:=i*salto;\r
+ if salto>1 then\r
+ salto:=salto div 2\r
+ else salto :=1; {por si acaso llego a uno antes de hallar el valor}\r
+ i:=SALT(a,x,Min,Max,salto);\r
+ exit;\r
+ end;\r
+\r
+\r
+\r
+ end; {fin del procedimiento}\r
+\r
+{----------------------------------------------------------}\r
+\r
+\r
+{----------------------------------------------------------}\r
+{busqueda por interpolacion - recursiva}\r
+{Este procedimiento realiza la busque de un numero n en un vector vec (el\r
+cual debe encontrarse ordenado de menor a mayor) y devuelve un valor cont\r
+que aclara cuantos ciclos de busqueda realizo}\r
+\r
+function INTR (var vec:tipovector;n:integer;PriInd,UltInd,Ct:integer):integer;\r
+var\r
+ r,prinum,ultnum:integer;\r
+ numerador,denominador:word;\r
+ pend,y:real;\r
+\r
+Begin\r
+\r
+ prinum:=vec[priind];\r
+ ultnum:=vec[ultind];\r
+ inc(Ct);\r
+\r
+ begin\r
+ if ultnum=prinum then INTR:=ct else\r
+ begin\r
+ NUMERADOR:=ultind-priind;\r
+ DENOMINADOR:=ultnum-prinum;\r
+ pend:=NUMERADOR/DENOMINADOR;\r
+ y:=pend*n-pend*prinum+priind; {desarrollo de la ecuacion de una recta\r
+ que pasa por dos puntos}\r
+ r:=round(y);\r
+ if vec[r]=n then INTR:=ct\r
+ else begin\r
+ if vec[r]>n then ultind:=r-1\r
+ else priind:=r+1;\r
+ ct:=INTR(vec,n,priind,ultind,ct);\r
+ end;\r
+\r
+\r
+ end;\r
+ end;\r
+end; {fin del procedimiento}\r
+\r
+{----------------------------------------------------------}\r
+{busqueda por interpolacion + secuencial}\r
+{Este procedimiento realiza la busque de un numero n en un vector vec (el\r
+cual debe encontrarse ordenado de menor a mayor). Realiza una busqueda por\r
+interpolacio y si no lo encuentra lo buscaca por la busqueda secuencial\r
+y devuelve un valor priind que aclara cuantos ciclos de busqueda realizo}\r
+\r
+function sec_de_intysec (var v:tipovector;k:integer;x:integer):integer;\r
+\r
+{usada posteriormente}\r
+\r
+var p,n,busc:integer;\r
+\r
+Begin\r
+\r
+ if v[x]<k then p:=x\r
+ else p:=low(v);\r
+ n:=high(v);\r
+ while (p<=n) and (v[p]<>k) do\r
+ begin\r
+ inc(p);\r
+ inc(busc);\r
+ end;\r
+sec_de_intysec:=busc;\r
+end; {fin del procedimiento}\r
+\r
+function INTS(var vec:tipovector;n:integer):integer;\r
+{esta es la funcion que se usará en el programa principal}\r
+var\r
+\r
+ r,priind,ultind,prinum,ultnum:integer;\r
+ pend,y:real;\r
+\r
+Begin\r
+\r
+ priind:=low(vec);\r
+\r
+ ultind:=high(vec);\r
+ prinum:=vec[priind];\r
+ ultnum:=vec[ultind];\r
+ pend:=(ultind-priind)/(ultnum-prinum);\r
+ y:=pend*n;\r
+ r:=round(y);\r
+ if r<=0 then r:=priind;\r
+ if r>ultind then r:=ultind;\r
+ if vec[r]<>n then INTS:=sec_de_intysec (vec,n,r);\r
+end; {fin del procedimiento}\r
+\r
+{----------------------------------------------------------}\r
+{programa principal}\r
+{----------------------------------------------------------}\r
+\r
+begin\r
+\r
+\r
+\r
+clrscr;\r
+\r
+Presentacion;\r
+\r
+Tipo_busqueda (Tipo_b); {define el nombre de las busquedas que se van a usar}\r
+Randomize; {inicializa la funcion random}\r
+\r
+{por cada distribucion de probabilidades se deberá generar un ciclo}\r
+\r
+for i:=1 to 6 do\r
+ begin\r
+ {inicializacion del numero de consultas}\r
+ for caso:=1 to 8 do Consultas[caso]:=0;\r
+\r
+ {creacion del vector original}\r
+ vectoraleatorio(100,vector);\r
+ {carga de probalidades}\r
+ perm(i,r,s,t);\r
+\r
+ clrscr;\r
+\r
+ textbackground(black);\r
+ for a:=1 to 80 do for b:=1 to 5 do imprime_en(a,b,' ');\r
+ textcolor(white);\r
+ imprime_en(5,5,'DISTRIBUCION DE PROBABILIDADES');\r
+\r
+\r
+ textbackground(white+blink);\r
+ textcolor(black);\r
+ for a:=1 to 80 do for b:=6 to 11 do imprime_en(a,b,' ');\r
+ imprime_en(5,6,'ALTERNATIVA');\r
+ str(i,linea_t);\r
+ imprime_en(17,6,linea_t);\r
+ imprime_en(5,8,'SECCION>>');\r
+ imprime_en(5,9,'1ERA.:');\r
+ imprime_en(5,10,'2DA:');\r
+ imprime_en(5,11,'3RA.:');\r
+\r
+ Str(round(r*100),linea_t);\r
+ imprime_en(12,9,linea_t);\r
+ Str(round(s*100),linea_t);\r
+ imprime_en(12,10,linea_t);\r
+ Str(round(t*100),linea_t);\r
+ imprime_en(12,11,linea_t);\r
+\r
+ textbackground(cyan);\r
+ for a:=1 to 80 do imprime_en(a,7,' ');\r
+\r
+ Muestra_barra(green,r,9);\r
+ Muestra_barra(red,s,10);\r
+ Muestra_barra(blue,t,11);\r
+ textbackground(white);\r
+ textbackground(cyan);\r
+ textcolor(black);\r
+\r
+ {carga de referencias}\r
+ Asignar_Referencia (ref_vector,vector);\r
+\r
+ for ciclo:=1 to 10000 do\r
+ begin\r
+ x:=subindice(random,r,s,t,30,60,100);\r
+ for caso:=1 to 8 do\r
+ busqueda[caso]:=valor(x,ref_vector[caso]);\r
+ {asigna para cada vector el valor correspondiente\r
+ al subindice hallado previamente}\r
+ consultas[1]:=SEQB(ref_vector[1],busqueda[1]);\r
+ consultas[2]:=MRU(ref_vector[2],busqueda[2]);\r
+ consultas[3]:=MFU(ref_vector[3],busqueda[3]);\r
+ consultas[4]:=SEQB(ref_vector[4],busqueda[4]);\r
+ consultas[5]:=BINR(ref_vector[5],busqueda[5],primera,ultima,0);\r
+ consultas[6]:=SALT(ref_vector[6],busqueda[6],1,100,2);\r
+ consultas[7]:=INTR(ref_vector[7],busqueda[7],primera,ultima,0);\r
+ consultas[8]:=INTS(ref_vector[8],busqueda[8]);\r
+\r
+ {en caso de estar en un valor "estadistico"}\r
+ if (ciclo=100) or (ciclo=500) or (ciclo=1000) or (ciclo=5000) or (ciclo=10000) then\r
+ for caso := 1 to 8 do\r
+ Graba_en_Archivo (ciclo,ref_vector[caso],consultas[caso],tipo_b[caso],i);\r
+{esto es una sola instruccion}\r
+ end;\r
+ end;\r
+ {Pantalla de salida}\r
+ clrscr;\r
+ textbackground(black);\r
+ for a:=8 to 72 do for b:=10 to 15 do imprime_en(a,b,' ');\r
+ textbackground(white);\r
+ for a:=7 to 71 do for b:=11 to 17 do imprime_en(a,b,' ');\r
+ textcolor(black);\r
+\r
+ Imprime_en(10,12,'El programa programa finaliz¢ exitosamente.');\r
+ Imprime_en(10,13,'Busque los resultados en la Raiz de su disco local (C:\)');\r
+ Imprime_en(10,14,'<Presione una tecla para salir>');\r
+ Salida; {cartel de salida}\r
+\r
+\r
+end. {fin del programa}\r
+\r
--- /dev/null
+ (**************************************)\r
+ (**************************************)\r
+ (** **)\r
+ (** ALGORITMOS DE BUSQUEDA EN PASCAL **)\r
+ (** **)\r
+ (**************************************)\r
+ (**************************************)\r
+\r
+(***************************************************************************\r
+ *\r
+ * Busqueda Secuencial\r
+ *\r
+ * Recorre el vector y compara hasta encontrar el elemento.\r
+ * Devuelve el indice del elemento.\r
+ *\r
+ ***************************************************************************)\r
+\r
+function bSecuencial(var v: Vector; { Vector en donde se va a buscar }\r
+ d: Dato) { Dato a buscar (igual que el elemento de v }\r
+ : Integer; { Indice en donde se encuentra el dato buscado o cero si no esta }\r
+\r
+ var\r
+ i, resultado: Integer;\r
+\r
+ begin\r
+ resultado := 0;\r
+ for i := 1 to TAM do { TAM es el tama¤o del vector }\r
+ if v[i] = d then begin { Si encontro el dato d en v ... }\r
+ resultado := i; { Asigna el indice actual al resultado }\r
+ break; { Finaliza el ciclo for }\r
+ end; { if }\r
+ bSecuencial := resultado;\r
+ end; { function bSecuencial }\r
+\r
+{===========================================================================}\r
+\r
+(***************************************************************************\r
+ *\r
+ * Busqueda Secuencial Auto-organizada moviendo al frente el elemento encontrado\r
+ *\r
+ * Recorre el vector y compara hasta encontrar el elemento. Al encontrar el\r
+ * elemento, lo mueve automaticamente al inicio del vector.\r
+ * Devuelve true si se encontro o false si no se encontro.\r
+ *\r
+ ***************************************************************************)\r
+\r
+function bSecuencialAutoOrganizadaMoverAlFrente\r
+ (var v: Vector; { Vector en donde se va a buscar }\r
+ d: Dato) { Dato a buscar (igual que el elemento de v }\r
+ : Boolean; { True si lo encontr¢, False si no lo hizo. La posicion es 1 siempre }\r
+\r
+(***************************************************************************\r
+ *\r
+ * Mueve el elemento que se encuentra en el indice i hasta el inicio,\r
+ * desplazando al resto de los indices hacia abajo.\r
+ *\r
+ ***************************************************************************)\r
+\r
+ procedure moverAlFrente(var v: Vector; { Vector a procesar }\r
+ pos: Integer); { Indice a mover al frente }\r
+\r
+ var\r
+ tmp: Dato;\r
+ i: Integer;\r
+\r
+ begin\r
+ if pos > 1 then begin\r
+ tmp := v[1];\r
+ v[1] := v[pos];\r
+ for i := pos - 2 downto 1 do\r
+ v[i+1] := v[i+2];\r
+ v[2] := tmp;\r
+ end; { if pos > 1 }\r
+ end; { procedure moverAlFrente }\r
+\r
+ (*******************************************************************)\r
+\r
+ { continuacion de la funcion bSecuencialAutoOrganizadaMoverAlFrente }\r
+\r
+ var\r
+ i: Integer;\r
+ resultado: Boolean;\r
+\r
+ begin\r
+ resultado := false;\r
+ for i := 1 to TAM do { TAM es el tama¤o del vector }\r
+ if v[i] = d then begin { Si encontro el dato d en v ... }\r
+ moverAlFrente(v, i); { Mueve al frente el elemento en i }\r
+ resultado := true; { Asigna true al resultado }\r
+ break; { Finaliza el ciclo for }\r
+ end; { if }\r
+ bSecuencialAutoOrganizadaMoverAlFrente := resultado;\r
+ end; { function bSecuencialAutoOrganizadaMoverAlFrente }\r
+\r
+{===========================================================================}\r
+\r
+(***************************************************************************\r
+ *\r
+ * Busqueda Secuencial Auto-organizada moviendo el elemento encontrado a la\r
+ * posicion del elemento anterior.\r
+ *\r
+ * Recorre el vector y compara hasta encontrar el elemento. Al encontrar el\r
+ * elemento, lo mueve automaticamente a la posicion anterior del vector.\r
+ * Devuelve el indice del elemento.\r
+ *\r
+ ***************************************************************************)\r
+\r
+function bSecuencialAutoOrganizadaMoverAnterior\r
+ (var v: Vector; { Vector en donde se va a buscar }\r
+ d: Dato) { Dato a buscar (igual que el elemento de v }\r
+ : Integer; { Indice en donde se encuentra el dato buscado o cero si no esta }\r
+\r
+ var\r
+ i, resultado: Integer;\r
+ aux: Dato;\r
+\r
+ begin\r
+ resultado := 0;\r
+ if v[1] = d then\r
+ resultado := 1\r
+ else\r
+ for i := 2 to TAM do { TAM es el tama¤o del vector }\r
+ if v[i] = d then { Si encontro el dato d en v ... }\r
+ aux := v[i]; { Realiza el intercambio del elemento }\r
+ v[i] := v[i-1]; { encontrado con el primer elemento }\r
+ v[i-1] := aux; { del vector v }\r
+ resultado := i - 1; { Pone como resultado a la nueva posicion de d }\r
+ break; { Finaliza el ciclo for }\r
+ end; { if }\r
+ bSecuencialAutoOrganizadaMoverAnterior := resultado;\r
+ end; { function bSecuencialAutoOrganizadaMoverAnterior }\r
+\r
+{===========================================================================}\r
+\r
+(***************************************************************************\r
+ *\r
+ * Busqueda Binaria Recursiva.\r
+ *\r
+ * Requiere que el vector este ordenado de menor a mayor (creciente).\r
+ * Parte el vector al medio y compara. Si es igual, lo encontro y devuelve\r
+ * la posicion. Si el valor buscado es menor, toma la primera mitad y le\r
+ * la segunda mitad y le aplica la funcion recursivamente.\r
+ * Devuelve el indice del elemento.\r
+ *\r
+ ***************************************************************************)\r
+\r
+function bBinariaRecursiva(var v: Vector; { Vector en donde se va a buscar }\r
+ ini, { Indice por el cual empieza la busqueda }\r
+ fin: Integer;{ Indice por el cual termina la busqueda }\r
+ d: Dato) { Dato a buscar (igual que el elemento de v }\r
+ : Integer; { Indice en donde se encuentra el dato buscado o cero si no esta }\r
+\r
+ var\r
+ medio: Integer;\r
+\r
+ begin\r
+ if (v[ini] > d) or (v[fin] < d) then begin { Si d no esta entre el mayor y menor valor de v ... }\r
+ bBinariaRecursiva := 0 { Asigna 0 al resultado, indicando que no encontro el dato }\r
+ else begin { Si esta entre los valores ... }\r
+ medio := ini + ((fin - ini) div 2); { Parte el vector en dos con el valor medio }\r
+ if v[medio] = d then { Si el dato esta en la posicion del medio ... }\r
+ bBinariaRecursiva := medio { Asigna a la funcion el valor de dicho indice }\r
+ else if v[medio] < d then { Si el valor intermedio es menor que el buscado ... }\r
+ { Asigna a la funcion (recursivamente) el valor de ella misma evaluada con inicio en el medio }\r
+ { mas 1 (la posicion del medio ya fue comparada) y el mismo fin. Esto se debe a que el vector }\r
+ { esta ordenado de forma creciente y el dato buscado es mayor que el dato intermedio, entonces }\r
+ { si se encuentra el valor buscado, estara en la segunda mitad del vector }\r
+ bBinariaRecursiva := bBinariaRecursiva(v, medio + 1, fin, d)\r
+ else { Si el valor intermedio es mayor que el buscado ... }\r
+ { Igual que el anterior pero lo busca en la primera mitad }\r
+ bBinariaRecursiva := bBinariaRecursiva(v, ini, medio - 1, d);\r
+ end; { if (v[ini] > d) or (v[fin] < d) }\r
+ end; { bBinariaRecursiva }\r
+\r
+{===========================================================================}\r
+\r
+(***************************************************************************\r
+ *\r
+ * Busqueda Binaria Recursiva.\r
+ *\r
+ * Requiere que el vector este ordenado de menor a mayor (creciente).\r
+ * Parte el vector al medio y compara. Si es igual, lo encontro y devuelve\r
+ * la posicion. Si el valor buscado es menor, toma la primera mitad y le\r
+ * la segunda mitad y le aplica la funcion recursivamente.\r
+ * Devuelve el indice del elemento.\r
+ *\r
+ ***************************************************************************)\r
+\r
+function bInterpolacionRecursiva\r
+ (var v: Vector; { Vector en donde se va a buscar }\r
+ ini, { Indice por el cual empieza la busqueda }\r
+ fin: Integer;{ Indice por el cual termina la busqueda }\r
+ d: Dato) { Dato a buscar (igual que el elemento de v }\r
+ : Integer; { Indice en donde se encuentra el dato buscado o cero si no esta }\r
+\r
+ var\r
+ medio: Integer;\r
+\r
+ begin\r
+ if (v[ini] > d) or (v[fin] < d) then begin { Si d no esta entre el mayor y menor valor de v ... }\r
+ bBinariaRecursiva := 0 { Asigna 0 al resultado, indicando que no encontro el dato }\r
+ else begin { Si esta entre los valores ... }\r
+ medio := ini + ((fin - ini) div 2); { Parte el vector en dos con el valor medio }\r
+ if v[medio] = d then { Si el dato esta en la posicion del medio ... }\r
+ bBinariaRecursiva := medio { Asigna a la funcion el valor de dicho indice }\r
+ else if v[medio] < d then { Si el valor intermedio es menor que el buscado ... }\r
+ { Asigna a la funcion (recursivamente) el valor de ella misma evaluada con inicio en el medio }\r
+ { mas 1 (la posicion del medio ya fue comparada) y el mismo fin. Esto se debe a que el vector }\r
+ { esta ordenado de forma creciente y el dato buscado es mayor que el dato intermedio, entonces }\r
+ { si se encuentra el valor buscado, estara en la segunda mitad del vector }\r
+ bBinariaRecursiva := bBinariaRecursiva(v, medio + 1, fin, d)\r
+ else { Si el valor intermedio es mayor que el buscado ... }\r
+ { Igual que el anterior pero lo busca en la primera mitad }\r
+ bBinariaRecursiva := bBinariaRecursiva(v, ini, medio - 1, d);\r
+ end; { if (v[ini] > d) or (v[fin] < d) }\r
+ end; { bBinariaRecursiva }\r
+\r
--- /dev/null
+233\r
+44\r
+3433\r
+34\r
+23\r
+1\r
+55\r
+-12\r
+9988\r
+8\r
+88\r
+23\r
+2331\r
+1232\r
+232\r
+232\r
+121\r
+23\r
+-23\r
+-123\r
+-11231\r
+12\r
+1233\r
+123\r
+31\r
+1\r
+12233\r
+123\r
+-231\r
+653\r
+-653\r
+5334\r
+-55\r
+-53445\r
+3453\r
+4567\r
+45456\r
+7777\r
+545\r
+-767\r
+-563\r
+345\r
+6555\r
+-45\r
+5658\r
+4585\r
+334
\ No newline at end of file
--- /dev/null
+<HEAD>
+<TITLE>Binary tree reorganization hashing: insertion
+</TITLE>
+<BODY>
+<H2>
+<H3>
+<A HREF="../../images/handbook.gif"><IMG SRC="../../images/handbook2.gif" align=left></A>
+<A HREF="../../hbook.html">
+<IMG SRC="../../images/home_g.gif" hspace = 15 vspace = 4></A><BR>
+<A HREF="../../expand.html">
+<IMG SRC="../../images/contents_g.gif" hspace = 15 vspace = 4></A><BR>
+<A HREF="../../search_a.html">
+<IMG SRC="../../images/chapter_g.gif" hspace = 15 vspace = 4></A><BR>
+<A HREF="311.ins.c.html"><IMG SRC="../../images/prevalg_g.gif" hspace = 15 vspace = 4></A><BR>
+<A HREF="311c.srch.c.html">
+<IMG SRC="../../images/nextalg_g.gif" hspace = 15 vspace = 4></A><BR>
+<BR></H2>
+<HR>
+<H2><B>Binary tree reorganization hashing: insertion
+</B></H2><BR>
+<CENTER>
+<TABLE BORDER>
+<TR>
+<TD COLSPAN = 1>
+<TD rowspan = 1>
+<TR><TD>
+<XMP>
+ procedure insert( key : typekey; var r : dataarray );
+ var i, inc, init, j : integer;
+
+ function SearchMove ( init, inc, level : integer ) : integer;
+ {*** Find the first hole (empty location) at the given depth
+ in the binary tree spanned by a key ***}
+ label 999;
+ var i, inc1, j, k : integer;
+ begin
+ i := (init + inc*level) mod m;
+ if empty(r[i]) or deleted(r[i]) then SearchMove := i
+ else begin
+ for j:=level-1 downto 0 do begin
+ i := (init + inc*j) mod m;
+ inc1 := increment( r[i].k );
+ k := SearchMove( (i+inc1) mod m, inc1, level-j-1 );
+ if k>-1 then begin
+ {*** A hole was found, move forward ***}
+ r[k] := r[i];
+ SearchMove := i;
+ goto 999 {*** return ***}
+ end
+ end;
+ {*** Could not find hole ***}
+ SearchMove := -1;
+ end;
+ 999:
+ end;
+
+ begin
+ init := hashfunction( key );
+ inc := increment( key );
+ i := 0; j := -1;
+ while (i<=n) and (j<0) and (n<m) do begin
+ j := SearchMove( init, inc, i );
+ i := i+1
+ end;
+ if j>-1 then begin
+ {*** A hole was found, insert key ***}
+ r[j].k := key;
+ n := n+1
+ end
+ else Error {*** table is full ***};
+ end;
+</XMP></TD></TR></TABLE>
+<BR>
+<H3><A HREF="ftp://sunsite.dcc.uchile.cl/pub/users/rbaeza/handbook/algs/3/3382.ins.p"><IMG SRC="../../images/ftp.xbm" hspace=10>Pascal</A> source (3382.ins.p) </H3></CENTER>
+<HR><H4>
+<IMG SRC="../../images/aw3.gif" align=left><H5><BR>
+© <A HREF="http://aw.com">Addison-Wesley </A>Publishing Co. Inc.
+</H5></H4><HR>
+</BODY>
--- /dev/null
+<HEAD>
+<TITLE>Brent's reorganization scheme: insertion
+</TITLE>
+<BODY>
+<H2>
+<H3>
+<A HREF="../../images/handbook.gif"><IMG SRC="../../images/handbook2.gif" align=left></A>
+<A HREF="../../hbook.html">
+<IMG SRC="../../images/home_g.gif" hspace = 15 vspace = 4 ALT = "[Home]"></A><BR>
+<A HREF="../../search_a.html">
+<IMG SRC="../../images/chapter_g.gif" hspace = 15 vspace = 4 ALT = "[Chapter]"></A><BR>
+<A HREF="../../expand.html">
+<IMG SRC="../../images/contents_g.gif" hspace = 15 vspace = 4 ALT = "[Contents]"></A><BR>
+<A HREF="3381.ins.c.html">
+</A>
+<A HREF="3381.ins.c.html">
+<IMG SRC="../../images/prevalg_g.gif" hspace = 15 vspace = 4 ALT = "[Previous Algorithm]"></A><BR>
+<A HREF="341.data.c.html">
+<IMG SRC="../../images/nextalg_g.gif" hspace = 15 vspace = 4 ALT = "[Next Algorithm]"></A><BR>
+<BR></H2>
+<HR>
+<H2><B>Brent's reorganization scheme: insertion
+</B></H2><BR>
+<CENTER>
+<TABLE BORDER>
+<TR>
+<TD COLSPAN = 1>
+<TD rowspan = 1>
+<TR><TD>
+<XMP>
+ procedure insert( key : typekey; var r : dataarray );
+ label 999;
+ var i, ii, inc, init, j, jj : integer;
+
+ begin
+ init := hashfunction( key );
+ inc := increment( key );
+ for i:=0 to n do
+ for j:=i downto 0 do begin
+ jj := (init + inc*j) mod m;
+ ii := (jj + increment(r[jj].k) * (i-j)) mod m;
+ if empty(r[ii]) or deleted(r[ii]) then begin
+ {*** move record forward ***}
+ r[ii] := r[jj];
+ {*** insert new in r[jj] ***}
+ r[jj].k := key;
+ n := n+1;
+ goto 999 {*** return ***}
+ end
+ end;
+ Error {*** table full ***};
+ 999:
+ end;
+</XMP></TD></TR></TABLE>
+<BR>
+<H3><A HREF="ftp://sunsite.dcc.uchile.cl/pub/users/rbaeza/handbook/algs/3/3381.ins.c"><IMG SRC="../../images/ftp.xbm" hspace=10>C</A> source (3381.ins.c) <A HREF="ftp://sunsite.dcc.uchile.cl/pub/users/rbaeza/handbook/algs/3/3381.ins.p"><IMG SRC="../../images/ftp.xbm" hspace=10>Pascal</A> source (3381.ins.p)
+</H3></CENTER>
+<HR><H4>
+<IMG SRC="../../images/aw3.gif" align=left><H5><BR>
+© <A HREF="http://aw.com">Addison-Wesley </A>Publishing Co. Inc.
+</H5></H4><HR>
+</BODY>
--- /dev/null
+<HEAD>
+<TITLE>Double hashing: insertion
+</TITLE>
+<BODY>
+<H2>
+<H3>
+<A HREF="../../images/handbook.gif"><IMG SRC="../../images/handbook2.gif" align=left></A>
+<A HREF="../../hbook.html">
+<IMG SRC="../../images/home_g.gif" hspace = 15 vspace = 4 ALT = "[Home]"></A><BR>
+<A HREF="../../search_a.html">
+<IMG SRC="../../images/chapter_g.gif" hspace = 15 vspace = 4 ALT = "[Chapter]"></A><BR>
+<A HREF="../../expand.html">
+<IMG SRC="../../images/contents_g.gif" hspace = 15 vspace = 4 ALT = "[Contents]"></A><BR>
+<A HREF="335.ins.c.html">
+</A>
+<A HREF="335.ins.c.html">
+<IMG SRC="../../images/prevalg_g.gif" hspace = 15 vspace = 4 ALT = "[Previous Algorithm]"></A><BR>
+<A HREF="335.srch.c.html">
+<IMG SRC="../../images/nextalg_g.gif" hspace = 15 vspace = 4 ALT = "[Next Algorithm]"></A><BR>
+<BR></H2>
+<HR>
+<H2><B>Double hashing: insertion
+</B></H2><BR>
+<CENTER>
+<TABLE BORDER>
+<TR>
+<TD COLSPAN = 1>
+<TD rowspan = 1>
+<TR><TD>
+<XMP>
+ procedure insert( key : typekey; var r : dataarray );
+ var i, inc, last : integer;
+
+ begin
+ i := hashfunction( key ) ;
+ inc := increment( key );
+ last := (i+(m-1)*inc) mod m;
+ while (i<>last) and (not empty(r[i]))
+ and (not deleted(r[i])) and (r[i].k<>key) do
+ i := (i+inc) mod m;
+ if empty(r[i]) or deleted(r[i]) then
+ begin
+ {*** insert here ***}
+ r[i].k := key;
+ n := n+1
+ end
+ else Error {*** table full, or key already in table ***};
+ end;
+</XMP></TD></TR></TABLE>
+<BR>
+<H3><A HREF="ftp://sunsite.dcc.uchile.cl/pub/users/rbaeza/handbook/algs/3/335.ins.c"><IMG SRC="../../images/ftp.xbm" hspace=10>C</A> source (335.ins.c) <A HREF="ftp://sunsite.dcc.uchile.cl/pub/users/rbaeza/handbook/algs/3/335.ins.p"><IMG SRC="../../images/ftp.xbm" hspace=10>Pascal</A> source (335.ins.p)
+</H3></CENTER>
+<HR><H4>
+<IMG SRC="../../images/aw3.gif" align=left><H5><BR>
+© <A HREF="http://aw.com">Addison-Wesley </A>Publishing Co. Inc.
+</H5></H4><HR>
+</BODY>
--- /dev/null
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">\r
+<!-- saved from url=(0044)http://www.cosy.sbg.ac.at/~ppalfrad/hashing/ -->\r
+<HTML><HEAD><TITLE>Hashing</TITLE>\r
+<META content="Weasel alias Peter Palfrader - weasel@netalive.org" name=Author>\r
+<META content="text/html; charset=iso-8859-1" http-equiv=Content-Type>\r
+<META \r
+content="hash, hashing, linear probing, squared probing, double hashing, pascal" \r
+name=keywords>\r
+<META \r
+content="A small paper that explains how hashing works with examples in Pascal." \r
+name=description>\r
+<META content="MSHTML 5.00.2314.1000" name=GENERATOR></HEAD>\r
+<BODY aLink=#ffff00 bgColor=#ffffff leftMargin=0 link=#000000 text=#000000 \r
+topMargin=0 vLink=#000000>\r
+<TABLE border=0 cellPadding=4 cellSpacing=0 width="100%">\r
+ <TBODY>\r
+ <TR>\r
+ <TD bgColor=#000000><FONT color=#ffffff face=verdana,arial,helvetica \r
+ size=1><A href="http://www.cosy.sbg.ac.at/~ppalfrad/"><STRONG><FONT \r
+ color=#ffffff>home</FONT></STRONG></A> | <STRONG><FONT \r
+ color=#ffffff>Hashing</FONT></STRONG> </FONT></TD></TR>\r
+ <TR>\r
+ <TD bgColor=#777777><IMG alt="" height=1 src="" \r
+width=1></TD></TR></TBODY></TABLE>\r
+<TABLE border=0 cellPadding=4 cellSpacing=0 width="100%">\r
+ <TBODY>\r
+ <TR>\r
+ <TD vAlign=top>\r
+ <H1>Hashing</H1><FONT size=2>V 0.1</FONT> \r
+ <P>Hashing is a method to store data in an array so that storing, \r
+ searching, inserting and deleting data is fast (in theory it's O(1)). For \r
+ this every record needs an unique key. \r
+ <P>The basic idea is not to search for the correct position of a record \r
+ with comparisons but to compute the position within the array. The \r
+ function that returns the position is called the 'hash function' and the \r
+ array is called a 'hash table'. \r
+ <P>In our examples our key is an integer value as is the actual data. \r
+ <P>[note that I use pascal syntax since this is easily readable by \r
+ everybody I asume] \r
+ <P><!-- code2html add pas
+type
+ THash_Record = record
+ key : integer;
+ data : integer;
+ end;
+--><!-- code2html delete start --><PRE><A name=1_line1></A>\r
+<A name=1_line2><STRONG>type</STRONG></A>\r
+<A name=1_line3> <FONT color=#993333>THash_Record</FONT> <FONT color=#4444ff>=</FONT> <STRONG>record</STRONG></A>\r
+<A name=1_line4> <FONT color=#993333>key</FONT> <FONT color=#4444ff>:</FONT> <FONT color=#993333>integer</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=1_line5> <FONT color=#993333>data</FONT> <FONT color=#4444ff>:</FONT> <FONT color=#993333>integer</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=1_line6> <STRONG>end</STRONG><FONT color=#4444ff>;</FONT></A>\r
+</PRE><PRE></PRE><!-- code2html delete stop -->\r
+ <P>the hash table now looks like this: \r
+ <P><!-- code2html add pas
+const
+ HASH_LENGTH = 100; { the length of the hash table and so the }
+ { maximum number of records that can be stored }
+
+type
+ THash_Table = array[0..HASH_LENGTH-1] of THash_Record;
+--><!-- code2html delete start --><PRE><A name=2_line1></A>\r
+<A name=2_line2><STRONG>const</STRONG></A>\r
+<A name=2_line3> <FONT color=#993333>HASH_LENGTH</FONT> <FONT color=#4444ff>=</FONT> <FONT color=#ff0000>100</FONT><FONT color=#4444ff>;</FONT> <FONT color=#444444>{ the length of the hash table and so the }</FONT></A>\r
+<A name=2_line4> <FONT color=#444444>{ maximum number of records that can be stored }</FONT></A>\r
+<A name=2_line5></A>\r
+<A name=2_line6><STRONG>type</STRONG></A>\r
+<A name=2_line7> <FONT color=#993333>THash_Table</FONT> <FONT color=#4444ff>=</FONT> <STRONG>array</STRONG><FONT color=#4444ff>[</FONT><FONT color=#ff0000>0..</FONT><FONT color=#993333>HASH_LENGTH</FONT><FONT color=#4444ff>-</FONT><FONT color=#ff0000>1</FONT><FONT color=#4444ff>]</FONT> <STRONG>of</STRONG> <FONT color=#993333>THash_Record</FONT><FONT color=#4444ff>;</FONT></A>\r
+</PRE><PRE></PRE><!-- code2html delete stop -->\r
+ <P>If we know that the key is in a small range we could use the key itself \r
+ as an index (also called hash address) for our array. However this is very \r
+ rarely the case so we have to find some kind of hash function. A very \r
+ common and not so bad function is a simple MODulo function: \r
+ <P><!-- code2html add pas
+function Hash_Function(key : integer) : integer;
+begin
+ Hash_Function := key MOD HASH_LENGTH;
+end;
+--><!-- code2html delete start --><PRE><A name=3_line1></A>\r
+<A name=3_line2><STRONG>function</STRONG> <FONT color=#993333>Hash_Function</FONT><FONT color=#4444ff>(</FONT><FONT color=#993333>key</FONT> <FONT color=#4444ff>:</FONT> <FONT color=#993333>integer</FONT><FONT color=#4444ff>)</FONT> <FONT color=#4444ff>:</FONT> <FONT color=#993333>integer</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=3_line3><STRONG>begin</STRONG></A>\r
+<A name=3_line4> <FONT color=#993333>Hash_Function</FONT> <FONT color=#4444ff>:</FONT><FONT color=#4444ff>=</FONT> <FONT color=#993333>key</FONT> <FONT color=#993333>MOD</FONT> <FONT color=#993333>HASH_LENGTH</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=3_line5><STRONG>end</STRONG><FONT color=#4444ff>;</FONT></A>\r
+</PRE><PRE></PRE><!-- code2html delete stop -->\r
+ <P>If we now want to insert a record into the hash we could do it this \r
+ way: \r
+ <P><!-- code2html add pas
+procedure Insert_Into_Hash( VAR hash : THash_table;
+ rec : THash_record);
+begin
+ hash[ Hash_Function(rec.key) ] := rec;
+end;
+--><!-- code2html delete start --><PRE><A name=4_line1></A>\r
+<A name=4_line2><STRONG>procedure</STRONG> <FONT color=#993333>Insert_Into_Hash</FONT><FONT color=#4444ff>(</FONT> <FONT color=#993333>VAR</FONT> <FONT color=#993333>hash</FONT> <FONT color=#4444ff>:</FONT> <FONT color=#993333>THash_table</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=4_line3> <FONT color=#993333>rec</FONT> <FONT color=#4444ff>:</FONT> <FONT color=#993333>THash_record</FONT><FONT color=#4444ff>)</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=4_line4><STRONG>begin</STRONG></A>\r
+<A name=4_line5> <FONT color=#993333>hash</FONT><FONT color=#4444ff>[</FONT> <FONT color=#993333>Hash_Function</FONT><FONT color=#4444ff>(</FONT><FONT color=#993333>rec<FONT color=#4444ff>.</FONT>key</FONT><FONT color=#4444ff>)</FONT> <FONT color=#4444ff>]</FONT> <FONT color=#4444ff>:</FONT><FONT color=#4444ff>=</FONT> <FONT color=#993333>rec</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=4_line6><STRONG>end</STRONG><FONT color=#4444ff>;</FONT></A>\r
+</PRE><PRE></PRE><!-- code2html delete stop -->\r
+ <P>But wait! What happens if two different keys return the same hash \r
+ address from the hash function? Well if you have a good hash function this \r
+ happens very rarely but it can and will happen. There are two ways to \r
+ handle a so called 'hash collision'. \r
+ <P>\r
+ <UL>\r
+ <LI>collision handling within the hash table \r
+ <LI>collision handling outside of the hash table </LI></UL>\r
+ <H2>COLLISION HANDLING OUTSIDE OF THE HASH TABLE ...</H2>... means that \r
+ our hash table no longer is an array of records but instead it is an array \r
+ of pointers. Each pointer points to a linked list of the hash records. \r
+ <P><!-- code2html add pas
+type
+ PHash_Record = ^THash_Record; {a pointer type to the type THash_record }
+ THash_Record = record
+ key : integer;
+ data : integer;
+ next : PHash_Record; { the pointer to the next item in the list }
+ end;
+
+ THash_Table = array[0..HASH_LENGTH-1] of PHash_Record;
+--><!-- code2html delete start --><PRE><A name=5_line1></A>\r
+<A name=5_line2><STRONG>type</STRONG></A>\r
+<A name=5_line3> <FONT color=#993333>PHash_Record</FONT> <FONT color=#4444ff>=</FONT> ^<FONT color=#993333>THash_Record</FONT><FONT color=#4444ff>;</FONT> <FONT color=#444444>{a pointer type to the type THash_record }</FONT></A>\r
+<A name=5_line4> <FONT color=#993333>THash_Record</FONT> <FONT color=#4444ff>=</FONT> <STRONG>record</STRONG></A>\r
+<A name=5_line5> <FONT color=#993333>key</FONT> <FONT color=#4444ff>:</FONT> <FONT color=#993333>integer</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=5_line6> <FONT color=#993333>data</FONT> <FONT color=#4444ff>:</FONT> <FONT color=#993333>integer</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=5_line7> <FONT color=#993333>next</FONT> <FONT color=#4444ff>:</FONT> <FONT color=#993333>PHash_Record</FONT><FONT color=#4444ff>;</FONT> <FONT color=#444444>{ the pointer to the next item in the list }</FONT></A>\r
+<A name=5_line8> <STRONG>end</STRONG><FONT color=#4444ff>;</FONT></A>\r
+<A name=5_line9></A>\r
+<A name=5_line10> <FONT color=#993333>THash_Table</FONT> <FONT color=#4444ff>=</FONT> <STRONG>array</STRONG><FONT color=#4444ff>[</FONT><FONT color=#ff0000>0..</FONT><FONT color=#993333>HASH_LENGTH</FONT><FONT color=#4444ff>-</FONT><FONT color=#ff0000>1</FONT><FONT color=#4444ff>]</FONT> <STRONG>of</STRONG> <FONT color=#993333>PHash_Record</FONT><FONT color=#4444ff>;</FONT></A>\r
+</PRE><PRE></PRE><!-- code2html delete stop -->\r
+ <P>If now a key return the same 'hash address' like an already stored item \r
+ we simply insert the record into the list of this hash entry. \r
+ <P><!-- code2html add pas
+procedure Insert_Into_Hash( VAR hash : THash_Table;
+ rec : THash_Record);
+VAR
+ hash_address : integer;
+ item : PHash_record;
+begin
+ hash_address := Hash_Function(rec.key);
+
+ new(item);
+ item^ := rec;
+ item^.next = hash[ hash_address ];
+ hash[ hash_address ] := item;
+end;
+--><!-- code2html delete start --><PRE><A name=6_line1></A>\r
+<A name=6_line2><STRONG>procedure</STRONG> <FONT color=#993333>Insert_Into_Hash</FONT><FONT color=#4444ff>(</FONT> <FONT color=#993333>VAR</FONT> <FONT color=#993333>hash</FONT> <FONT color=#4444ff>:</FONT> <FONT color=#993333>THash_Table</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=6_line3> <FONT color=#993333>rec</FONT> <FONT color=#4444ff>:</FONT> <FONT color=#993333>THash_Record</FONT><FONT color=#4444ff>)</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=6_line4><FONT color=#993333>VAR</FONT></A>\r
+<A name=6_line5> <FONT color=#993333>hash_address</FONT> <FONT color=#4444ff>:</FONT> <FONT color=#993333>integer</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=6_line6> <FONT color=#993333>item</FONT> <FONT color=#4444ff>:</FONT> <FONT color=#993333>PHash_record</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=6_line7><STRONG>begin</STRONG></A>\r
+<A name=6_line8> <FONT color=#993333>hash_address</FONT> <FONT color=#4444ff>:</FONT><FONT color=#4444ff>=</FONT> <FONT color=#993333>Hash_Function</FONT><FONT color=#4444ff>(</FONT><FONT color=#993333>rec<FONT color=#4444ff>.</FONT>key</FONT><FONT color=#4444ff>)</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=6_line9></A>\r
+<A name=6_line10> <FONT color=#993333>new</FONT><FONT color=#4444ff>(</FONT><FONT color=#993333>item</FONT><FONT color=#4444ff>)</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=6_line11> <FONT color=#993333>item</FONT>^ <FONT color=#4444ff>:</FONT><FONT color=#4444ff>=</FONT> <FONT color=#993333>rec</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=6_line12> <FONT color=#993333>item<FONT color=#4444ff>^.</FONT>next</FONT> <FONT color=#4444ff>=</FONT> <FONT color=#993333>hash</FONT><FONT color=#4444ff>[</FONT> <FONT color=#993333>hash_address</FONT> <FONT color=#4444ff>]</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=6_line13> <FONT color=#993333>hash</FONT><FONT color=#4444ff>[</FONT> <FONT color=#993333>hash_address</FONT> <FONT color=#4444ff>]</FONT> <FONT color=#4444ff>:</FONT><FONT color=#4444ff>=</FONT> <FONT color=#993333>item</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=6_line14><STRONG>end</STRONG><FONT color=#4444ff>;</FONT></A>\r
+</PRE><PRE></PRE><!-- code2html delete stop -->\r
+ <P>To get an item out of the hash you can first determine it's hash \r
+ address with the hash function and then use a classical linear search to \r
+ find the item you want. If you keep the list sorted you could speed read \r
+ access up for some cost at inserting items. \r
+ <P><!-- code2html add pas
+procedure Get_From_Hash( hash : THash_Table;
+ key : integer;
+ VAR rec : THash_Record);
+VAR
+ hash_address : integer;
+ item : PHash_record;
+begin
+ hash_address := Hash_Function(rec.key);
+
+ item := hash[ hash_address ];
+ while (item <> nil) and (item^.key <> key) do { make sure you have short }
+ item := item^.next; { curcuit bool evaluation, so }
+ { that the second comparison }
+ { is never made if item is nil}
+ if (item<>nil) then
+ rec := item^
+ else
+ { ITEM NOT IN LIST! }
+end;
+--><!-- code2html delete start --><PRE><A name=7_line1></A>\r
+<A name=7_line2><STRONG>procedure</STRONG> <FONT color=#993333>Get_From_Hash</FONT><FONT color=#4444ff>(</FONT> <FONT color=#993333>hash</FONT> <FONT color=#4444ff>:</FONT> <FONT color=#993333>THash_Table</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=7_line3> <FONT color=#993333>key</FONT> <FONT color=#4444ff>:</FONT> <FONT color=#993333>integer</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=7_line4> <FONT color=#993333>VAR</FONT> <FONT color=#993333>rec</FONT> <FONT color=#4444ff>:</FONT> <FONT color=#993333>THash_Record</FONT><FONT color=#4444ff>)</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=7_line5><FONT color=#993333>VAR</FONT></A>\r
+<A name=7_line6> <FONT color=#993333>hash_address</FONT> <FONT color=#4444ff>:</FONT> <FONT color=#993333>integer</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=7_line7> <FONT color=#993333>item</FONT> <FONT color=#4444ff>:</FONT> <FONT color=#993333>PHash_record</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=7_line8><STRONG>begin</STRONG></A>\r
+<A name=7_line9> <FONT color=#993333>hash_address</FONT> <FONT color=#4444ff>:</FONT><FONT color=#4444ff>=</FONT> <FONT color=#993333>Hash_Function</FONT><FONT color=#4444ff>(</FONT><FONT color=#993333>rec<FONT color=#4444ff>.</FONT>key</FONT><FONT color=#4444ff>)</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=7_line10></A>\r
+<A name=7_line11> <FONT color=#993333>item</FONT> <FONT color=#4444ff>:</FONT><FONT color=#4444ff>=</FONT> <FONT color=#993333>hash</FONT><FONT color=#4444ff>[</FONT> <FONT color=#993333>hash_address</FONT> <FONT color=#4444ff>]</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=7_line12> <STRONG>while</STRONG> <FONT color=#4444ff>(</FONT><FONT color=#993333>item</FONT> <FONT color=#4444ff><</FONT><FONT color=#4444ff>></FONT> <STRONG>nil</STRONG><FONT color=#4444ff>)</FONT> <STRONG>and</STRONG> <FONT color=#4444ff>(</FONT><FONT color=#993333>item<FONT color=#4444ff>^.</FONT>key</FONT> <FONT color=#4444ff><</FONT><FONT color=#4444ff>></FONT> <FONT color=#993333>key</FONT><FONT color=#4444ff>)</FONT> <STRONG>do</STRONG> <FONT color=#444444>{ make sure you have short }</FONT></A>\r
+<A name=7_line13> <FONT color=#993333>item</FONT> <FONT color=#4444ff>:</FONT><FONT color=#4444ff>=</FONT> <FONT color=#993333>item<FONT color=#4444ff>^.</FONT>next</FONT><FONT color=#4444ff>;</FONT> <FONT color=#444444>{ curcuit bool evaluation, so }</FONT></A>\r
+<A name=7_line14> <FONT color=#444444>{ that the second comparison }</FONT></A>\r
+<A name=7_line15> <FONT color=#444444>{ is never made if item is nil}</FONT></A>\r
+<A name=7_line16> <STRONG>if</STRONG> <FONT color=#4444ff>(</FONT><FONT color=#993333>item</FONT><FONT color=#4444ff><</FONT><FONT color=#4444ff>></FONT><STRONG>nil</STRONG><FONT color=#4444ff>)</FONT> <STRONG>then</STRONG></A>\r
+<A name=7_line17> <FONT color=#993333>rec</FONT> <FONT color=#4444ff>:</FONT><FONT color=#4444ff>=</FONT> <FONT color=#993333>item</FONT>^</A>\r
+<A name=7_line18> <STRONG>else</STRONG></A>\r
+<A name=7_line19> <FONT color=#444444>{ ITEM NOT IN LIST! }</FONT></A>\r
+<A name=7_line20><STRONG>end</STRONG><FONT color=#4444ff>;</FONT></A>\r
+</PRE><PRE></PRE><!-- code2html delete stop -->\r
+ <P>If you want to delete an item, you simply remove it from the linked \r
+ list: \r
+ <P><!-- code2html add pas
+procedure Remove_From_Hash( VAR hash : THash_Table;
+ key : integer);
+VAR
+ hash_address : integer;
+ item : PHash_record;
+ tmp : PHash_record;
+begin
+ hash_address := Hash_Function(rec.key);
+
+ item := hash[ hash_address ];
+ if (item<>nil) and (item^.key = key) then { make sure you have short }
+ begin { curcuit bool evaluation, so }
+ hash[ hash_address ] := item^.next { that the second comparison }
+ dispose(item); { deallocate memory } { is never made if item is nil}
+ end
+ else
+ begin
+ while (item^.next <> nil) and
+ (item^.next^.key <> key) do
+ item := item^.next;
+
+ if (item^.next <> nil) then
+ begin
+ tmp := item^.next;
+ item^.next := tmp^.next;
+ dispose(tmp); { deallocate memory }
+ end
+ else
+ { ITEM NOT IN LIST! }
+ end;
+end;
+--><!-- code2html delete start --><PRE><A name=8_line1></A>\r
+<A name=8_line2><STRONG>procedure</STRONG> <FONT color=#993333>Remove_From_Hash</FONT><FONT color=#4444ff>(</FONT> <FONT color=#993333>VAR</FONT> <FONT color=#993333>hash</FONT> <FONT color=#4444ff>:</FONT> <FONT color=#993333>THash_Table</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=8_line3> <FONT color=#993333>key</FONT> <FONT color=#4444ff>:</FONT> <FONT color=#993333>integer</FONT><FONT color=#4444ff>)</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=8_line4><FONT color=#993333>VAR</FONT></A>\r
+<A name=8_line5> <FONT color=#993333>hash_address</FONT> <FONT color=#4444ff>:</FONT> <FONT color=#993333>integer</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=8_line6> <FONT color=#993333>item</FONT> <FONT color=#4444ff>:</FONT> <FONT color=#993333>PHash_record</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=8_line7> <FONT color=#993333>tmp</FONT> <FONT color=#4444ff>:</FONT> <FONT color=#993333>PHash_record</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=8_line8><STRONG>begin</STRONG></A>\r
+<A name=8_line9> <FONT color=#993333>hash_address</FONT> <FONT color=#4444ff>:</FONT><FONT color=#4444ff>=</FONT> <FONT color=#993333>Hash_Function</FONT><FONT color=#4444ff>(</FONT><FONT color=#993333>rec<FONT color=#4444ff>.</FONT>key</FONT><FONT color=#4444ff>)</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=8_line10></A>\r
+<A name=8_line11> <FONT color=#993333>item</FONT> <FONT color=#4444ff>:</FONT><FONT color=#4444ff>=</FONT> <FONT color=#993333>hash</FONT><FONT color=#4444ff>[</FONT> <FONT color=#993333>hash_address</FONT> <FONT color=#4444ff>]</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=8_line12> <STRONG>if</STRONG> <FONT color=#4444ff>(</FONT><FONT color=#993333>item</FONT><FONT color=#4444ff><</FONT><FONT color=#4444ff>></FONT><STRONG>nil</STRONG><FONT color=#4444ff>)</FONT> <STRONG>and</STRONG> <FONT color=#4444ff>(</FONT><FONT color=#993333>item<FONT color=#4444ff>^.</FONT>key</FONT> <FONT color=#4444ff>=</FONT> <FONT color=#993333>key</FONT><FONT color=#4444ff>)</FONT> <STRONG>then</STRONG> <FONT color=#444444>{ make sure you have short }</FONT></A>\r
+<A name=8_line13> <STRONG>begin</STRONG> <FONT color=#444444>{ curcuit bool evaluation, so }</FONT></A>\r
+<A name=8_line14> <FONT color=#993333>hash</FONT><FONT color=#4444ff>[</FONT> <FONT color=#993333>hash_address</FONT> <FONT color=#4444ff>]</FONT> <FONT color=#4444ff>:</FONT><FONT color=#4444ff>=</FONT> <FONT color=#993333>item<FONT color=#4444ff>^.</FONT>next</FONT> <FONT color=#444444>{ that the second comparison }</FONT></A>\r
+<A name=8_line15> <FONT color=#993333>dispose</FONT><FONT color=#4444ff>(</FONT><FONT color=#993333>item</FONT><FONT color=#4444ff>)</FONT><FONT color=#4444ff>;</FONT> <FONT color=#444444>{ deallocate memory }</FONT> <FONT color=#444444>{ is never made if item is nil}</FONT></A>\r
+<A name=8_line16> <STRONG>end</STRONG></A>\r
+<A name=8_line17> <STRONG>else</STRONG></A>\r
+<A name=8_line18> <STRONG>begin</STRONG></A>\r
+<A name=8_line19> <STRONG>while</STRONG> <FONT color=#4444ff>(</FONT><FONT color=#993333>item<FONT color=#4444ff>^.</FONT>next</FONT> <FONT color=#4444ff><</FONT><FONT color=#4444ff>></FONT> <STRONG>nil</STRONG><FONT color=#4444ff>)</FONT> <STRONG>and</STRONG></A>\r
+<A name=8_line20> <FONT color=#4444ff>(</FONT><FONT color=#993333>item<FONT color=#4444ff>^.</FONT>next<FONT color=#4444ff>^.</FONT>key</FONT> <FONT color=#4444ff><</FONT><FONT color=#4444ff>></FONT> <FONT color=#993333>key</FONT><FONT color=#4444ff>)</FONT> <STRONG>do</STRONG></A>\r
+<A name=8_line21> <FONT color=#993333>item</FONT> <FONT color=#4444ff>:</FONT><FONT color=#4444ff>=</FONT> <FONT color=#993333>item<FONT color=#4444ff>^.</FONT>next</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=8_line22></A>\r
+<A name=8_line23> <STRONG>if</STRONG> <FONT color=#4444ff>(</FONT><FONT color=#993333>item<FONT color=#4444ff>^.</FONT>next</FONT> <FONT color=#4444ff><</FONT><FONT color=#4444ff>></FONT> <STRONG>nil</STRONG><FONT color=#4444ff>)</FONT> <STRONG>then</STRONG></A>\r
+<A name=8_line24> <STRONG>begin</STRONG></A>\r
+<A name=8_line25> <FONT color=#993333>tmp</FONT> <FONT color=#4444ff>:</FONT><FONT color=#4444ff>=</FONT> <FONT color=#993333>item<FONT color=#4444ff>^.</FONT>next</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=8_line26> <FONT color=#993333>item<FONT color=#4444ff>^.</FONT>next</FONT> <FONT color=#4444ff>:</FONT><FONT color=#4444ff>=</FONT> <FONT color=#993333>tmp<FONT color=#4444ff>^.</FONT>next</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=8_line27> <FONT color=#993333>dispose</FONT><FONT color=#4444ff>(</FONT><FONT color=#993333>tmp</FONT><FONT color=#4444ff>)</FONT><FONT color=#4444ff>;</FONT> <FONT color=#444444>{ deallocate memory }</FONT></A>\r
+<A name=8_line28> <STRONG>end</STRONG></A>\r
+<A name=8_line29> <STRONG>else</STRONG></A>\r
+<A name=8_line30> <FONT color=#444444>{ ITEM NOT IN LIST! }</FONT></A>\r
+<A name=8_line31> <STRONG>end</STRONG><FONT color=#4444ff>;</FONT></A>\r
+<A name=8_line32><STRONG>end</STRONG><FONT color=#4444ff>;</FONT></A>\r
+</PRE><PRE></PRE><!-- code2html delete stop -->\r
+ <H2>COLLISION HANDLING WITHIN THE HASH TABLE...</H2>... is totally \r
+ different. Instead of having a list which can grow up to an arbitrary size \r
+ all the data is stored in the hash table itself. This means that we can \r
+ never under any circumstance store more records in the hash as our hash is \r
+ long. This is obvious but I wanted to point it out. \r
+ <UL>\r
+ <LI>So what to do if the position we want to save our new record to is \r
+ already occupied? \r
+ <LI>And how do we know that it is occupied anyway? </LI></UL>\r
+ <P>Let's first solve the latter question since it is quite simply. We have \r
+ to store wheter a certain hash element is occupied. We do this by changing \r
+ the THash_Record record: <!-- code2html add pas
+type
+ THash_Occupied = (ho_empty, ho_occupied);
+
+ THash_Record = record
+ occupied : THash_Occupied;
+ key : integer;
+ data : integer;
+ end;
+--><!-- code2html delete start --><PRE><A name=9_line1></A>\r
+<A name=9_line2><STRONG>type</STRONG></A>\r
+<A name=9_line3> <FONT color=#993333>THash_Occupied</FONT> <FONT color=#4444ff>=</FONT> <FONT color=#4444ff>(</FONT><FONT color=#993333>ho_empty</FONT>, <FONT color=#993333>ho_occupied</FONT><FONT color=#4444ff>)</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=9_line4> </A>\r
+<A name=9_line5> <FONT color=#993333>THash_Record</FONT> <FONT color=#4444ff>=</FONT> <STRONG>record</STRONG></A>\r
+<A name=9_line6> <FONT color=#993333>occupied</FONT> <FONT color=#4444ff>:</FONT> <FONT color=#993333>THash_Occupied</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=9_line7> <FONT color=#993333>key</FONT> <FONT color=#4444ff>:</FONT> <FONT color=#993333>integer</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=9_line8> <FONT color=#993333>data</FONT> <FONT color=#4444ff>:</FONT> <FONT color=#993333>integer</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=9_line9> <STRONG>end</STRONG><FONT color=#4444ff>;</FONT></A>\r
+</PRE><PRE></PRE><!-- code2html delete stop -->\r
+ <P>So now to the former question: What to do if an address is already \r
+ occupied. The answer is straightforward: The have to store it at a \r
+ different address :) There are several methods to find a new, empty \r
+ address. Note that this address should have something to do with the key \r
+ since we want to be able to find it easily later. \r
+ <H3>linear probing:</H3>We add a constant number (usually 1) to the \r
+ position the hash_function returns until we have found an empty place: <!-- code2html add pas
+ pos0 := Hash_Function(key);
+ i := 0;
+ repeat
+ hash_address := (pos0 + i) MOD HASH_LENGTH;
+ inc(i);
+ until Hash[ hash_address].occupied <> ho_occupied;
+--><!-- code2html delete start --><PRE><A name=10_line1></A>\r
+<A name=10_line2> <FONT color=#993333>pos0</FONT> <FONT color=#4444ff>:</FONT><FONT color=#4444ff>=</FONT> <FONT color=#993333>Hash_Function</FONT><FONT color=#4444ff>(</FONT><FONT color=#993333>key</FONT><FONT color=#4444ff>)</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=10_line3> <FONT color=#993333>i</FONT> <FONT color=#4444ff>:</FONT><FONT color=#4444ff>=</FONT> <FONT color=#ff0000>0</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=10_line4> <STRONG>repeat</STRONG></A>\r
+<A name=10_line5> <FONT color=#993333>hash_address</FONT> <FONT color=#4444ff>:</FONT><FONT color=#4444ff>=</FONT> <FONT color=#4444ff>(</FONT><FONT color=#993333>pos0</FONT> <FONT color=#4444ff>+</FONT> <FONT color=#993333>i</FONT><FONT color=#4444ff>)</FONT> <FONT color=#993333>MOD</FONT> <FONT color=#993333>HASH_LENGTH</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=10_line6> <FONT color=#993333>inc</FONT><FONT color=#4444ff>(</FONT><FONT color=#993333>i</FONT><FONT color=#4444ff>)</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=10_line7> <STRONG>until</STRONG> <FONT color=#993333>Hash</FONT><FONT color=#4444ff>[</FONT> <FONT color=#993333>hash_address</FONT><FONT color=#4444ff>]</FONT>.<FONT color=#993333>occupied</FONT> <FONT color=#4444ff><</FONT><FONT color=#4444ff>></FONT> <FONT color=#993333>ho_occupied</FONT><FONT color=#4444ff>;</FONT></A>\r
+</PRE><PRE></PRE><!-- code2html delete stop -->\r
+ <H3>sqared probing:</H3>is very similar to linear probing but we do not \r
+ simply add the increasing value but we add it's square. This is usually \r
+ better than linear probing: <!-- code2html add pas
+ pos0 := Hash_Function(key);
+ i := 0;
+ repeat
+ hash_address := (pos0 + i*i) MOD HASH_LENGTH;
+ inc(i);
+ until Hash[ hash_address].occupied <> ho_occupied;
+--><!-- code2html delete start --><PRE><A name=11_line1></A>\r
+<A name=11_line2> <FONT color=#993333>pos0</FONT> <FONT color=#4444ff>:</FONT><FONT color=#4444ff>=</FONT> <FONT color=#993333>Hash_Function</FONT><FONT color=#4444ff>(</FONT><FONT color=#993333>key</FONT><FONT color=#4444ff>)</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=11_line3> <FONT color=#993333>i</FONT> <FONT color=#4444ff>:</FONT><FONT color=#4444ff>=</FONT> <FONT color=#ff0000>0</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=11_line4> <STRONG>repeat</STRONG></A>\r
+<A name=11_line5> <FONT color=#993333>hash_address</FONT> <FONT color=#4444ff>:</FONT><FONT color=#4444ff>=</FONT> <FONT color=#4444ff>(</FONT><FONT color=#993333>pos0</FONT> <FONT color=#4444ff>+</FONT> <FONT color=#993333>i</FONT><FONT color=#4444ff>*</FONT><FONT color=#993333>i</FONT><FONT color=#4444ff>)</FONT> <FONT color=#993333>MOD</FONT> <FONT color=#993333>HASH_LENGTH</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=11_line6> <FONT color=#993333>inc</FONT><FONT color=#4444ff>(</FONT><FONT color=#993333>i</FONT><FONT color=#4444ff>)</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=11_line7> <STRONG>until</STRONG> <FONT color=#993333>Hash</FONT><FONT color=#4444ff>[</FONT> <FONT color=#993333>hash_address</FONT><FONT color=#4444ff>]</FONT>.<FONT color=#993333>occupied</FONT> <FONT color=#4444ff><</FONT><FONT color=#4444ff>></FONT> <FONT color=#993333>ho_occupied</FONT><FONT color=#4444ff>;</FONT></A>\r
+</PRE><PRE></PRE><!-- code2html delete stop -->\r
+ <P>One disadvantage of all those probing methods is that they tend to \r
+ build clusters aroung already occupied areas of the hash table. A soluton \r
+ to this problem is \r
+ <H3>double hashing:</H3>The idea is to add a value to the hash address \r
+ that depends on the key of the item, so that the probing order is spezific \r
+ to the key: <!-- code2html add pas
+ hash_address := Hash_Function(key);
+ while Hash[ hash_address].occupied = ho_occupied do
+ hash_address := (hash_address + Hash_Function(key)) MOD HASH_LENGTH;
+
+ double_hashing := hash_address;
+--><!-- code2html delete start --><PRE><A name=12_line1></A>\r
+<A name=12_line2> <FONT color=#993333>hash_address</FONT> <FONT color=#4444ff>:</FONT><FONT color=#4444ff>=</FONT> <FONT color=#993333>Hash_Function</FONT><FONT color=#4444ff>(</FONT><FONT color=#993333>key</FONT><FONT color=#4444ff>)</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=12_line3> <STRONG>while</STRONG> <FONT color=#993333>Hash</FONT><FONT color=#4444ff>[</FONT> <FONT color=#993333>hash_address</FONT><FONT color=#4444ff>]</FONT>.<FONT color=#993333>occupied</FONT> <FONT color=#4444ff>=</FONT> <FONT color=#993333>ho_occupied</FONT> <STRONG>do</STRONG></A>\r
+<A name=12_line4> <FONT color=#993333>hash_address</FONT> <FONT color=#4444ff>:</FONT><FONT color=#4444ff>=</FONT> <FONT color=#4444ff>(</FONT><FONT color=#993333>hash_address</FONT> <FONT color=#4444ff>+</FONT> <FONT color=#993333>Hash_Function</FONT><FONT color=#4444ff>(</FONT><FONT color=#993333>key</FONT><FONT color=#4444ff>)</FONT><FONT color=#4444ff>)</FONT> <FONT color=#993333>MOD</FONT> <FONT color=#993333>HASH_LENGTH</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=12_line5> </A>\r
+<A name=12_line6> <FONT color=#993333>double_hashing</FONT> <FONT color=#4444ff>:</FONT><FONT color=#4444ff>=</FONT> <FONT color=#993333>hash_address</FONT><FONT color=#4444ff>;</FONT></A>\r
+</PRE><PRE></PRE><!-- code2html delete stop -->\r
+ <P>Hash_Function(rec.key) and HASH_LENGTH should have a greatest common \r
+ factor of 1 so that the complete hash table is probed. This is guaranteed \r
+ if HASH_LENGTH is a prime number. \r
+ <P> \r
+ <P>So inserting an item looks like this: <!-- code2html add pas
+procedure Insert_Into_Hash( VAR hash : THash_Table;
+ rec : THash_Record);
+VAR
+ hash_address;
+begin
+
+ <get the hash address, probing for an empty entry>
+ hash[ hash_address ] := rec;
+ rec.occupied := ho_occupied;
+end;
+--><!-- code2html delete start --><PRE><A name=13_line1></A>\r
+<A name=13_line2><STRONG>procedure</STRONG> <FONT color=#993333>Insert_Into_Hash</FONT><FONT color=#4444ff>(</FONT> <FONT color=#993333>VAR</FONT> <FONT color=#993333>hash</FONT> <FONT color=#4444ff>:</FONT> <FONT color=#993333>THash_Table</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=13_line3> <FONT color=#993333>rec</FONT> <FONT color=#4444ff>:</FONT> <FONT color=#993333>THash_Record</FONT><FONT color=#4444ff>)</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=13_line4><FONT color=#993333>VAR</FONT></A>\r
+<A name=13_line5> <FONT color=#993333>hash_address</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=13_line6><STRONG>begin</STRONG></A>\r
+<A name=13_line7> </A>\r
+<A name=13_line8> <FONT color=#4444ff><</FONT><FONT color=#993333>get</FONT> <FONT color=#993333>the</FONT> <FONT color=#993333>hash</FONT> <FONT color=#993333>address</FONT>, <FONT color=#993333>probing</FONT> <STRONG>for</STRONG> <FONT color=#993333>an</FONT> <FONT color=#993333>empty</FONT> <FONT color=#993333>entry</FONT><FONT color=#4444ff>></FONT></A>\r
+<A name=13_line9> <FONT color=#993333>hash</FONT><FONT color=#4444ff>[</FONT> <FONT color=#993333>hash_address</FONT> <FONT color=#4444ff>]</FONT> <FONT color=#4444ff>:</FONT><FONT color=#4444ff>=</FONT> <FONT color=#993333>rec</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=13_line10> <FONT color=#993333>rec<FONT color=#4444ff>.</FONT>occupied</FONT> <FONT color=#4444ff>:</FONT><FONT color=#4444ff>=</FONT> <FONT color=#993333>ho_occupied</FONT><FONT color=#4444ff>;</FONT></A>\r
+<A name=13_line11><STRONG>end</STRONG><FONT color=#4444ff>;</FONT></A>\r
+</PRE><PRE></PRE><!-- code2html delete stop -->\r
+ <P>To search for an item, you have to first get the hash_address and then \r
+ probe until you either find an empty entry or the searched entry. \r
+ <P>Deleting an item is rather simple: Search for the address like when you \r
+ search the item and set the occupied value to ho_occupied. But wait! This \r
+ would break our searching, since we search until we either find the object \r
+ or an empty entry. \r
+ <P>The solution is to modify THash_Occupied a bit so that it reads: <!-- code2html add pas
+ THash_Occupied = (ho_empty, ho_occupied, ho_deleted);
+--><!-- code2html delete start --><PRE><A name=14_line1></A>\r
+<A name=14_line2> <FONT color=#993333>THash_Occupied</FONT> <FONT color=#4444ff>=</FONT> <FONT color=#4444ff>(</FONT><FONT color=#993333>ho_empty</FONT>, <FONT color=#993333>ho_occupied</FONT>, <FONT color=#993333>ho_deleted</FONT><FONT color=#4444ff>)</FONT><FONT color=#4444ff>;</FONT></A>\r
+</PRE><PRE></PRE><!-- code2html delete stop -->\r
+ <P>If we delete an item we set the occupied state to ho_deleted. When \r
+ inserting Items we treat ho_deleted like it was ho_empty and when \r
+ searching for an item we treat as if it was ho_occupied. \r
+ <P> \r
+ <P> \r
+ <P> \r
+ <P> \r
+ <P> \r
+ <P>If you have questions, feel free to contact me! </P></TD></TR>\r
+ <TR>\r
+ <TD>\r
+ <HR SIZE=1>\r
+ </TD></TR>\r
+ <TR>\r
+ <TD><FONT face=verdana,arial,helvetica size=1><!-- hhmts start -->Last \r
+ modified: Sun Aug 1 20:26:14 CEST 1999 <!-- hhmts end -->by <A \r
+ href="mailto:weasel@netalive.org">Peter Palfrader</A></FONT> \r
+ <BR></TD></TR></TBODY></TABLE></BODY></HTML>\r
--- /dev/null
+<HEAD>
+<TITLE>Heapsort
+</TITLE>
+<BODY>
+<H2>
+<H3>
+<A HREF="../../images/handbook.gif"><IMG SRC="../../images/handbook2.gif" align=left></A>
+<A HREF="../../hbook.html">
+<IMG SRC="../../images/home_g.gif" hspace = 15 vspace = 4 ALT = "[Home]"></A><BR>
+<A HREF="../../sort_a.html">
+<IMG SRC="../../images/chapter_g.gif" hspace = 15 vspace = 4 ALT = "[Chapter]"></A><BR>
+<A HREF="../../expand.html">
+<IMG SRC="../../images/contents_g.gif" hspace = 15 vspace = 4 ALT = "[Contents]"></A><BR>
+<A HREF="415.sort.c.html">
+</A>
+<A HREF="415.sort.c.html">
+<IMG SRC="../../images/prevalg_g.gif" hspace = 15 vspace = 4 ALT = "[Previous Algorithm]"></A><BR>
+<A HREF="416.sort.c.html">
+<IMG SRC="../../images/nextalg_g.gif" hspace = 15 vspace = 4 ALT = "[Next Algorithm]"></A><BR>
+<BR></H2>
+<HR>
+<H2><B>Heapsort
+</B></H2><BR>
+<CENTER>
+<TABLE BORDER>
+<TR>
+<TD COLSPAN = 1>
+<TD rowspan = 1>
+<TR><TD>
+<XMP>
+ procedure sort( var r : ArrayToSort; lo, up : integer );
+
+ var i : integer;
+ tempr : ArrayEntry;
+ begin
+ {*** construct heap ***}
+ for i := (up div 2) downto 2 do siftup(r,i,up);
+ {*** repeatedly extract maximum ***}
+ for i := up downto 2 do begin
+ siftup(r,1,i);
+ tempr := r[1];
+ r[1] := r[i];
+ r[i] := tempr
+ end
+ end;
+</XMP></TD></TR></TABLE>
+<BR>
+<H3><A HREF="ftp://sunsite.dcc.uchile.cl/pub/users/rbaeza/handbook/algs/4/415.sort.c"><IMG SRC="../../images/ftp.xbm" hspace=10>C</A> source (415.sort.c) <A HREF="ftp://sunsite.dcc.uchile.cl/pub/users/rbaeza/handbook/algs/4/415.sort.p"><IMG SRC="../../images/ftp.xbm" hspace=10>Pascal</A> source (415.sort.p)
+</H3></CENTER>
+<HR><H4>
+<IMG SRC="../../images/aw3.gif" align=left><H5><BR>
+© <A HREF="http://aw.com">Addison-Wesley </A>Publishing Co. Inc.
+</H5></H4><HR>
+</BODY>
--- /dev/null
+<HEAD>
+<TITLE>Interpolation (in-place) sort
+</TITLE>
+<BODY>
+<H2>
+<H3>
+<A HREF="../../images/handbook.gif"><IMG SRC="../../images/handbook2.gif" align=left></A>
+<A HREF="../../hbook.html">
+<IMG SRC="../../images/home_g.gif" hspace = 15 vspace = 4 ALT = "[Home]"></A><BR>
+<A HREF="../../expand.html">
+<IMG SRC="../../images/contents_g.gif" hspace = 15 vspace = 4 ALT = "[Contents]"></A><BR>
+<A HREF="../../sort_a.html">
+<IMG SRC="../../images/chapter_g.gif" hspace = 15 vspace = 4 ALT = "[Chapter]"></A><BR>
+<A HREF="416.sort.c.html"><IMG SRC="../../images/prevalg_g.gif" hspace = 15 vspace = 4 ALT = "[Previous Algorithm]"></A><BR>
+<A HREF="417.sort.c.html">
+<IMG SRC="../../images/nextalg_g.gif" hspace = 15 vspace = 4 ALT = "[Next Algorithm]"></A><BR>
+</A>
+<BR></H2>
+<HR>
+<H2><B>Interpolation (in-place) sort
+</B></H2><BR>
+<CENTER>
+<TABLE BORDER>
+<TR>
+<TD COLSPAN = 1>
+<TD rowspan = 1>
+<TR><TD>
+<XMP>
+ sort( r, lo, up )
+ ArrayToSort r;
+ int lo, up;
+
+ {ArrayIndices iwk;
+ ArrayEntry tempr;
+ int i, j;
+
+ for (i=lo; i<=up; i++) {iwk[i] = 0; r[i].k = -r[i].k;}
+ iwk[lo] = lo-1;
+ for (i=lo; i<=up; i++) iwk[ phi(-r[i].k,lo,up) ]++;
+ for (i=lo; i<up; i++) iwk[i+1] += iwk[i];
+ for (i=up; i>=lo; i--) if ( r[i].k<0 )
+ do {
+ r[i].k = -r[i].k;
+ j = iwk[ phi( r[i].k, lo, up ) ]--;
+ tempr = r[i];
+ r[i] = r[j];
+ r[j] = tempr;
+ } while ( i != j );
+ for ( i=up-1; i>=lo; i-- ) {
+ tempr = r[i];
+ for ( j=i+1; j<=up && (tempr.k>r[j].k); j++ )
+ r[j-1] = r[j];
+ r[j-1] = tempr;
+ }
+ };
+</XMP></TD></TR></TABLE>
+<BR>
+<H3><A HREF="ftp://sunsite.dcc.uchile.cl/pub/users/rbaeza/handbook/algs/4/416b.sort.c"><IMG SRC="../../images/ftp.xbm" hspace=10>C</A> source (416b.sort.c) </H3></CENTER>
+<HR><H4>
+<IMG SRC="../../images/aw3.gif" align=left><H5><BR>
+© <A HREF="http://aw.com">Addison-Wesley </A>Publishing Co. Inc.
+</H5></H4><HR>
+</BODY>
--- /dev/null
+<HEAD>
+<TITLE>Linear probing hashing: search
+</TITLE>
+<BODY>
+<H2>
+<H3>
+<A HREF="../../images/handbook.gif"><IMG SRC="../../images/handbook2.gif" align=left></A>
+<A HREF="../../hbook.html">
+<IMG SRC="../../images/home_g.gif" hspace = 15 vspace = 4 ALT = "[Home]"></A><BR>
+<A HREF="../../search_a.html">
+<IMG SRC="../../images/chapter_g.gif" hspace = 15 vspace = 4 ALT = "[Chapter]"></A><BR>
+<A HREF="../../expand.html">
+<IMG SRC="../../images/contents_g.gif" hspace = 15 vspace = 4 ALT = "[Contents]"></A><BR>
+<A HREF="334.srch.c.html">
+</A>
+<A HREF="334.srch.c.html">
+<IMG SRC="../../images/prevalg_g.gif" hspace = 15 vspace = 4 ALT = "[Previous Algorithm]"></A><BR>
+<A HREF="335.ins.c.html">
+<IMG SRC="../../images/nextalg_g.gif" hspace = 15 vspace = 4 ALT = "[Next Algorithm]"></A><BR>
+<BR></H2>
+<HR>
+<H2><B>Linear probing hashing: search
+</B></H2><BR>
+<CENTER>
+<TABLE BORDER>
+<TR>
+<TD COLSPAN = 1>
+<TD rowspan = 1>
+<TR><TD>
+<XMP>
+ function search( key : typekey; var r : dataarray ) : integer;
+ var i, last : integer;
+
+ begin
+ i := hashfunction( key ) ;
+ last := (i+n-1) mod m;
+ while (i<>last) and (not empty(r[i])) and (r[i].k<>key) do
+ i := (i+1) mod m;
+ if r[i].k=key then search := i {*** found(r[i]) ***}
+ else search := -1; {*** notfound(key) ***}
+ end;
+</XMP></TD></TR></TABLE>
+<BR>
+<H3><A HREF="ftp://sunsite.dcc.uchile.cl/pub/users/rbaeza/handbook/algs/3/334.srch.c"><IMG SRC="../../images/ftp.xbm" hspace=10>C</A> source (334.srch.c) <A HREF="ftp://sunsite.dcc.uchile.cl/pub/users/rbaeza/handbook/algs/3/334.srch.p"><IMG SRC="../../images/ftp.xbm" hspace=10>Pascal</A> source (334.srch.p)
+</H3></CENTER>
+<HR><H4>
+<IMG SRC="../../images/aw3.gif" align=left><H5><BR>
+© <A HREF="http://aw.com">Addison-Wesley </A>Publishing Co. Inc.
+</H5></H4><HR>
+</BODY>
--- /dev/null
+<HEAD>
+<TITLE>Linear probing sort
+</TITLE>
+<BODY>
+<H2>
+<H3>
+<A HREF="../../images/handbook.gif"><IMG SRC="../../images/handbook2.gif" align=left></A>
+<A HREF="../../hbook.html">
+<IMG SRC="../../images/home_g.gif" hspace = 15 vspace = 4 ALT = "[Home]"></A><BR>
+<A HREF="../../sort_a.html">
+<IMG SRC="../../images/chapter_g.gif" hspace = 15 vspace = 4 ALT = "[Chapter]"></A><BR>
+<A HREF="../../expand.html">
+<IMG SRC="../../images/contents_g.gif" hspace = 15 vspace = 4 ALT = "[Contents]"></A><BR>
+<A HREF="417.sort.c.html">
+</A>
+<A HREF="417.sort.c.html">
+<IMG SRC="../../images/prevalg_g.gif" hspace = 15 vspace = 4 ALT = "[Previous Algorithm]"></A><BR>
+<A HREF="42.char.c.html">
+<IMG SRC="../../images/nextalg_g.gif" hspace = 15 vspace = 4 ALT = "[Next Algorithm]"></A><BR>
+<BR></H2>
+<HR>
+<H2><B>Linear probing sort
+</B></H2><BR>
+<CENTER>
+<TABLE BORDER>
+<TR>
+<TD COLSPAN = 1>
+<TD rowspan = 1>
+<TR><TD>
+<XMP>
+ procedure sort( var r : ArrayToSort; lo, up : integer );
+
+ var i, j : integer;
+ r1 : ArrayToSort;
+ begin
+ r1 := r;
+ for j:=lo to UppBoundr do r[j].k := NoKey;
+ for j:=lo to up do begin
+ i := phi(r1[j].k,lo,m);
+ while r[i].k <> NoKey do begin
+ if r1[j].k < r[i].k then begin
+ r1[j-1] := r[i];
+ r[i] := r1[j];
+ r1[j] := r1[j-1]
+ end;
+ i := i+1;
+ if i > UppBoundr then Error
+ end;
+ r[i] := r1[j]
+ end;
+ i := lo-1;
+ for j:=lo to UppBoundr do
+ if r[j].k <> NoKey then begin
+ i := i+1;
+ r[i] := r[j]
+ end;
+ for j:=i+1 to UppBoundr do r[j].k := NoKey;
+ end;
+</XMP></TD></TR></TABLE>
+<BR>
+<H3><A HREF="ftp://sunsite.dcc.uchile.cl/pub/users/rbaeza/handbook/algs/4/417.sort.c"><IMG SRC="../../images/ftp.xbm" hspace=10>C</A> source (417.sort.c) <A HREF="ftp://sunsite.dcc.uchile.cl/pub/users/rbaeza/handbook/algs/4/417.sort.p"><IMG SRC="../../images/ftp.xbm" hspace=10>Pascal</A> source (417.sort.p)
+</H3></CENTER>
+<HR><H4>
+<IMG SRC="../../images/aw3.gif" align=left><H5><BR>
+© <A HREF="http://aw.com">Addison-Wesley </A>Publishing Co. Inc.
+</H5></H4><HR>
+</BODY>
--- /dev/null
+<HEAD>
+<TITLE>Ordered hashing: insertion
+</TITLE>
+<BODY>
+<H2>
+<H3>
+<A HREF="../../images/handbook.gif"><IMG SRC="../../images/handbook2.gif" align=left></A>
+<A HREF="../../hbook.html">
+<IMG SRC="../../images/home_g.gif" hspace = 15 vspace = 4></A><BR>
+<A HREF="../../expand.html">
+<IMG SRC="../../images/contents_g.gif" hspace = 15 vspace = 4></A><BR>
+<A HREF="../../search_a.html">
+<IMG SRC="../../images/chapter_g.gif" hspace = 15 vspace = 4></A><BR>
+<A HREF="311.ins.c.html"><IMG SRC="../../images/prevalg_g.gif" hspace = 15 vspace = 4></A><BR>
+<A HREF="311c.srch.c.html">
+<IMG SRC="../../images/nextalg_g.gif" hspace = 15 vspace = 4></A><BR>
+<BR></H2>
+<HR>
+<H2><B>Ordered hashing: insertion
+</B></H2><BR>
+<CENTER>
+<TABLE BORDER>
+<TR>
+<TD COLSPAN = 1>
+<TD rowspan = 1>
+<TR><TD>
+<XMP>
+ procedure insert( key : typekey; var r : dataarray );
+ var i : integer;
+ temp : typekey;
+
+ begin
+ if n>=m then Error {*** table is full ***}
+ else begin
+ i := hashfunction( key ) ;
+ while (not empty(r[i])) and (not deleted(r[i]))
+ and (r[i].k<>key) do begin
+ if r[i].k > key then begin
+ {*** Exchange key and continue ***}
+ temp := key; key := r[i].k; r[i].k := temp
+ end;
+ i := (i+increment(key)) mod m
+ end;
+ if empty(r[i]) or deleted(r[i]) then begin
+ {*** do insertion ***}
+ r[i].k := key;
+ n := n+1
+ end
+ else Error {*** key already in table ***}
+ end
+ end;
+</XMP></TD></TR></TABLE>
+<BR>
+<H3><A HREF="ftp://sunsite.dcc.uchile.cl/pub/users/rbaeza/handbook/algs/3/337.ins.p"><IMG SRC="../../images/ftp.xbm" hspace=10>Pascal</A> source (337.ins.p) </H3></CENTER>
+<HR><H4>
+<IMG SRC="../../images/aw3.gif" align=left><H5><BR>
+© <A HREF="http://aw.com">Addison-Wesley </A>Publishing Co. Inc.
+</H5></H4><HR>
+</BODY>
--- /dev/null
+<HEAD>
+<TITLE>Quadratic hashing: insertion
+</TITLE>
+<BODY>
+<H2>
+<H3>
+<A HREF="../../images/handbook.gif"><IMG SRC="../../images/handbook2.gif" align=left></A>
+<A HREF="../../hbook.html">
+<IMG SRC="../../images/home_g.gif" hspace = 15 vspace = 4></A><BR>
+<A HREF="../../expand.html">
+<IMG SRC="../../images/contents_g.gif" hspace = 15 vspace = 4></A><BR>
+<A HREF="../../search_a.html">
+<IMG SRC="../../images/chapter_g.gif" hspace = 15 vspace = 4></A><BR>
+<A HREF="311.ins.c.html"><IMG SRC="../../images/prevalg_g.gif" hspace = 15 vspace = 4></A><BR>
+<A HREF="311c.srch.c.html">
+<IMG SRC="../../images/nextalg_g.gif" hspace = 15 vspace = 4></A><BR>
+<BR></H2>
+<HR>
+<H2><B>Quadratic hashing: insertion
+</B></H2><BR>
+<CENTER>
+<TABLE BORDER>
+<TR>
+<TD COLSPAN = 1>
+<TD rowspan = 1>
+<TR><TD>
+<XMP>
+ procedure insert( key : typekey; var r : dataarray );
+ var i, inc : integer;
+
+ begin
+ i := hashfunction( key );
+ inc := 0;
+ while (inc<m) and (not empty(r[i])) and
+ (not deleted(r[i])) and (r[i].k<>key) do begin
+ i := (i+inc+1) mod m;
+ inc := inc + 2;
+ end;
+ if empty(r[i]) or deleted(r[i]) then
+ begin
+ {*** insert here ***}
+ r[i].k := key;
+ n := n+1
+ end
+ else Error {*** table full, or key already in table ***};
+ end;
+</XMP></TD></TR></TABLE>
+<BR>
+<H3><A HREF="ftp://sunsite.dcc.uchile.cl/pub/users/rbaeza/handbook/algs/3/336.ins.p"><IMG SRC="../../images/ftp.xbm" hspace=10>Pascal</A> source (336.ins.p) </H3></CENTER>
+<HR><H4>
+<IMG SRC="../../images/aw3.gif" align=left><H5><BR>
+© <A HREF="http://aw.com">Addison-Wesley </A>Publishing Co. Inc.
+</H5></H4><HR>
+</BODY>
--- /dev/null
+<HEAD>
+<TITLE>Shellsort
+</TITLE>
+<BODY>
+<H2>
+<H3>
+<A HREF="../../images/handbook.gif"><IMG SRC="../../images/handbook2.gif" align=left></A>
+<A HREF="../../hbook.html">
+<IMG SRC="../../images/home_g.gif" hspace = 15 vspace = 4 ALT = "[Home]"></A><BR>
+<A HREF="../../sort_a.html">
+<IMG SRC="../../images/chapter_g.gif" hspace = 15 vspace = 4 ALT = "[Chapter]"></A><BR>
+<A HREF="../../expand.html">
+<IMG SRC="../../images/contents_g.gif" hspace = 15 vspace = 4 ALT = "[Contents]"></A><BR>
+<A HREF="414.sort.c.html">
+</A>
+<A HREF="414.sort.c.html">
+<IMG SRC="../../images/prevalg_g.gif" hspace = 15 vspace = 4 ALT = "[Previous Algorithm]"></A><BR>
+<A HREF="414b.sort.c.html">
+<IMG SRC="../../images/nextalg_g.gif" hspace = 15 vspace = 4 ALT = "[Next Algorithm]"></A><BR>
+<BR></H2>
+<HR>
+<H2><B>Shellsort
+</B></H2><BR>
+<CENTER>
+<TABLE BORDER>
+<TR>
+<TD COLSPAN = 1>
+<TD rowspan = 1>
+<TR><TD>
+<XMP>
+ procedure sort( var r : ArrayToSort; lo, up : integer );
+
+ label 999;
+ var d, i, j : integer;
+ tempr : ArrayEntry;
+ begin
+ d := up-lo+1;
+ while d>1 do begin
+ if d<5 then d := 1
+ else d := trunc( 0.45454*d );
+ {*** Do linear insertion sort in steps size d ***}
+ for i:=up-d downto lo do begin
+ tempr := r[i];
+ j := i+d;
+ while j <= up do
+ if tempr.k > r[j].k then begin
+ r[j-d] := r[j];
+ j := j+d
+ end
+ else goto 999; {*** break ***}
+ 999:
+ r[j-d] := tempr
+ end
+ end
+ end;
+</XMP></TD></TR></TABLE>
+<BR>
+<H3><A HREF="ftp://sunsite.dcc.uchile.cl/pub/users/rbaeza/handbook/algs/4/414.sort.c"><IMG SRC="../../images/ftp.xbm" hspace=10>C</A> source (414.sort.c) <A HREF="ftp://sunsite.dcc.uchile.cl/pub/users/rbaeza/handbook/algs/4/414.sort.p"><IMG SRC="../../images/ftp.xbm" hspace=10>Pascal</A> source (414.sort.p)
+</H3></CENTER>
+<HR><H4>
+<IMG SRC="../../images/aw3.gif" align=left><H5><BR>
+© <A HREF="http://aw.com">Addison-Wesley </A>Publishing Co. Inc.
+</H5></H4><HR>
+</BODY>
--- /dev/null
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">\r
+<!-- saved from url=(0053)http://www.ibilce.unesp.br/courseware/datas/data5.htm -->\r
+<HTML><HEAD><TITLE>Stacks, Queues, Lists and Hash Tables</TITLE>\r
+<META content="Tue, 25 Apr 1995 09:30:00 -0700" http-equiv=Expires>\r
+<META content="text/html; charset=iso-8859-1" http-equiv=Content-Type>\r
+<META content="MSHTML 5.00.2314.1000" name=GENERATOR></HEAD>\r
+<BODY bgColor=#ffffff>\r
+<P align=center><!--webbot bot="ImageMap" startspan\r
+rectangle=" (284,4) (328, 20) onlinet.htm"\r
+rectangle=" (231,4) (277, 19) cstart.htm"\r
+rectangle=" (158,4) (223, 19) mailto:brian.brown@cit.ac.nz"\r
+rectangle=" (55,4) (153, 20) ../default.htm##_top"\r
+rectangle=" (6,3) (51, 19) default.htm##_top"\r
+src="images/dsmenu.gif" alt="Menu bar" border="0" width="334"\r
+height="22" ismap --><MAP name=FrontPageMap0><AREA coords=284,4,328,20 \r
+ href="http://www.ibilce.unesp.br/courseware/datas/onlinet.htm" \r
+ shape=RECT><AREA coords=231,4,277,19 \r
+ href="http://www.ibilce.unesp.br/courseware/datas/cstart.htm" shape=RECT><AREA \r
+ coords=158,4,223,19 href="mailto:brian.brown@cit.ac.nz" shape=RECT><AREA \r
+ coords=55,4,153,20 href="http://www.ibilce.unesp.br/courseware/default.htm" \r
+ shape=RECT target=_top><AREA coords=6,3,51,19 \r
+ href="http://www.ibilce.unesp.br/courseware/datas/default.htm" shape=RECT \r
+ target=_top></MAP><IMG alt="Menu bar" border=0 height=22 isMap \r
+src="Stacks, Queues, Lists and Hash Tables_archivos/dsmenu.gif" \r
+useMap=#FrontPageMap0 width=334><!--webbot bot="ImageMap"\r
+i-checksum="35063" endspan --><BR><FONT color=#0000ff size=5>Data Structures \r
+And Number Systems</FONT><FONT color=#000000 size=4><BR></FONT><FONT \r
+color=#000000 size=3><B>© Copyright Brian Brown, 1984-1999. All rights \r
+reserved.</B></FONT></P>\r
+<P align=center>Part 5<BR><A \r
+href="http://www.ibilce.unesp.br/courseware/datas/default.htm"><IMG alt=index \r
+border=0 height=20 src="Stacks, Queues, Lists and Hash Tables_archivos/menu.gif" \r
+width=60></A> <A \r
+href="http://www.ibilce.unesp.br/courseware/datas/data4.htm"><IMG alt=prev \r
+border=0 height=20 \r
+src="Stacks, Queues, Lists and Hash Tables_archivos/previous.gif" width=60></A> \r
+</P>\r
+<HR>\r
+\r
+<P><A name=stacks></A></P>\r
+<P><B>STACKS</B><BR>A stack is used to provide temporary storage space for \r
+values. It is defined as a data structure which operates on a <B>first in, last \r
+out</B> basis. Its uses a single pointer (index) to keep track of the \r
+information in the stack. </P>\r
+<P>The basic operations associated with a stack are, </P>\r
+<UL>\r
+ <LI>insert (push) an item onto the stack \r
+ <LI>remove (pop) an item from the stack </LI></UL>\r
+<P>The following diagram shows an empty stack of four locations. It looks just \r
+like an array, and it has an index pointer pointing to the beginning of the \r
+stack (called the <B>TOP</B> of the stack). </P><PRE><FONT face=fixedsys size=3>\r
+ +--------+\r
+ | | <------- Stack Pointer \r
+ +--------+ \r
+ | | \r
+ +--------+ \r
+ | | \r
+ +--------+\r
+ | | \r
+ +--------+\r
+\r
+</FONT></PRE>\r
+<P><B>Pushing items onto the stack</B><BR>The stack pointer is considered to be \r
+pointing to a free (empty) slot in the stack. A push operation thus involves \r
+copying data into the empty slot of the stack, then adjusting the stack pointer \r
+to point to the next free slot. </P><PRE><FONT face=fixedsys size=3>\r
+ Module Push\r
+ stack[stack_pointer] = data;\r
+ stack_pointer = stack_pointer + 1;\r
+ Module End\r
+\r
+</FONT></PRE>\r
+<P>Lets push the value 45 onto the stack. [Note: The stack could hold any data \r
+type, not necessarily decimal numbers. We have used numbers for simplicity]. The \r
+stack now looks like </P><PRE><FONT face=fixedsys size=3>\r
+ +--------+ \r
+ | 45 | \r
+ +--------+\r
+ | | <------- Stack Pointer \r
+ +--------+ \r
+ | | \r
+ +--------+ \r
+ | | \r
+ +--------+\r
+\r
+</FONT></PRE>\r
+<P>Note how the stack pointer has been adjusted to point to the next free \r
+location in the stack. [Note: for the time being we are ignoring certain \r
+problems. We will address these shortly!!!]. </P>\r
+<P><B>Removing items from the stack</B><BR>To remove an item, first decrement \r
+(subtract 1 from) the stack pointer, then extract the data from that position in \r
+the stack. </P><PRE><FONT face=fixedsys size=3>\r
+ Module Remove\r
+ stack_pointer = stack_pointer - 1;\r
+ data = stack[stack_pointer];\r
+ Module End\r
+\r
+</FONT></PRE>\r
+<P><B>Time now to address the problems of the above implementation</B><BR>There \r
+are a number of problems associated with the above routines for pushing and \r
+removing items. </P>\r
+<UL>\r
+ <LI>the push module does not check to see if the stack is full \r
+ <LI>the remove module does not check to see if the stack is empty </LI></UL>\r
+<P>There are a number of solutions to this problem. We shall present a \r
+simplified solution. We do not argue that it is the best, just that it is one of \r
+a possible number of solutions. </P><PRE><FONT face=fixedsys size=3>\r
+ Comment: Assume that the array elements begin at 1\r
+ Comment: Assume that the maximum elements of the stack is MAX\r
+\r
+ Var: stack[MAX] : Integer;\r
+\r
+ Module Initialize\r
+ stack_pointer = 1;\r
+ Module End\r
+\r
+ Module Push\r
+ if stack_pointer >= MAX then\r
+ return error\r
+ else begin\r
+ stack[stack_pointer] = data;\r
+ stack_pointer = stack_pointer + 1;\r
+ end\r
+ Module End\r
+\r
+ Module Remove\r
+ if stack_pointer <= 1 then\r
+ return error\r
+ else begin\r
+ stack_pointer = stack_pointer - 1;\r
+ data = stack[stack_pointer];\r
+ end\r
+ Module End\r
+\r
+</FONT></PRE>\r
+<HR>\r
+\r
+<P><A name=queues></A></P>\r
+<P><B>QUEUES</B><BR>Everybody has experience with queues as they are common \r
+place. Queues occur in cafeterias, petrol stations, shopping centres, anyplace \r
+where many people (customers) line up for few resources (cashier's, salespeople, \r
+petrol pumps etc). </P>\r
+<P>The purpose of a queue is to provide some form of buffering. Typical uses of \r
+queues in computer systems are, </P>\r
+<UL>\r
+ <LI>process management \r
+ <LI>buffer between the fast computer and a slow printer </LI></UL>\r
+<P>A queue is defined as a data structure which holds a series of items to be \r
+processed on a <B>first in first out</B> basis (though some queues can be sorted \r
+in priority). The operations associated with a queue are, </P>\r
+<UL>\r
+ <LI>initialize the queue \r
+ <LI>insert an item in the queue \r
+ <LI>remove an item from the queue \r
+ <LI>count the number of empty slots in the queue \r
+ <LI>count the number of items in the queue </LI></UL>\r
+<P>The following diagram shows an empty queue. It is identified as a series of \r
+ten locations, and two pointers named <B>front</B> and <B>rear</B>. These two \r
+pointers keep track of where the front and rear of the queue is. </P><PRE><FONT face=fixedsys size=3>\r
+ 1 2 3 4 5 6 7 8 9 10 \r
+ +---+---+---+---+---+---+---+---+---+---+ \r
+ | | | | | | | | | | | \r
+ +---+---+---+---+---+---+---+---+---+---+ \r
+ +---+ \r
+ | 1 | Front \r
+ +---+ \r
+ +---+ \r
+ | 10| Rear \r
+ +---+ \r
+ \r
+</FONT></PRE>\r
+<P>The front pointer is used to delete items, and the rear pointer insert items. \r
+Inserting two items called A and B will rearrange the queue to look like, </P><PRE><FONT face=fixedsys size=3> \r
+ 1 2 3 4 5 6 7 8 9 10 \r
+ +---+---+---+---+---+---+---+---+---+---+ \r
+ | A | B | | | | | | | | | \r
+ +---+---+---+---+---+---+---+---+---+---+ \r
+ +---+ \r
+ | 1 | Front \r
+ +---+ \r
+ +---+ \r
+ | 2 | Rear \r
+ +---+ \r
+\r
+</FONT></PRE>\r
+<P>The pseudo-code for the various queue operations follows. </P><PRE><FONT face=fixedsys size=3> \r
+ module initialize \r
+ count = 0 \r
+ head = 1 \r
+ rear = size of queue \r
+ end module initialize \r
+ \r
+ module insert \r
+ if count = size of queue \r
+ queue is full and do not insert \r
+ else \r
+ begin \r
+ increment count \r
+ increment rear \r
+ if rear > size of queue \r
+ rear = 1 \r
+ endif \r
+ insert data at queue[rear] \r
+ endif \r
+ end module insert \r
+ \r
+ module remove \r
+ if count = 0 \r
+ queue is empty and do not remove \r
+ else \r
+ begin \r
+ data = queue[front] \r
+ decrement count \r
+ increment front \r
+ if front > size of queue \r
+ front = 1 \r
+ endif \r
+ endif \r
+ end module remove \r
+\r
+ module count \r
+ return count \r
+ end module count \r
+ \r
+ module free_space \r
+ return queue.size - count \r
+ end module free_space \r
+ \r
+ \r
+</FONT></PRE>\r
+<P>The implementation of this is left to the student as a programming exercise. \r
+</P>\r
+<HR>\r
+\r
+<P><A name=linkedlists></A></P>\r
+<P><B>LINKED LISTS</B><BR>Data structures can be arranged in memory in a variety \r
+of different ways. Each method has advantages and disadvantages. Arrays for \r
+example seem easy to use, where each element is stored sequentially in memory. \r
+</P>\r
+<P>This type of approach is not efficient in larger computer systems, where a \r
+number of users share main memory. In such circumstances, there may not be \r
+enough contiguous main memory left to hold a sequentially stored data structure \r
+like an array (but there could be enough if all the small free blocks were moved \r
+into one large block). </P>\r
+<P>One way to overcome this is to link all elements of data together. Data is \r
+arranged into records, and a special item is added to each record called a \r
+pointer (a link field), which contains a link to the next record etc. Renaming \r
+each record as a node and we have a complex data structure called a<B> linked \r
+list</B>. </P>\r
+<P>A linked list is a series of nodes connected together via pointers. \r
+Pictorially, it looks like, </P><PRE><FONT face=fixedsys size=3> \r
+ Node 1 +---+ Node 2 +---+ Node n \r
+ +--------+--+ | +--------+--+ | +--------+--+ \r
+ | | ------+ | | ------+ | | | \r
+ +--------+--+ +--------+--+ +--------+--+ \r
+ Data Link Data Lnk Data Lnk \r
+ \r
+</FONT></PRE>\r
+<P>In Pascal, a node definition looks like, </P><PRE><FONT face=fixedsys size=3> \r
+ type ptr = ^node; \r
+ node = record \r
+ data : string[20]; \r
+ next : ptr; \r
+ end; \r
+ \r
+</FONT></PRE>\r
+<P>The following Pascal program declares three nodes, inserts data into each of \r
+them, then using a pointer, cycles through the chain from node to node printing \r
+out the contents of each node. The value 0 is always stored in the last node of \r
+a chain, to indicate the end of the list. </P><PRE><FONT face=fixedsys size=3> \r
+ program linked_list; \r
+ type ptr = ^node; \r
+ node = record \r
+ data : string[20]; \r
+ next : ptr; \r
+ end; \r
+ var \r
+ node1, node2, node3 : node; \r
+ nodeptr : ptr; \r
+ begin \r
+ node1.data := 'Welcome '; \r
+ node1.next := @node2; \r
+ node2.data := 'to '; \r
+ node2.next := @node3; \r
+ node3.data := 'Linked Lists.'; \r
+ node3.next := nil; \r
+ nodeptr := @node1; \r
+ while nodeptr <> nil do \r
+ begin \r
+ write( nodeptr^.data ); \r
+ nodeptr := nodeptr^.next; \r
+ end; \r
+ writeln; \r
+ end. \r
+ \r
+</FONT></PRE>\r
+<P>Linked lists are used in a wide variety of applications. </P>\r
+<UL>\r
+ <LI>directory structures \r
+ <LI>operating systems for process management \r
+ <LI>data management in data base systems. </LI></UL>\r
+<P>An advantage of storing data using a linked list is that the key sequence can \r
+be altered by changing the pointers, not by moving data nodes. This means \r
+sorting data is quick, but searching is slower as you must follow the chain from \r
+node to node. </P>\r
+<HR>\r
+\r
+<P><A name=hashing></A></P>\r
+<P><B>HASHING</B><BR>Hashing is a technique used to improve data access times. \r
+Rather than sorting the data according to a key, it computes the location of the \r
+data from the key. In simple terms, it computes an <B>index value from the \r
+key</B> of the desired record. At that index value, the record is \r
+stored/retrieved. </P>\r
+<P>If we had an array of 1000 elements, we would expect our hash function (the \r
+method used to calculate the index value) to evenly distribute the keys over \r
+this range. In practice this is difficult to achieve. It is possible that two \r
+different search keys might generate the same hash value (ie, index), and we \r
+call this a <B>collision</B>. </P>\r
+<P>The size of the table (array) is generally a prime number, as this has the \r
+least probability of creating collisions. </P>\r
+<P>The following code segment defines an array of records in Pascal which will \r
+be used to demonstrate hashing. </P><PRE><FONT face=fixedsys size=3> \r
+ const size = 511; \r
+ type data = record \r
+ name : string[20]; \r
+ age : integer; \r
+ end; \r
+ hashtable = array[1..size] of data; \r
+ \r
+</FONT></PRE>\r
+<P>Next, lets initialize the table with zero's, so this makes it easy to see if \r
+information is already stored at a particular element (important when inserting \r
+data later). </P><PRE><FONT face=fixedsys size=3> \r
+ procedure initialize ( var Table : hashtable ); \r
+ var i : integer; \r
+ begin \r
+ for i := 1 to size do \r
+ begin \r
+ Table[i].name := ' '; \r
+ Table[i].age := 0; \r
+ end; \r
+ end; \r
+ \r
+</FONT></PRE>\r
+<P>The procedure insert will take the hash value and the data and insert it into \r
+the table. If the position is already occupied (ie, a collision occurs) the \r
+table will be searched from that point onwards till an empty slot occurs. </P><PRE><FONT face=fixedsys size=3> \r
+ procedure insert ( Position : integer; Element : data ; var Table : hashtable ); \r
+ begin \r
+ while Table[Position].name[1] <> ' ' do \r
+ Position := (Position + 1) mod size; \r
+ Table[Position] := Element; \r
+ end; \r
+ \r
+</FONT></PRE>\r
+<P>The procedure hash will generate a hash value from a given data record. In \r
+deciding this, it must generate a value between 1 and 511. Obviously, we cannot \r
+use the age field of the record, this will generate too many collisions. The \r
+best method is to add up the value of all the characters in the persons name, \r
+then extract nine bits from it (2^9 = 512) to generate the index value. </P><PRE><FONT face=fixedsys size=3>\r
+ procedure hash ( var Position : integer ; Element : data ; var Table : hashtable ); \r
+ var i : integer; \r
+ begin \r
+ i := 1; \r
+ position := 0; \r
+ while i < 20 do \r
+ position := position + ord(Element.name[i]); \r
+ position := position mod 511; \r
+ end; \r
+ \r
+</FONT></PRE>\r
+<P>The remaining procedures to search and delete are left as a programming \r
+exercise for the student. <BR></P>\r
+<HR>\r
+\r
+<P><B>INDEXED SEQUENTIAL</B><BR>This method seeks to make a direct access file \r
+appear like a sequence file. The sequencing is achieved via an index table, \r
+which holds the keys of the records and their position within the file. </P>\r
+<P>A program reads the index sequentially, and when it locates the key it \r
+desires, it reads the record from the indicated position. </P>\r
+<P>The advantages of this method are, </P>\r
+<UL>\r
+ <LI>the records need not be in key sequence \r
+ <LI>the records may be processed sequentially or directly </LI></UL>\r
+<HR>\r
+\r
+<P><B>FILE MERGING</B><BR>This is the process of merging two or more input files \r
+into a single output file (which are normally all sequential in nature). The \r
+files to be merged are first sorted using the same key sequence, which is \r
+preserved in the output file. </P>\r
+<P>A pseudo-code example for a 2-way merge is shown below. </P><PRE><FONT face=fixedsys size=3> \r
+ program two_way merge \r
+ begin \r
+ read 1st record of infile1, name as rec1 \r
+ read 1st record of infile2, name as rec2 \r
+ while rec1 or rec2 is not an end-of-record \r
+ begin \r
+ if rec1.key < rec2.key \r
+ begin \r
+ write rec1 to outfile \r
+ read new rec1 from infile1 \r
+ end \r
+ else \r
+ begin \r
+ write rec2 to outfile \r
+ read new rec2 from infile2 \r
+ end \r
+ endif \r
+ endwhile \r
+ write end-of-record to outfile \r
+ end program two_way merge \r
+\r
+</FONT></PRE>\r
+<HR>\r
+\r
+<P align=center><A \r
+href="http://www.ibilce.unesp.br/courseware/datas/default.htm"><IMG alt=index \r
+border=0 height=20 src="Stacks, Queues, Lists and Hash Tables_archivos/menu.gif" \r
+width=60></A> <A \r
+href="http://www.ibilce.unesp.br/courseware/datas/data4.htm"><IMG alt=prev \r
+border=0 height=20 \r
+src="Stacks, Queues, Lists and Hash Tables_archivos/previous.gif" width=60></A> \r
+</P>\r
+<P align=center><A \r
+href="http://www.ibilce.unesp.br/courseware/datas/default.htm" target=_top><FONT \r
+size=2>Home</FONT></A><FONT size=2> | </FONT><A \r
+href="http://www.ibilce.unesp.br/courseware/default.htm" target=_top><FONT \r
+size=2>Other Courses</FONT></A><FONT size=2> | </FONT><A \r
+href="mailto:brian.brown@cit.ac.nz"><FONT size=2>Feedback</FONT></A><FONT \r
+size=2> | </FONT><A \r
+href="http://www.ibilce.unesp.br/courseware/datas/cstart.htm"><FONT \r
+size=2>Notes</FONT></A><FONT size=2> | </FONT><A \r
+href="http://www.ibilce.unesp.br/courseware/datas/onlinet.htm"><FONT \r
+size=2>Tests</FONT></A><FONT size=2> </FONT></P>\r
+<P align=center>© Copyright Brian Brown, 1984-1999. All rights \r
+reserved.<BR></P></BODY></HTML>\r
--- /dev/null
+program Ejercicio1;\r
+\r
+const\r
+ MAX = 10;\r
+\r
+type\r
+ Vector = array [1..MAX] of integer;\r
+\r
+\r
+ (*****************************************************)\r
+\r
+ procedure visualiza(var v: Vector; titulo: String);\r
+\r
+ var\r
+ i: integer;\r
+\r
+ begin\r
+ writeln(titulo);\r
+ writeln;\r
+ for i := 1 to MAX do\r
+ writeln('Numero ', i, ': ', v[i]);\r
+ writeln;\r
+ end; { visualiza }\r
+\r
+ (*****************************************************)\r
+\r
+ procedure leerDatos(var v: Vector);\r
+\r
+ var\r
+ f: Text;\r
+ i, k, code: integer;\r
+ s: String;\r
+\r
+ begin\r
+ assign(f, 'datos.txt');\r
+ reset(f);\r
+ i := 1;\r
+ while (not eof(f)) and (i <= MAX) do begin\r
+ readln(f, s);\r
+ val(s, k, code);\r
+ if code <> 0 then begin\r
+ Writeln('Error en la posici¢n: ', Code);\r
+ exit;\r
+ end;\r
+ v[i] := k;\r
+ i := i + 1;\r
+ end;\r
+ close(f);\r
+ visualiza(v, 'Datos Originales');\r
+ end; { leerDatos }\r
+\r
+ (*****************************************************)\r
+\r
+ procedure ordenarDecreciente(var v: Vector);\r
+\r
+ var\r
+ i, j, aux: integer;\r
+\r
+ begin\r
+ for i := 1 to MAX do\r
+ for j := i + 1 to MAX do\r
+ if v[i] < v[j] then begin\r
+ aux := v[i];\r
+ v[i] := v[j];\r
+ v[j] := aux;\r
+ end;\r
+ end; { ordenarDecreciente }\r
+\r
+ (*****************************************************)\r
+\r
+var\r
+ v: Vector;\r
+\r
+begin\r
+ leerDatos(v);\r
+ ordenarDecreciente(v);\r
+ visualiza(v, 'Datos Ordenados');\r
+end.
\ No newline at end of file
--- /dev/null
+program Ejercicio2;\r
+\r
+const\r
+ MAX_FILAS = 7;\r
+ MAX_COLUMNAS = 6;\r
+\r
+type\r
+ Datos = record\r
+ i: integer;\r
+ j: integer;\r
+ end;\r
+ Matriz = array [1..MAX_FILAS, 1..MAX_COLUMNAS] of integer;\r
+ Vector = array [1..MAX_FILAS+MAX_COLUMNAS] of Datos;\r
+\r
+\r
+ (*****************************************************)\r
+\r
+ procedure visualiza(var m: Matriz; titulo: String);\r
+\r
+ var\r
+ i, j: integer;\r
+\r
+ begin\r
+ writeln(titulo);\r
+ writeln;\r
+ for i := 1 to MAX_FILAS do begin\r
+ for j := 1 to MAX_COLUMNAS do\r
+ write(' ', m[i,j]: 8);\r
+ writeln;\r
+ end;\r
+ writeln;\r
+ end; { visualiza }\r
+\r
+ (*****************************************************)\r
+\r
+ procedure leerDatos(var m: Matriz);\r
+\r
+ var\r
+ f: Text;\r
+ i, j, k, code: integer;\r
+ s: String;\r
+\r
+ begin\r
+ assign(f, 'datos.txt');\r
+ reset(f);\r
+ i := 1;\r
+ j := 1;\r
+ while (not eof(f)) and (i <= MAX_FILAS) and (j <= MAX_COLUMNAS) do begin\r
+ readln(f, s);\r
+ val(s, k, code);\r
+ if code <> 0 then begin\r
+ Writeln('Error en la posici¢n: ', Code);\r
+ exit;\r
+ end;\r
+ m[i,j] := k;\r
+ if j < MAX_COLUMNAS then\r
+ j := j + 1\r
+ else begin\r
+ i := i + 1;\r
+ j := 1;\r
+ end;\r
+ end;\r
+ close(f);\r
+ end; { leerDatos }\r
+\r
+ (*****************************************************)\r
+\r
+ function buscarMayor(var m: Matriz): integer;\r
+\r
+ var\r
+ i, j, max: integer;\r
+\r
+ begin\r
+ max := - MAXINT;\r
+ for i := 1 to MAX_FILAS do\r
+ for j := 1 to MAX_COLUMNAS do\r
+ if m[i,j] > max then\r
+ max := m[i,j];\r
+ buscarMayor := max;\r
+ end; { buscarMayor }\r
+\r
+ (*****************************************************)\r
+\r
+ procedure buscarIndices(var m: Matriz; max: integer; var indices: Vector);\r
+\r
+ var\r
+ i, j, k: integer;\r
+\r
+ begin\r
+ k := 1;\r
+ for i := 1 to MAX_FILAS do\r
+ for j := 1 to MAX_COLUMNAS do\r
+ if m[i,j] = max then begin\r
+ indices[k].i := i;\r
+ indices[k].j := j;\r
+ k := k + 1;\r
+ end;\r
+ end; { buscarIndices }\r
+\r
+ (*****************************************************)\r
+\r
+var\r
+ m: Matriz;\r
+ i, max: integer;\r
+ indices: Vector;\r
+\r
+begin\r
+ leerDatos(m);\r
+ visualiza(m, 'Datos');\r
+ writeln;\r
+ max := buscarMayor(m);\r
+ writeln(' Valor Maximo: ', max);\r
+ writeln(' Se encuantra en los indices: ');\r
+ buscarIndices(m, max, indices);\r
+ for i := 1 to MAX_FILAS + MAX_COLUMNAS do\r
+ if (indices[i].i > 0) and (indices[i].j > 0) then\r
+ writeln(' | ', indices[i].i, ' | ', indices[i].j, ' |')\r
+ else\r
+ break;\r
+end.
\ No newline at end of file
--- /dev/null
+program Ejercicio3;\r
+\r
+const\r
+ MAX = 10;\r
+\r
+type\r
+ Vector = array [1..MAX] of integer;\r
+\r
+\r
+ (*****************************************************)\r
+\r
+ procedure leerDatos(var v: Vector);\r
+\r
+ var\r
+ i: integer;\r
+\r
+ begin\r
+ for i := 1 to MAX do begin\r
+ write('Numero: ');\r
+ readln(v[i]);\r
+ end;\r
+ end; { leerDatos }\r
+\r
+ (*****************************************************)\r
+\r
+ procedure ordenarDecreciente(var v: Vector);\r
+\r
+ var\r
+ i, j, aux: integer;\r
+\r
+ begin\r
+ for i := 1 to MAX do\r
+ for j := i + 1 to MAX do\r
+ if v[i] < v[j] then begin\r
+ aux := v[i];\r
+ v[i] := v[j];\r
+ v[j] := aux;\r
+ end;\r
+ end; { ordenarDecreciente }\r
+\r
+ (*****************************************************)\r
+\r
+ function buscaBinaria(var v: Vector; num, ini, fin: integer): integer;\r
+\r
+ var\r
+ medio: integer;\r
+\r
+ begin\r
+ if (v[ini] < num) or (v[fin] > num) then\r
+ buscaBinaria := 0\r
+ else begin\r
+ medio := ini + ((fin - ini) div 2);\r
+ if num = v[medio] then\r
+ buscaBinaria := medio\r
+ else\r
+ if num < v[medio] then\r
+ buscaBinaria := buscaBinaria(v, num, medio + 1, fin)\r
+ else\r
+ buscaBinaria := buscaBinaria(v, num, ini, medio - 1);\r
+ end;\r
+ end;\r
+\r
+ (*****************************************************)\r
+\r
+var\r
+ v: Vector;\r
+ indice: integer;\r
+\r
+begin\r
+ leerDatos(v);\r
+ ordenarDecreciente(v);\r
+ indice := buscaBinaria(v, 333, 1, MAX);\r
+ if indice = 0 then\r
+ writeln('NO SE ENCONTRO EL NUMERO ''333'' ENTRE LOS INGRESADOS')\r
+ else\r
+ writeln('El numero ''333'' se encuentra en la posicion ', indice, '.');\r
+end.
\ No newline at end of file
--- /dev/null
+<html><head><title>orden.pas</title></head><body bgcolor="#FFFFFF" text="#000000"><pre>
+ <font color="#444444">(**************************************************)</font>\r
+ <font color="#444444">(* *)</font>\r
+ <font color="#444444">(* ALGORITMOS DE ORDENAMIENTO *)</font>\r
+ <font color="#444444">(* ========== == ============ *)</font>\r
+ <font color="#444444">(* *)</font>\r
+ <font color="#444444">(**************************************************)</font>\r
+\r
+<strong>program</strong> <font color="#993333">Ordenamientos</font><font color="#4444FF">;</font>\r
+\r
+<strong>const</strong>\r
+ <font color="#993333">MAX</font> <font color="#4444FF">=</font> <font color="#FF0000">15</font><font color="#4444FF">;</font>\r
+\r
+<strong>type</strong>\r
+ <font color="#993333">Dato</font> <font color="#4444FF">=</font> <font color="#993333">Integer</font><font color="#4444FF">;</font>\r
+ <font color="#993333">Vector</font> <font color="#4444FF">=</font> <strong>array</strong> <font color="#4444FF">[</font><font color="#FF0000">1..</font><font color="#993333">MAX</font><font color="#4444FF">]</font> <strong>of</strong> <font color="#993333">Dato</font><font color="#4444FF">;</font>\r
+\r
+\r
+<font color="#444444">(****************************************************\r
+ *\r
+ * BUBBLE SORT.\r
+ *\r
+ ****************************************************)</font>\r
+\r
+ <strong>procedure</strong> <font color="#993333">bubbleSort</font><font color="#4444FF">(</font><strong>var</strong> <font color="#993333">v</font><font color="#4444FF">:</font> <font color="#993333">Vector</font><font color="#4444FF">;</font> <font color="#444444">{ Vector a ordenar }</font>\r
+ <font color="#993333">min</font>, <font color="#444444">{ Valor de donde se comienza a ordenar }</font>\r
+ <font color="#993333">max</font><font color="#4444FF">:</font> <font color="#993333">Integer</font><font color="#4444FF">)</font><font color="#4444FF">;</font> <font color="#444444">{ Valor en donde se termina de ordenar }</font>\r
+\r
+ <strong>var</strong>\r
+ <font color="#993333">i</font>, <font color="#993333">j</font>, <font color="#993333">aux</font><font color="#4444FF">:</font> <font color="#993333">integer</font><font color="#4444FF">;</font>\r
+\r
+ <strong>begin</strong>\r
+ <strong>if</strong> <font color="#993333">min</font> <font color="#4444FF"><</font> <font color="#993333">max</font> <strong>then</strong>\r
+ <strong>for</strong> <font color="#993333">i</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">max</font> <font color="#4444FF">-</font> <font color="#FF0000">1</font> <strong>downto</strong> <font color="#993333">min</font> <strong>do</strong>\r
+ <strong>for</strong> <font color="#993333">j</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">min</font> <strong>to</strong> <font color="#993333">i</font> <strong>do</strong>\r
+ <strong>if</strong> <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">j</font><font color="#4444FF">]</font> <font color="#4444FF">></font> <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">j</font><font color="#4444FF">+</font><font color="#FF0000">1</font><font color="#4444FF">]</font> <strong>then</strong> <strong>begin</strong>\r
+ <font color="#993333">aux</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">j</font><font color="#4444FF">]</font><font color="#4444FF">;</font>\r
+ <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">j</font><font color="#4444FF">]</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">j</font><font color="#4444FF">+</font><font color="#FF0000">1</font><font color="#4444FF">]</font><font color="#4444FF">;</font>\r
+ <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">j</font><font color="#4444FF">+</font><font color="#FF0000">1</font><font color="#4444FF">]</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">aux</font><font color="#4444FF">;</font>\r
+ <strong>end</strong><font color="#4444FF">;</font>\r
+ <strong>end</strong><font color="#4444FF">;</font> <font color="#444444">{ bubbleSort }</font>\r
+\r
+<font color="#444444">(****************************************************\r
+ *\r
+ * BUBBLE SORT MEJORADO.\r
+ *\r
+ ****************************************************)</font>\r
+\r
+ <strong>procedure</strong> <font color="#993333">bubbleSortMejor</font><font color="#4444FF">(</font><strong>var</strong> <font color="#993333">v</font><font color="#4444FF">:</font> <font color="#993333">Vector</font><font color="#4444FF">;</font> <font color="#444444">{ Vector a ordenar }</font>\r
+ <font color="#993333">min</font>, <font color="#444444">{ Valor de donde se comienza a ordenar }</font>\r
+ <font color="#993333">max</font><font color="#4444FF">:</font> <font color="#993333">Integer</font><font color="#4444FF">)</font><font color="#4444FF">;</font> <font color="#444444">{ Valor en donde se termina de ordenar }</font>\r
+\r
+ <strong>var</strong>\r
+ <font color="#993333">i</font>, <font color="#993333">j</font>, <font color="#993333">aux</font><font color="#4444FF">:</font> <font color="#993333">integer</font><font color="#4444FF">;</font>\r
+ <font color="#993333">huboInt</font><font color="#4444FF">:</font> <font color="#993333">Boolean</font><font color="#4444FF">;</font>\r
+\r
+ <strong>begin</strong>\r
+ <font color="#993333">huboInt</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">false</font><font color="#4444FF">;</font>\r
+ <font color="#993333">i</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">max</font> <font color="#4444FF">-</font> <font color="#FF0000">1</font><font color="#4444FF">;</font>\r
+ <strong>if</strong> <font color="#993333">min</font> <font color="#4444FF"><</font> <font color="#993333">max</font> <strong>then</strong>\r
+ <strong>repeat</strong>\r
+ <strong>for</strong> <font color="#993333">j</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">min</font> <strong>to</strong> <font color="#993333">i</font> <strong>do</strong>\r
+ <strong>if</strong> <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">j</font><font color="#4444FF">]</font> <font color="#4444FF">></font> <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">j</font><font color="#4444FF">+</font><font color="#FF0000">1</font><font color="#4444FF">]</font> <strong>then</strong> <strong>begin</strong>\r
+ <font color="#993333">aux</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">j</font><font color="#4444FF">]</font><font color="#4444FF">;</font>\r
+ <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">j</font><font color="#4444FF">]</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">j</font><font color="#4444FF">+</font><font color="#FF0000">1</font><font color="#4444FF">]</font><font color="#4444FF">;</font>\r
+ <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">j</font><font color="#4444FF">+</font><font color="#FF0000">1</font><font color="#4444FF">]</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">aux</font><font color="#4444FF">;</font>\r
+ <font color="#993333">huboInt</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">true</font><font color="#4444FF">;</font>\r
+ <strong>end</strong><font color="#4444FF">;</font>\r
+ <font color="#993333">i</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">i</font> <font color="#4444FF">-</font> <font color="#FF0000">1</font><font color="#4444FF">;</font>\r
+ <strong>until</strong> <strong>not</strong> <font color="#993333">huboInt</font><font color="#4444FF">;</font>\r
+ <strong>end</strong><font color="#4444FF">;</font> <font color="#444444">{ bubbleSortMejor }</font>\r
+\r
+<font color="#444444">(****************************************************\r
+ *\r
+ * SHAKE SORT (o Bubble Sort Bidireccional).\r
+ *\r
+ ****************************************************)</font>\r
+\r
+ <strong>procedure</strong> <font color="#993333">shakeSort</font><font color="#4444FF">(</font><strong>var</strong> <font color="#993333">v</font><font color="#4444FF">:</font> <font color="#993333">Vector</font><font color="#4444FF">;</font> <font color="#444444">{ Vector a ordenar }</font>\r
+ <font color="#993333">min</font>, <font color="#444444">{ Valor de donde se comienza a ordenar }</font>\r
+ <font color="#993333">max</font><font color="#4444FF">:</font> <font color="#993333">Integer</font><font color="#4444FF">)</font><font color="#4444FF">;</font> <font color="#444444">{ Valor en donde se termina de ordenar }</font>\r
+\r
+ <strong>var</strong>\r
+ <font color="#993333">i</font>, <font color="#993333">fin</font>, <font color="#993333">ini</font>, <font color="#993333">aux</font>, <font color="#993333">tmp</font><font color="#4444FF">:</font> <font color="#993333">integer</font><font color="#4444FF">;</font>\r
+\r
+ <strong>begin</strong>\r
+ <font color="#993333">fin</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">max</font> <font color="#4444FF">-</font> <font color="#FF0000">1</font><font color="#4444FF">;</font>\r
+ <font color="#993333">ini</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">min</font><font color="#4444FF">;</font>\r
+ <strong>if</strong> <font color="#993333">min</font> <font color="#4444FF"><</font> <font color="#993333">max</font> <strong>then</strong>\r
+ <strong>repeat</strong>\r
+ <font color="#993333">tmp</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">ini</font><font color="#4444FF">;</font>\r
+ <strong>for</strong> <font color="#993333">i</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">ini</font> <strong>to</strong> <font color="#993333">fin</font> <strong>do</strong>\r
+ <strong>if</strong> <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">i</font><font color="#4444FF">]</font> <font color="#4444FF">></font> <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">i</font><font color="#4444FF">+</font><font color="#FF0000">1</font><font color="#4444FF">]</font> <strong>then</strong> <strong>begin</strong>\r
+ <font color="#993333">aux</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">i</font><font color="#4444FF">]</font><font color="#4444FF">;</font>\r
+ <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">i</font><font color="#4444FF">]</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">i</font><font color="#4444FF">+</font><font color="#FF0000">1</font><font color="#4444FF">]</font><font color="#4444FF">;</font>\r
+ <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">i</font><font color="#4444FF">+</font><font color="#FF0000">1</font><font color="#4444FF">]</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">aux</font><font color="#4444FF">;</font>\r
+ <font color="#993333">tmp</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">i</font><font color="#4444FF">;</font>\r
+ <strong>end</strong><font color="#4444FF">;</font>\r
+ <font color="#993333">fin</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">tmp</font><font color="#4444FF">;</font>\r
+ <strong>for</strong> <font color="#993333">i</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">fin</font> <strong>downto</strong> <font color="#993333">ini</font> <strong>do</strong>\r
+ <strong>if</strong> <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">i</font><font color="#4444FF">]</font> <font color="#4444FF">></font> <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">i</font><font color="#4444FF">+</font><font color="#FF0000">1</font><font color="#4444FF">]</font> <strong>then</strong> <strong>begin</strong>\r
+ <font color="#993333">aux</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">i</font><font color="#4444FF">]</font><font color="#4444FF">;</font>\r
+ <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">i</font><font color="#4444FF">]</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">i</font><font color="#4444FF">+</font><font color="#FF0000">1</font><font color="#4444FF">]</font><font color="#4444FF">;</font>\r
+ <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">i</font><font color="#4444FF">+</font><font color="#FF0000">1</font><font color="#4444FF">]</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">aux</font><font color="#4444FF">;</font>\r
+ <font color="#993333">tmp</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">i</font><font color="#4444FF">;</font>\r
+ <strong>end</strong><font color="#4444FF">;</font>\r
+ <font color="#993333">ini</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">tmp</font><font color="#4444FF">;</font>\r
+ <strong>until</strong> <font color="#993333">ini</font> <font color="#4444FF">></font><font color="#4444FF">=</font> <font color="#993333">fin</font><font color="#4444FF">;</font>\r
+ <strong>end</strong><font color="#4444FF">;</font> <font color="#444444">{ shakeSort }</font>\r
+\r
+<font color="#444444">(****************************************************\r
+ *\r
+ * INSERTION SORT.\r
+ *\r
+ ****************************************************)</font>\r
+\r
+ <strong>procedure</strong> <font color="#993333">insertionSort</font><font color="#4444FF">(</font><strong>var</strong> <font color="#993333">v</font><font color="#4444FF">:</font> <font color="#993333">Vector</font><font color="#4444FF">;</font> <font color="#444444">{ Vector a ordenar }</font>\r
+ <font color="#993333">min</font>, <font color="#444444">{ Valor de donde se comienza a ordenar }</font>\r
+ <font color="#993333">max</font><font color="#4444FF">:</font> <font color="#993333">Integer</font><font color="#4444FF">)</font><font color="#4444FF">;</font> <font color="#444444">{ Valor en donde se termina de ordenar }</font>\r
+\r
+ <strong>var</strong>\r
+ <font color="#993333">i</font>, <font color="#993333">j</font><font color="#4444FF">:</font> <font color="#993333">integer</font><font color="#4444FF">;</font>\r
+ <font color="#993333">tmp</font><font color="#4444FF">:</font> <font color="#993333">Dato</font><font color="#4444FF">;</font>\r
+ <font color="#993333">huboInt</font><font color="#4444FF">:</font> <font color="#993333">Boolean</font><font color="#4444FF">;</font>\r
+\r
+ <strong>begin</strong>\r
+ <strong>if</strong> <font color="#993333">min</font> <font color="#4444FF"><</font> <font color="#993333">max</font> <strong>then</strong>\r
+ <strong>for</strong> <font color="#993333">i</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">min</font> <font color="#4444FF">+</font> <font color="#FF0000">1</font> <strong>to</strong> <font color="#993333">max</font> <strong>do</strong> <strong>begin</strong>\r
+ <font color="#993333">tmp</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">i</font><font color="#4444FF">]</font><font color="#4444FF">;</font>\r
+ <font color="#993333">j</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">i</font> <font color="#4444FF">-</font> <font color="#FF0000">1</font><font color="#4444FF">;</font>\r
+ <font color="#993333">huboInt</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">true</font><font color="#4444FF">;</font>\r
+ <strong>while</strong> <font color="#4444FF">(</font><font color="#993333">j</font> <font color="#4444FF">></font><font color="#4444FF">=</font> <font color="#FF0000">1</font><font color="#4444FF">)</font> <strong>and</strong> <font color="#993333">huboInt</font> <strong>do</strong>\r
+ <strong>if</strong> <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">j</font><font color="#4444FF">]</font> <font color="#4444FF">></font> <font color="#993333">tmp</font> <strong>then</strong> <strong>begin</strong>\r
+ <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">j</font><font color="#4444FF">+</font><font color="#FF0000">1</font><font color="#4444FF">]</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">j</font><font color="#4444FF">]</font><font color="#4444FF">;</font>\r
+ <font color="#993333">j</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">j</font> <font color="#4444FF">-</font> <font color="#FF0000">1</font><font color="#4444FF">;</font>\r
+ <strong>end</strong> <strong>else</strong>\r
+ <font color="#993333">huboInt</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">false</font><font color="#4444FF">;</font>\r
+ <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">j</font><font color="#4444FF">+</font><font color="#FF0000">1</font><font color="#4444FF">]</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">tmp</font><font color="#4444FF">;</font>\r
+ <strong>end</strong><font color="#4444FF">;</font>\r
+ <strong>end</strong><font color="#4444FF">;</font> <font color="#444444">{ insertionSort }</font>\r
+\r
+<font color="#444444">(****************************************************\r
+ *\r
+ * QUICK SORT.\r
+ *\r
+ ****************************************************)</font>\r
+\r
+ <strong>procedure</strong> <font color="#993333">quickSort</font><font color="#4444FF">(</font><strong>var</strong> <font color="#993333">v</font><font color="#4444FF">:</font> <font color="#993333">Vector</font><font color="#4444FF">;</font> <font color="#444444">{ Vector a ordenar }</font>\r
+ <font color="#993333">min</font>, <font color="#444444">{ Valor de donde se comienza a ordenar }</font>\r
+ <font color="#993333">max</font><font color="#4444FF">:</font> <font color="#993333">Integer</font><font color="#4444FF">)</font><font color="#4444FF">;</font> <font color="#444444">{ Valor en donde se termina de ordenar }</font>\r
+\r
+ <strong>var</strong>\r
+ <font color="#993333">ini</font>, <font color="#993333">fin</font>, <font color="#993333">medio</font><font color="#4444FF">:</font> <font color="#993333">integer</font><font color="#4444FF">;</font>\r
+ <font color="#993333">aux</font>, <font color="#993333">tmp</font><font color="#4444FF">:</font> <font color="#993333">Dato</font><font color="#4444FF">;</font>\r
+\r
+ <strong>begin</strong>\r
+ <strong>if</strong> <font color="#993333">min</font> <font color="#4444FF">></font><font color="#4444FF">=</font> <font color="#993333">max</font> <strong>then</strong>\r
+ <font color="#993333">exit</font><font color="#4444FF">;</font>\r
+ <font color="#993333">ini</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">min</font><font color="#4444FF">;</font>\r
+ <font color="#993333">fin</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">max</font><font color="#4444FF">;</font>\r
+ <font color="#993333">medio</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#4444FF">(</font><font color="#993333">min</font> <font color="#4444FF">+</font> <font color="#993333">max</font><font color="#4444FF">)</font> <strong>div</strong> <font color="#FF0000">2</font><font color="#4444FF">;</font>\r
+ <font color="#993333">tmp</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">medio</font><font color="#4444FF">]</font><font color="#4444FF">;</font>\r
+ <strong>repeat</strong>\r
+ <strong>while</strong> <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">ini</font><font color="#4444FF">]</font> <font color="#4444FF"><</font> <font color="#993333">tmp</font> <strong>do</strong>\r
+ <font color="#993333">ini</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">ini</font> <font color="#4444FF">+</font> <font color="#FF0000">1</font><font color="#4444FF">;</font>\r
+ <strong>while</strong> <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">fin</font><font color="#4444FF">]</font> <font color="#4444FF">></font> <font color="#993333">tmp</font> <strong>do</strong>\r
+ <font color="#993333">fin</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">fin</font> <font color="#4444FF">-</font> <font color="#FF0000">1</font><font color="#4444FF">;</font>\r
+ <strong>if</strong> <font color="#993333">ini</font> <font color="#4444FF"><</font><font color="#4444FF">=</font> <font color="#993333">fin</font> <strong>then</strong> <strong>begin</strong>\r
+ <strong>if</strong> <font color="#993333">ini</font> <font color="#4444FF"><</font> <font color="#993333">fin</font> <strong>then</strong> <strong>begin</strong>\r
+ <font color="#993333">aux</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">ini</font><font color="#4444FF">]</font><font color="#4444FF">;</font>\r
+ <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">ini</font><font color="#4444FF">]</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">fin</font><font color="#4444FF">]</font><font color="#4444FF">;</font>\r
+ <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">fin</font><font color="#4444FF">]</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">aux</font><font color="#4444FF">;</font>\r
+ <strong>end</strong><font color="#4444FF">;</font>\r
+ <font color="#993333">ini</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">ini</font> <font color="#4444FF">+</font> <font color="#FF0000">1</font><font color="#4444FF">;</font>\r
+ <font color="#993333">fin</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">fin</font> <font color="#4444FF">-</font> <font color="#FF0000">1</font><font color="#4444FF">;</font>\r
+ <strong>end</strong><font color="#4444FF">;</font>\r
+ <strong>until</strong> <font color="#993333">ini</font> <font color="#4444FF">></font> <font color="#993333">fin</font><font color="#4444FF">;</font>\r
+ <strong>if</strong> <font color="#993333">min</font> <font color="#4444FF"><</font> <font color="#993333">fin</font> <strong>then</strong>\r
+ <font color="#993333">quickSort</font><font color="#4444FF">(</font><font color="#993333">v</font>, <font color="#993333">min</font>, <font color="#993333">fin</font><font color="#4444FF">)</font><font color="#4444FF">;</font>\r
+ <strong>if</strong> <font color="#993333">max</font> <font color="#4444FF">></font> <font color="#993333">ini</font> <strong>then</strong>\r
+ <font color="#993333">quickSort</font><font color="#4444FF">(</font><font color="#993333">v</font>, <font color="#993333">ini</font>, <font color="#993333">max</font><font color="#4444FF">)</font><font color="#4444FF">;</font>\r
+ <strong>end</strong><font color="#4444FF">;</font> <font color="#444444">{ quickSort }</font>\r
+\r
+<font color="#444444">(****************************************************\r
+ *\r
+ * SHELL'S SORT.\r
+ *\r
+ ****************************************************)</font>\r
+\r
+ <strong>procedure</strong> <font color="#993333">Shellsort</font><font color="#4444FF">(</font> <strong>var</strong> <font color="#993333">v</font> <font color="#4444FF">:</font> <font color="#993333">Vector</font><font color="#4444FF">;</font> <font color="#444444">{ Vector a ordenar }</font>\r
+ <font color="#993333">min</font>, <font color="#444444">{ Valor de donde se comienza a ordenar }</font>\r
+ <font color="#993333">max</font> <font color="#4444FF">:</font> <font color="#993333">Integer</font> <font color="#4444FF">)</font><font color="#4444FF">;</font> <font color="#444444">{ Valor en donde se termina de ordenar }</font>\r
+\r
+ <strong>var</strong>\r
+ <font color="#993333">i</font>, <font color="#993333">j</font>, <font color="#993333">medio</font> <font color="#4444FF">:</font> <font color="#993333">Integer</font><font color="#4444FF">;</font>\r
+ <font color="#993333">tmp</font> <font color="#4444FF">:</font> <font color="#993333">Dato</font><font color="#4444FF">;</font>\r
+\r
+ <strong>begin</strong>\r
+ <font color="#993333">medio</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">max</font> <font color="#4444FF">-</font> <font color="#993333">min</font> <font color="#4444FF">+</font> <font color="#FF0000">1</font><font color="#4444FF">;</font>\r
+ <strong>while</strong> <font color="#993333">medio</font> <font color="#4444FF">></font> <font color="#FF0000">1</font> <strong>do</strong> <strong>begin</strong>\r
+ <strong>if</strong> <font color="#993333">medio</font> <font color="#4444FF"><</font> <font color="#FF0000">5</font> <strong>then</strong>\r
+ <font color="#993333">medio</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#FF0000">1</font>\r
+ <strong>else</strong>\r
+ <font color="#993333">medio</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">trunc</font><font color="#4444FF">(</font> <font color="#FF0000">0.45454</font> <font color="#4444FF">*</font> <font color="#993333">medio</font> <font color="#4444FF">)</font><font color="#4444FF">;</font>\r
+ <font color="#444444">{*** Do linear insertion sort in steps size d ***}</font>\r
+ <strong>for</strong> <font color="#993333">i</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">max</font> <font color="#4444FF">-</font> <font color="#993333">medio</font> <strong>downto</strong> <font color="#993333">min</font> <strong>do</strong> <strong>begin</strong>\r
+ <font color="#993333">tmp</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">i</font><font color="#4444FF">]</font><font color="#4444FF">;</font>\r
+ <font color="#993333">j</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">i</font> <font color="#4444FF">+</font> <font color="#993333">medio</font><font color="#4444FF">;</font>\r
+ <strong>while</strong> <font color="#993333">j</font> <font color="#4444FF"><</font><font color="#4444FF">=</font> <font color="#993333">max</font> <strong>do</strong>\r
+ <strong>if</strong> <font color="#993333">tmp</font> <font color="#4444FF">></font> <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">j</font><font color="#4444FF">]</font> <strong>then</strong> <strong>begin</strong>\r
+ <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">j</font><font color="#4444FF">-</font><font color="#993333">medio</font><font color="#4444FF">]</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">j</font><font color="#4444FF">]</font><font color="#4444FF">;</font>\r
+ <font color="#993333">j</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">j</font> <font color="#4444FF">+</font> <font color="#993333">medio</font>\r
+ <strong>end</strong> <strong>else</strong>\r
+ <font color="#993333">break</font><font color="#4444FF">;</font>\r
+ <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">j</font><font color="#4444FF">-</font><font color="#993333">medio</font><font color="#4444FF">]</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">tmp</font>\r
+ <strong>end</strong><font color="#4444FF">;</font>\r
+ <strong>end</strong><font color="#4444FF">;</font>\r
+ <strong>end</strong><font color="#4444FF">;</font> <font color="#444444">{ Shellsort }</font>\r
+\r
+\r
+<font color="#444444">(************************************************************************)</font>\r
+\r
+ <strong>procedure</strong> <font color="#993333">verVector</font><font color="#4444FF">(</font><strong>var</strong> <font color="#993333">v</font><font color="#4444FF">:</font> <font color="#993333">Vector</font><font color="#4444FF">;</font> <font color="#993333">s</font><font color="#4444FF">:</font> <font color="#993333">String</font><font color="#4444FF">)</font><font color="#4444FF">;</font>\r
+\r
+ <strong>var</strong>\r
+ <font color="#993333">i</font><font color="#4444FF">:</font> <font color="#993333">Integer</font><font color="#4444FF">;</font>\r
+\r
+ <strong>begin</strong>\r
+ <font color="#444444">(** MUESTRA VECTOR **)</font>\r
+ <font color="#993333">writeln</font><font color="#4444FF">(</font><font color="#993333">s</font><font color="#4444FF">)</font><font color="#4444FF">;</font>\r
+ <strong>for</strong> <font color="#993333">i</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#FF0000">1</font> <strong>to</strong> <font color="#993333">MAX</font> <strong>do</strong>\r
+ <font color="#993333">write</font><font color="#4444FF">(</font><font color="#008000">' | '</font>, <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">i</font><font color="#4444FF">]</font><font color="#4444FF">)</font><font color="#4444FF">;</font>\r
+ <font color="#993333">writeln</font><font color="#4444FF">(</font><font color="#008000">' | '</font><font color="#4444FF">)</font><font color="#4444FF">;</font>\r
+ <font color="#993333">writeln</font><font color="#4444FF">;</font>\r
+ <strong>end</strong><font color="#4444FF">;</font> <font color="#444444">{ verVector }</font>\r
+\r
+\r
+<font color="#444444">(************************************************************************)</font>\r
+\r
+ <strong>procedure</strong> <font color="#993333">cargarVector</font><font color="#4444FF">(</font><strong>var</strong> <font color="#993333">v</font><font color="#4444FF">:</font> <font color="#993333">Vector</font><font color="#4444FF">)</font><font color="#4444FF">;</font>\r
+\r
+ <strong>var</strong>\r
+ <font color="#993333">i</font><font color="#4444FF">:</font> <font color="#993333">Integer</font><font color="#4444FF">;</font>\r
+\r
+ <strong>begin</strong>\r
+ <font color="#444444">(** INICIALIZA VECTOR **)</font>\r
+ <strong>for</strong> <font color="#993333">i</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#FF0000">1</font> <strong>to</strong> <font color="#993333">MAX</font> <strong>do</strong>\r
+ <font color="#993333">v</font><font color="#4444FF">[</font><font color="#993333">i</font><font color="#4444FF">]</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">round</font><font color="#4444FF">(</font><font color="#993333">random</font> <font color="#4444FF">*</font> <font color="#FF0000">100</font><font color="#4444FF">)</font><font color="#4444FF">;</font>\r
+ <strong>end</strong><font color="#4444FF">;</font> <font color="#444444">{ cargarVector }</font>\r
+\r
+\r
+<font color="#444444">(************************************************************************)</font>\r
+<font color="#444444">(************************************************************************)</font>\r
+<font color="#444444">(* PROGRAMA PRINCIPAL *)</font>\r
+\r
+<strong>var</strong>\r
+ <font color="#993333">i</font><font color="#4444FF">:</font> <font color="#993333">Integer</font><font color="#4444FF">;</font>\r
+ <font color="#993333">v</font>, <font color="#993333">w</font><font color="#4444FF">:</font> <font color="#993333">Vector</font><font color="#4444FF">;</font>\r
+\r
+<strong>begin</strong>\r
+ <font color="#993333">cargarVector</font><font color="#4444FF">(</font><font color="#993333">w</font><font color="#4444FF">)</font><font color="#4444FF">;</font>\r
+ <font color="#993333">v</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">w</font><font color="#4444FF">;</font>\r
+ <font color="#993333">verVector</font><font color="#4444FF">(</font><font color="#993333">v</font>, <font color="#008000">'Desordenado:'</font><font color="#4444FF">)</font><font color="#4444FF">;</font>\r
+ <font color="#993333">bubbleSort</font><font color="#4444FF">(</font><font color="#993333">v</font>, <font color="#FF0000">1</font>, <font color="#993333">MAX</font><font color="#4444FF">)</font><font color="#4444FF">;</font>\r
+ <font color="#993333">verVector</font><font color="#4444FF">(</font><font color="#993333">v</font>, <font color="#008000">'Bubble Sort:'</font><font color="#4444FF">)</font><font color="#4444FF">;</font>\r
+ <font color="#993333">bubbleSortMejor</font><font color="#4444FF">(</font><font color="#993333">v</font>, <font color="#FF0000">1</font>, <font color="#993333">MAX</font><font color="#4444FF">)</font><font color="#4444FF">;</font>\r
+ <font color="#993333">verVector</font><font color="#4444FF">(</font><font color="#993333">v</font>, <font color="#008000">'Bubble Sort Mejorado:'</font><font color="#4444FF">)</font><font color="#4444FF">;</font>\r
+ <font color="#993333">v</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">w</font><font color="#4444FF">;</font>\r
+ <font color="#993333">shakeSort</font><font color="#4444FF">(</font><font color="#993333">v</font>, <font color="#FF0000">1</font>, <font color="#993333">MAX</font><font color="#4444FF">)</font><font color="#4444FF">;</font>\r
+ <font color="#993333">verVector</font><font color="#4444FF">(</font><font color="#993333">v</font>, <font color="#008000">'Shake Sort (Bubble Sort Bidireccional):'</font><font color="#4444FF">)</font><font color="#4444FF">;</font>\r
+ <font color="#993333">v</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">w</font><font color="#4444FF">;</font>\r
+ <font color="#993333">insertionSort</font><font color="#4444FF">(</font><font color="#993333">v</font>, <font color="#FF0000">1</font>, <font color="#993333">MAX</font><font color="#4444FF">)</font><font color="#4444FF">;</font>\r
+ <font color="#993333">verVector</font><font color="#4444FF">(</font><font color="#993333">v</font>, <font color="#008000">'Insertion Sort:'</font><font color="#4444FF">)</font><font color="#4444FF">;</font>\r
+ <font color="#993333">v</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">w</font><font color="#4444FF">;</font>\r
+ <font color="#993333">quickSort</font><font color="#4444FF">(</font><font color="#993333">v</font>, <font color="#FF0000">1</font>, <font color="#993333">MAX</font><font color="#4444FF">)</font><font color="#4444FF">;</font>\r
+ <font color="#993333">verVector</font><font color="#4444FF">(</font><font color="#993333">v</font>, <font color="#008000">'Quick Sort:'</font><font color="#4444FF">)</font><font color="#4444FF">;</font>\r
+ <font color="#993333">v</font> <font color="#4444FF">:</font><font color="#4444FF">=</font> <font color="#993333">w</font><font color="#4444FF">;</font>\r
+ <font color="#993333">shellSort</font><font color="#4444FF">(</font><font color="#993333">v</font>, <font color="#FF0000">1</font>, <font color="#993333">MAX</font><font color="#4444FF">)</font><font color="#4444FF">;</font>\r
+ <font color="#993333">verVector</font><font color="#4444FF">(</font><font color="#993333">v</font>, <font color="#008000">'Shell'</font><font color="#008000">'s Sort:'</font><font color="#4444FF">)</font><font color="#4444FF">;</font>\r
+<strong>end</strong>.\r
+\r
+</pre></body></html>
--- /dev/null
+ (**************************************************)\r
+ (* *)\r
+ (* ALGORITMOS DE ORDENAMIENTO *)\r
+ (* ========== == ============ *)\r
+ (* *)\r
+ (**************************************************)\r
+\r
+program Ordenamientos;\r
+\r
+const\r
+ MAX = 15;\r
+\r
+type\r
+ Dato = Integer;\r
+ Vector = array [1..MAX] of Dato;\r
+\r
+\r
+(****************************************************\r
+ *\r
+ * BUBBLE SORT.\r
+ *\r
+ ****************************************************)\r
+\r
+ procedure bubbleSort(var v: Vector; { Vector a ordenar }\r
+ min, { Valor de donde se comienza a ordenar }\r
+ max: Integer); { Valor en donde se termina de ordenar }\r
+\r
+ var\r
+ i, j, aux: integer;\r
+\r
+ begin\r
+ if min < max then\r
+ for i := max - 1 downto min do\r
+ for j := min to i do\r
+ if v[j] > v[j+1] then begin\r
+ aux := v[j];\r
+ v[j] := v[j+1];\r
+ v[j+1] := aux;\r
+ end;\r
+ end; { bubbleSort }\r
+\r
+(****************************************************\r
+ *\r
+ * BUBBLE SORT MEJORADO.\r
+ *\r
+ ****************************************************)\r
+\r
+ procedure bubbleSortMejor(var v: Vector; { Vector a ordenar }\r
+ min, { Valor de donde se comienza a ordenar }\r
+ max: Integer); { Valor en donde se termina de ordenar }\r
+\r
+ var\r
+ i, j, aux: integer;\r
+ huboInt: Boolean;\r
+\r
+ begin\r
+ huboInt := false;\r
+ i := max - 1;\r
+ if min < max then\r
+ repeat\r
+ for j := min to i do\r
+ if v[j] > v[j+1] then begin\r
+ aux := v[j];\r
+ v[j] := v[j+1];\r
+ v[j+1] := aux;\r
+ huboInt := true;\r
+ end;\r
+ i := i - 1;\r
+ until not huboInt;\r
+ end; { bubbleSortMejor }\r
+\r
+(****************************************************\r
+ *\r
+ * SHAKE SORT (o Bubble Sort Bidireccional).\r
+ *\r
+ ****************************************************)\r
+\r
+ procedure shakeSort(var v: Vector; { Vector a ordenar }\r
+ min, { Valor de donde se comienza a ordenar }\r
+ max: Integer); { Valor en donde se termina de ordenar }\r
+\r
+ var\r
+ i, fin, ini, aux, tmp: integer;\r
+\r
+ begin\r
+ fin := max - 1;\r
+ ini := min;\r
+ if min < max then\r
+ repeat\r
+ tmp := ini;\r
+ for i := ini to fin do\r
+ if v[i] > v[i+1] then begin\r
+ aux := v[i];\r
+ v[i] := v[i+1];\r
+ v[i+1] := aux;\r
+ tmp := i;\r
+ end;\r
+ fin := tmp;\r
+ for i := fin downto ini do\r
+ if v[i] > v[i+1] then begin\r
+ aux := v[i];\r
+ v[i] := v[i+1];\r
+ v[i+1] := aux;\r
+ tmp := i;\r
+ end;\r
+ ini := tmp;\r
+ until ini >= fin;\r
+ end; { shakeSort }\r
+\r
+(****************************************************\r
+ *\r
+ * INSERTION SORT.\r
+ *\r
+ ****************************************************)\r
+\r
+ procedure insertionSort(var v: Vector; { Vector a ordenar }\r
+ min, { Valor de donde se comienza a ordenar }\r
+ max: Integer); { Valor en donde se termina de ordenar }\r
+\r
+ var\r
+ i, j: integer;\r
+ tmp: Dato;\r
+ huboInt: Boolean;\r
+\r
+ begin\r
+ if min < max then\r
+ for i := min + 1 to max do begin\r
+ tmp := v[i];\r
+ j := i - 1;\r
+ huboInt := true;\r
+ while (j >= 1) and huboInt do\r
+ if v[j] > tmp then begin\r
+ v[j+1] := v[j];\r
+ j := j - 1;\r
+ end else\r
+ huboInt := false;\r
+ v[j+1] := tmp;\r
+ end;\r
+ end; { insertionSort }\r
+\r
+(****************************************************\r
+ *\r
+ * QUICK SORT.\r
+ *\r
+ ****************************************************)\r
+\r
+ procedure quickSort(var v: Vector; { Vector a ordenar }\r
+ min, { Valor de donde se comienza a ordenar }\r
+ max: Integer); { Valor en donde se termina de ordenar }\r
+\r
+ var\r
+ ini, fin, medio: integer;\r
+ aux, tmp: Dato;\r
+\r
+ begin\r
+ if min >= max then\r
+ exit;\r
+ ini := min;\r
+ fin := max;\r
+ medio := (min + max) div 2;\r
+ tmp := v[medio];\r
+ repeat\r
+ while v[ini] < tmp do\r
+ ini := ini + 1;\r
+ while v[fin] > tmp do\r
+ fin := fin - 1;\r
+ if ini <= fin then begin\r
+ if ini < fin then begin\r
+ aux := v[ini];\r
+ v[ini] := v[fin];\r
+ v[fin] := aux;\r
+ end;\r
+ ini := ini + 1;\r
+ fin := fin - 1;\r
+ end;\r
+ until ini > fin;\r
+ if min < fin then\r
+ quickSort(v, min, fin);\r
+ if max > ini then\r
+ quickSort(v, ini, max);\r
+ end; { quickSort }\r
+\r
+(****************************************************\r
+ *\r
+ * SHELL'S SORT.\r
+ *\r
+ ****************************************************)\r
+\r
+ procedure Shellsort( var v : Vector; { Vector a ordenar }\r
+ min, { Valor de donde se comienza a ordenar }\r
+ max : Integer ); { Valor en donde se termina de ordenar }\r
+\r
+ var\r
+ i, j, medio : Integer;\r
+ tmp : Dato;\r
+\r
+ begin\r
+ medio := max - min + 1;\r
+ while medio > 1 do begin\r
+ if medio < 5 then\r
+ medio := 1\r
+ else\r
+ medio := trunc( 0.45454 * medio );\r
+ {*** Do linear insertion sort in steps size d ***}\r
+ for i := max - medio downto min do begin\r
+ tmp := v[i];\r
+ j := i + medio;\r
+ while j <= max do\r
+ if tmp > v[j] then begin\r
+ v[j-medio] := v[j];\r
+ j := j + medio\r
+ end else\r
+ break;\r
+ v[j-medio] := tmp\r
+ end;\r
+ end;\r
+ end; { Shellsort }\r
+\r
+\r
+(************************************************************************)\r
+\r
+ procedure verVector(var v: Vector; s: String);\r
+\r
+ var\r
+ i: Integer;\r
+\r
+ begin\r
+ (** MUESTRA VECTOR **)\r
+ writeln(s);\r
+ for i := 1 to MAX do\r
+ write(' | ', v[i]);\r
+ writeln(' | ');\r
+ writeln;\r
+ end; { verVector }\r
+\r
+\r
+(************************************************************************)\r
+\r
+ procedure cargarVector(var v: Vector);\r
+\r
+ var\r
+ i: Integer;\r
+\r
+ begin\r
+ (** INICIALIZA VECTOR **)\r
+ for i := 1 to MAX do\r
+ v[i] := round(random * 100);\r
+ end; { cargarVector }\r
+\r
+\r
+(************************************************************************)\r
+(************************************************************************)\r
+(* PROGRAMA PRINCIPAL *)\r
+\r
+var\r
+ i: Integer;\r
+ v, w: Vector;\r
+\r
+begin\r
+ cargarVector(w);\r
+ v := w;\r
+ verVector(v, 'Desordenado:');\r
+ bubbleSort(v, 1, MAX);\r
+ verVector(v, 'Bubble Sort:');\r
+ bubbleSortMejor(v, 1, MAX);\r
+ verVector(v, 'Bubble Sort Mejorado:');\r
+ v := w;\r
+ shakeSort(v, 1, MAX);\r
+ verVector(v, 'Shake Sort (Bubble Sort Bidireccional):');\r
+ v := w;\r
+ insertionSort(v, 1, MAX);\r
+ verVector(v, 'Insertion Sort:');\r
+ v := w;\r
+ quickSort(v, 1, MAX);\r
+ verVector(v, 'Quick Sort:');\r
+ v := w;\r
+ shellSort(v, 1, MAX);\r
+ verVector(v, 'Shell''s Sort:');\r
+end.\r
+\r
projects / z.facultad / 75.40 / 2do-cuat / material.git / commitdiff
