Algoritmos de ordenación y visualgo.net

¿Has llevado cursos de algoritmos? Son cursos básicos que te dejan para siempre el pensamiento algorítmico necesario para aprender a programar, antes de aprender a codificar. Esta idea de programar antes de codificar se desarrolla en este artículo presentado por Rosanigo y Paur.

fapencio_escribe

Interesante. “Aprender a programar, antes que aprender a codificar”. Va para mi libro.

Uno de los temas más interesantes en estos cursos de algoritmos es el tema de algortimos de ordenación. El problema clásico de, dada una lista de números, ordenar de mayor a menor, y las diferentes estrategias (algoritmos) para alcanzar el objetivo. Revisar cada algoritmo es un poco revisar la historia de la informática.

El asunto es que con el pasar de tiempo, los nombres y las estrategias de resolución (los algoritmos) se confunden y se olvidan.

visualgo.net

Entonces, encontré esta herramienta web muy interesante: http://visualgo.net/ donde se puede, entre otras cosas, revisar el funcionamiento de cada algoritmo de una forma muy visual. El objetivo de este post es mostrar los algoritmos de ordenación más importantes, junto a su respectiva animación en visualgo.net.

Entra a la página, ve a sorting y pones en exploration mode. El otro mode es para aprender a usar la interfaz. Básicamente, en la parte derecha hay dos botones, uno para crear la lista con diferentes opciones y otro para iniciar la ordenación. En el centro de la pantalla se ven los valores que se ordenarán. Abajo, unos controles tipo video, y a la derecha una opción para ver qué se ejecuta en ese momento y qué decisión se toma, y otra donde se observa el algoritmo usado y cómo se va recorriendo. En la parte superior, los diferentes algoritmos de ordenación para irlos seleccionando e ir ejecutando y observar las diferencias en cada estrategia de ordenación (algoritmo).

visualgo_captura.png

Captura de pantalla: Ordenación en ejecución (visualgo.net)

Algoritmos de ordenación

Los algoritmos de ordenación más conocidos son los siguientes:

  • Bubble Sort
  • Select Sort
  • Insert Sort
  • Merge Sort
  • Quick Sort
  • Count Sort

Varios nombres, estrategias algo parecidas. Entonces, vayamos viendo cada uno, junto a su animación en visualgo.net. Es decir, mira el algoritmo y ve a visualgo.net y ejecutalo.

Bubble Sort

Idea: Recorrer el listado de números comparando el izquierdo con el derecho, si el izquierdo es mayor, intercambiar (swap).

De esta forma, el elemento mayor “burbujea” hacia el final del listado.

visualgo.net propone este algoritmo, el que se recorrre cuando ejecutas desde la web:

do
  swapped = false
  for i = 1 to indexOfLastUnsortedElement
    if leftElement > rightElement
      swap(leftElement, rightElement)
      swapped = true
while swapped

Select Sort

Idea: Asignar el primer elemento como el mínimo y compararlo con los demás, si se encuentra otro menor, será el nuevo mínimo y hay que intercambiarlo a la primera posición sin ordenar.

De esta forma se va seleccionando el menor valor cada vez.

visualgo.net propone este algoritmo, el que se recorrre cuando ejecutas desde la web:

repeat (numOfElements - 1) times
  set the first unsorted element as the minimum
  for each of the unsorted elements
    if element < currentMinimum
      set element as new minimum
  swap minimum with first unsorted position

Insert Sort

Idea: Recorrer el listado de números, extrayendo cada número de izquierda a derecha y buscando su lugar para insertarlo. Para esto hay que ir moviendo los elementos del listado para dar espacio el elemento insertado.

visualgo.net propone este algoritmo, el que se recorrre cuando ejecutas desde la web:

mark first element as sorted
for each unsorted element
  'extract' the element
  for i = lastSortedIndex to 0
    if currentSortedElement > extractedElement
      move sorted element to the right by 1
    else: insert extracted element

Merge Sort

Idea: Usar una estrategia de “divide y vencerás”. Partir el listado en dos más pequeños, ordenar cada sublistado y luego mezclar (merge) ambos listados.

visualgo.net propone este algoritmo, el que se recorrre cuando ejecutas desde la web:

split each element into partitions of size 1
recursively merge adjancent partitions
  for i = leftPartStartIndex to rightPartLastIndex inclusive
    if leftPartHeadValue <= rightPartHeadValue
      copy leftPartHeadValue
    else: copy rightPartHeadValue
copy elements back to original array

Quick Sort

