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.

La computación como disciplina parte 1

Este texto es muy interesante. Recomendado.

What's going on?

Actualmente vengo trabajando en la traducción del reporte de la disciplina de la computación de Peter J. Denning y otros autores de 1989. Este texto es imporPeter_J._Denningtante para la difusión de la computación como cuerpo de conocimiento y como profesión en el país. En el Perú el debate sobre la disciplina aún mantiene antiguas percepciones sobre la disciplina, sobre todo por la mayor presencia de escuelas de ingeniería. Contar con la traducción de este texto es importante para una difusión del campo y también para la adopción en las distintas instituciones del país.

Dice una frase, “traductor, traidor”, espero que este trabajo de traducción se ajuste al texto original y permita conocer con mayor amplitud las bases de la disciplina de la computación para diferentes intereses y objetivos, pero principalmente para superar las diferencias que aún mantiene nuestra comunidad.

Aquí comparto la primera página del texto, más adelante continuaré…

Ver la entrada original 1.910 palabras más