Idea: Usar una estrategia de “divide y vencerás”. Usar un pivote para hacer movimientos sobre los valores siguientes entre lo que sea menor o mayor que el pivote. Finalmente mueve el pivote para realizar ordenaciones acotadas, y hacer cambio de pivote.

visualgo.net propone este algoritmo, el que se recorrre cuando ejecutas desde la web:

for each (unsorted) partition
  set first element as pivot
  storeIndex = pivotIndex + 1
  for i = pivotIndex + 1 to rightmostIndex
    if element[i] < element[pivot]
      swap(i, storeIndex); storeIndex++
  swap(pivot, storeIndex - 1)

Count Sort

Idea: Almacenar los valores en otro lugar donde se ha almacenado cada elemento con su valor correspondiente. Finalmente reconstruir el listado original.

visualgo.net propone este algoritmo, el que se recorrre cuando ejecutas desde la web:

create key (counting) array
for each element in list
  increase the respective counter by 1
for each counter, starting from smallest key
  while counter is non-zero
    restore element to list
    decrease counter by 1

Resumen

Bueno es un resumen para quedarse con ciertas cosas de lo anterior:

  • La ordenación es uno de las aplicaciones más frecuentes usadas en programación
  • Los datos se pueden ordenar en forma ascendente o descendente
  • Cada recorrido sobre los datos se llama iteración o pasada
  • Los algoritmos de ordenación más conocidos son:
    •  Burbuja (Bubble)
    •  Selección (Select)
    •  Inserción (Insert)
    •  Mezcla (Merge)
    •  Rápida (Quick)
    •  Conteo (Count)
  • Los algoritmos Merge, Quick y Count son más eficientes que Bubble, Insert y Select.
notbad

Visualización de algoritmos. Bien.

Nos vemos en la red.

COBOL en The Terminator

Estamos cerca del estreno de Terminator Genesys, y esta expectativa me hizo ir a Netflix y volver a ver The Terminator.

No recuerdo haber visto la primera película de la serie de forma completa alguna vez. La que he visto varias veces fue la segunda parte. Entonces me he encontrado con algunas sorpresas que espero hagan más entretenido el visionado del próximo estreno. Por ejemplo el “¡Sube si quieres vivir!” de Sarah es un gag a la misma frase dicha en la primera película.

Estaba viendo la película y entonces comenzaron a aparecer imágenes de unos lentes de visión nocturna acompañados con ciertos códigos assembler.  Entonces recordé que alguna vez leí que aparecía código COBOL en dicha película. Casi a mitad de la misma, pude ver el dichoso momento: Se descubre finalmente que el misterioso personaje es un robot, y vemos por primera vez desde su punto de vista, y observamos unos códigos extraños que parecen hacer cálculos complejos, que acompañan la visión del exterminador (sí, le tomé foto a mi TV):

Captura The Therminator

I’ll be back!

¿No se ve bien no? Bueno, lo escribo aquí:

IDENTIFICACION DIVISION.
PROGRAM-ID. ADD.
ENVIRONMENT DIVISION.
DATA DIVISION.
WORDKING STORAGE SECTION.
77 IDX PICTURE 9999.
77 SUM PICTURE 999999.
77 X PICTURE X.
PROCEDURE DIVISION.
BEGIN.
ACCEPT X.
MOVE ZERO TO IDX.
MOVE ZERO TO SUM.
PERFORM ADD-PAR UNTIL IDX = 1441.

Y esto, señores, es COBOL. ¡En la visión del exterminador! ¡El exterminador está escrito en COBOL!

En reddit algunos comentarios al respecto son muy graciosos:

I’m in. – Oh, no, wait, I know COBOL. THIS GUY MUST BE STOPPED!!!

The terminator was supposed to be near unstoppable, highly reliable by socially inept. Sound like COBOL to me!

They don’t call it Big Iron for nothing.

Pero ¿qué hace ese código? ¿Hasta donde se ve, realmente está calculando la forma más letal de matar a Sarah? ¿habrá una función KillNow() o algo así?

A pesar de que el código está incompleto, en realidad, aparece el nombre del programa, el programa se llama ADD. ¿Qué creen que hace? El programa realmente comienza en el BEGIN, lo anterior es parte declarativa, aquí van los archivos a los que se accede, estructuras y variables que se van a usar a lo largo del programa y comúnmente estructucturas de SQL embebido para acceso a BD. Y no esperes objetos. Programación estructurada pura y dura.

Desde le BEGIN vemos un ACCEPT (sí, para recibir desde “afuera” un valor), dos inicializaciones y luego una estructura de bucle infinita que termina con la bandera IDX = 1441. ¿Qué podemos suponer que hacer este código? Puede ser como mínimo que sume los primeros 1441 números, con lo que el código se completaría así:

IDENTIFICATION DIVISION.
PROGRAM-ID. ADD.
ENVIRONMENT DIVISION.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 IDX PICTURE 9999.
01 SUMA PICTURE 999999.
01 X PICTURE X.
PROCEDURE DIVISION.
BEGIN.
ACCEPT X.
MOVE ZERO TO IDX.
MOVE ZERO TO SUMA.
PERFORM ADD-PAR UNTIL IDX = 1441.
PERFORM TERMINAR.
ADD-PAR.
ADD 1 TO IDX
ADD IDX TO SUMA.
TERMINAR.
DISPLAY X ” : LA SUMA DE LOS ” IDX ” NUMEROS ES ” SUMA “.”.
STOP RUN.

Por el DISPLAY obtendremos la salida del programa, la que se enviará hacia quien esté invocando a dicho programa ADD.

Es posible que esto no sea lo que haga este programa, y que luego de la línea de lo que se ve, venga mucho código, pero un programa que se llame ADD y que tenga solo tres variables (es un hecho que no hay más variables ni más llamadas a otros programas, tampoco ha acceso a base de datos ni acceso a archivos, esto se escribe en la parte declarativa), difícilmente está haciendo cálculos complejos de la cantidad de dolor que debe infligir a alguien o el nivel de daño que debe recibir un cuerpo humano para morir o la trayectoria de la bala para que alguien muera de una sola a la distancia máxima.

¿En serio?

¿En serio?

Es en serio. No obstante, vale como dato friki. La pregunta es, ¿en Terminator Genesys veremos código nuevamente? ¿Habrán actualizado esto o veremos más COBOL?

Nos vemos en la red.

[Actualización 20/07/2017]: Habían unos errores en el código fuente. Ya están corregidos. En este link está el .cob. Lo acabo de compilar y ejecutar con un compilador Microfocus Cobol para UNIX sin problemas.

Syncsort, DFSORT en JCL: Ejemplos de uso

Si trabajas en Mainframe, seguramente conoces sobre las herramientas de ordenación, sobre ICETOOL, ICEMAN,  etc. o SORT a secas.

Estas herramientas en realidad, resuelven a las herramientas producto instaladas en el Mainframe como DFSORT o Syncsort.

En mi trabajo, usábamos DFSORT, luego por alguna razón notamos que nos cambiamos a Syncsort, y dos años después, volvimos a DFSORT. DFSORT es la herramienta de ordenación de IBM. Mientras que Syncsort es la herramienta de la empresa del mismo nombre.

Una costumbre habitual es circunscribir nuestros desarrollos a los modelos y ejemplos ya realizados por los demás. Y con el tiempo suponer que esa es la única forma de hacer las cosas. No lo hagas. Duda, investiga, intenta siempre hacer las cosas de manera diferente.

Por ejemplo, era costumbre en mi trabajo usar los STEP de un JCL solo para llamar a programas COBOL, y a lo más, para hacer ordenaciones sencillas. Para todo los demás, como por ejemplo para la mezcla de archivos en un archivo único (el famoso matching), debíamos usar programas COBOL.

Entonces, con la llegada de Syncsort, se me ocurrió entrar a la web, y lo que encontré fue a miles de personas haciendo las cosas no solo de otra manera, sino que esa otra manera era más eficiente, más rápida y más confiable, es decir, mejor.

Conseguí el manual de Syncsort, y desde ese momento, y poco a poco, en mi equipo ahora se usan muchos STEP de ordenaciones cada vez más complejos. Si el criterio antes era “usa los JCL para llamar a programas y para hacer ordenaciones simples“, ahora ha cambiado a “usa los JCL todo lo que puedas excepto para acceso a datos y decisiones complejas“.

"Sí jefe..."

“Sí jefe, tres días para hacer un programa que haga matching de dos archivos y grabe en la salida solo los registros que hagan match.”

Aquí algunos ejemplos tipo:

1. letf outer join (Es decir, para dos archivos A y B, obtener A – B)

//STEP1 EXEC PGM=SORT
//SORTJNF1 DD DSN=INPUT.FILE1 (VB/255)
//SORTJNF2 DD DSN=INPUT.FILE2 (VB/255)
//SORTOUT DD DSN=OUTPUT.FILE (VB/255)
//SYSOUT DD SYSOUT=*
//SYSIN DD *
JOINKEYS FILES=F1,FIELDS=(5,6,A,12,4,A,19,1,A)
JOINKEYS FILES=F2,FIELDS=(5,6,A,32,4,A,50,1,A)
JOIN UNPAIRED,F1
REFORMAT FIELDS=(F1:5,251,F2:5,251)
SORT FIELDS=COPY
OUTFIL FILES=OUT,
IFTHEN=(WHEN=(252,1,CH,EQ,C’ ‘),BUILD=(1,251)),
IFTHEN=(WHEN=(252,1,CH,NE,C’ ‘),BUILD=(1,251,/,252,251)),
FTOV
/*

2. Únicos y repetidos (Es decir, de una entrada dada, dejar dos archivos: Uno con los repetidos y otro con los de una sola ocurrencia).

//STEP1 EXEC PGM=SORT
//SORTIN DD *
0001
0002
0002
0003
0004
0005
0005
//SORTXDUP DD DSN=&&XDUP,DISP=(NEW,PASS)
//SORTOF01 DD DSN=&&OUT1,DISP=(NEW,PASS)
//SORTOF02 DD DSN=UNIQUE.RECORDS
//SYSOUT DD SYSOUT=*
//SYSIN DD *
INREC OVERLAY=(81:X’F1′)
SORT FIELDS=(1,5,CH,A)
DUPKEYS SUM=(81,1,ZD),XDUP
OUTFIL FILES=01,INCLUDE=(81,1,ZD,GT,1)
OUTFIL FILES=02,INCLUDE=(81,1,ZD,EQ,1),BUILD=(1,80)
/*
//STEP2 EXEC PGM=SORT
//SORTIN01 DD DSN=&&XDUP,DISP=SHR
//SORTIN02 DD DSN=&&OUT1,DISP=SHR
//SORTOUT DD DSN=ALLDUPS
//SYSOUT DD SYSOUT=*
//SYSIN DD *
INREC BUILD=(1,80)
MERGE FIELDS=(1,5,CH,A)
/*

3. Tres archivos: match, f1-f2 y f2-f1 (Es decir, dadas dos entradas F1 y F2, tener tres salidas: Lo común, F1 – F2 y F2 -F1)

//SYSIN DD *
JOINKEYS FILE=F1,FIELDS=(1,30,A)
JOINKEYS FILE=F2,FIELDS=(7,30,A)
JOIN UNPAIRED
REFORMAT FIELDS=(F2:1,93,F1:1,1717),FILL=X’FF’,
SORT FIELDS=COPY
OUTFIL FILES=03,INCLUDE=(1,1,CH,EQ,X’FF’),BUILD=(94,1717)
OUTFIL FILES=02,INCLUDE=(94,1,CH,EQ,X’FF’),BUILD=(1,93)
OUTFIL FILES=01,SAVE,BUILD=(1,93)
/*

4. Completar datos de una entrada, si no encontró, agregar texto

//STEP1 EXEC PGM=SORT
//SORTJNF1 DD *
A00001
A00002
A00003
A00004
//SORTJNF2 DD *
A00001. 90
A00003. 39
//SORTOUT DD SYSOUT=*
//SYSOUT DD SYSOUT=*
//SYSIN DD *
JOINKEYS FILES=F1,FIELDS=(1,6,A)
JOINKEYS FILES=F2,FIELDS=(1,6,A)
JOIN UNPAIRED,F1
REFORMAT FIELDS=(F1:1,6,F2:7,8)
SORT FIELDS=COPY
OUTREC IFTHEN=(WHEN=(7,8,CH,EQ,C’ ‘),OVERLAY=(7:C’. 00′))
/*

5. Formatear packed decimal (conversión a valores editados)

//SYSIN DD *
SORT FIELDS=COPY
OUTREC IFTHEN=(WHEN=(31,4,CH,EQ,C’1130′),
OVERLAY=(36:36,10,PD,EDIT=(STTTTTTTTTTTTTTTTTTT.TT),SIGNS=(+,-))),
IFTHEN=(WHEN=(31,4,CH,EQ,C’1131′),
OVERLAY=(46:36,10,PD,EDIT=(STTTTTTTTTTTTTTTTTTT.TT),SIGNS=(+,-))),
IFTHEN=(WHEN=(31,4,CH,EQ,C’1132′),
OVERLAY=(55:36,10,PD,EDIT=(STTTTTTTTTTTTTTTTTTT.TT),SIGNS=(+,-)))

6. Convertir PD (packed decimal) a zd (zoned decimal) (o desempaquetar un numérico)

//SYSIN DD *
SORT FIELDS=COPY
OUTREC FIELDS=(325,7,PD,TO=ZD,LENGTH=13)
/*

7. Convertir ZD a PD, según condición de entrada (o empaquetar un numérico)

OPTION COPY
INREC IFTHEN=(WHEN=(1,2,CH,EQ,C’30’),
OVERLAY=(3:3,8,FS,TO=PD,LENGTH=5,3X))
/*

8. Formatear una salida (construir un archivo de salida a partir de los archivos de entrada y otras condiciones)

OUTREC BUILD=(5,2,5C’*’,18,6,C’ABC’,+30,TO=BI,LENGTH=4,X’01’,80:X)

9. Finder dentro de un master (buscar una muestra dentro de un todo)

//JOIN EXEC PGM=SYNCSORT
//SORTJNF1 DD DSN=YOUR.INPUT.MASTER.FILE
//SORTJNF2 DD DSN=YOUR.FINDER.FILE
//SORTOUT DD DSN=YOUR.DESIRED.OUTPUT.FILE
//SYSOUT DD SYSOUT=*
//SYSIN DD *
JOINKEYS FILE=F1,FIELDS=(22,15,CH,A),SORTED
JOINKEYS FILE=F2,FIELDS=(1,15,CH,A),SORTED
REFORMAT FIELDS=(F1:1,3400)
SORT FIELDS=COPY
END
/*

Estos ejemplos en realidad funcionan en cualquier herramienta de ordenación. Todos estos ejemplos fueron tomados de Internet, y los fui ubicando a medida que los necesitaba.

¿Y cuál es la diferencia con hacer un programa COBOL que realice lo mismo? Total, también hay modelos ¿no?. Bueno, estas herramientas son tipo comandos a los que hay que cambiar los parámetros, y estamos seguros que los matching, conteos, sumas, restas u formateos no fallan. Las pruebas se enfocan en ver que hayamos puestos los parámetros de forma correcta y obtener la salida esperada. En cambio, cuando un programa COBOL hace un matching, hay que hacer varios tests de prueba, antes de estar seguros que el programa hacer el matching adecuadamente. Luego recién haremos las pruebas funcionales para ver que obtener la salida esperada. Ha habido más de una incidencia, cuya causa estaba asociada a defectos encontrados en estos programas COBOL. Una última ventaja, pasar un JCL por un circuito de cambios y de pase a Producción es más sencillo.

El motivo de este post es dejar en línea estos ejemplos tipo. Los apuntes se pierden con el tiempo.

Obtener los índices de una tabla (en DB2 y en Oracle)

Cuando vemos nuevos desarrollos, mantenimientos o atendemos incidencias, por lo general tenemos dudas que siempre debemos absolver mientras analizamos un pedido.

Por ejemplo, es muy habitual que necesitemos saber con qué índices cuenta una tabla, y con qué campos  están formados dichos índices.

Quienes trabajan en entornos gráficos, encontrarán esta duda muy trivial, ya que en pocos clics, con TOAD o con SQL Developer, por ejemplo, esta información es fácilmente identificable y de ubicación rápida.

Pero ¿qué si trabajamos en Mainframe con una Base de Datos (BD) en DB2? y ¿qué si trabajamos en UNIX con una BD en Oracle, la cual no se puede acceder con una herramienta gráfica? Esto puede pasar. A mí me sucede en el trabajo, dado que las dos aplicaciones que vemos en mi equipo están en estas tecnologías. Una en Mainframe y la otra en un UNIX.

En Oracle es más sencillo; buscas en Internet y en pocos minutos obtienes un query que te saca del apuro. En DB2 también, no obstante hay menos páginas con esta información. De todas maneras, siempre es bueno tener estos datos a la mano. Me ha pasado que la información que encontré en una página, meses después no la pude ubicar porque la página ya no estaba en línea.

¡Mi incidencia!

¡Mi incidencia sigue abierta!¡Cuáles son los índices de esa tabla!

Entonces, el query en DB2 puede ser este:

SELECT SUBSTR(TBNAME, 1, 10) AS TBNAME,      
      SUBSTR(NAME, 1, 15) AS NAME,          
      SUBSTR(COLNAME, 1, 15) AS COLNAME,    
      UNIQUERULE ,                          
      CLUSTERING                            
 FROM SYSIBM.SYSINDEXES A , SYSIBM.SYSKEYS B
WHERE A.NAME  = B.IXNAME                      
  AND A.TBNAME = ‘<NOMBRE_TABLA>’;

Y en Oracle, este:

Select table_name, index_name, column_name FROM user_ind_columns where table_name like ‘<NOMBRE_TABLA>’ Order by table_name, column_name;

El motivo de este post es pasar el testigo, mantener este contenido en línea, y tener esta información a la mano, para mí, y para quien lo necesite.