Problema de Algoritmos de ordenación #1

Post Series: Problema #1 - Ordenación

Este nuevo post, va ha ser el primero de una serie de post en los cuales se resolverá el problema planteado. El problema estará planteado con el objetivo de resolverlo usando 6 algoritmos diferentes, de los cuales 5 serán de ordenación y uno será un método directo de obtención del resultado.

Enunciado del problema

Dados un vector T, que contiene n números enteros positivos (n<10^6), y un numero entero m > 0 , queremos un algoritmo que imprima los m números menores de T.  Sabemos que m es mucho menor que n. Queremos un estudio analtico y experimental de distintas soluciones para este problema. Se deberán considerar soluciones en las que se ordene el vector T y otras en las que no se ordene: selectionSort, Insertion Sort, mergeSort, quickSort, heap, select(k-esimo).

Estructura

Para proceder a la resolución de este problema se irán creando una serie de posts, 1 por algoritmo, 6 en total. Con la explicación del algoritmo y su propia implementación. Al final de cada post se procederá a realizar un estudio analítico del mismo.
Cada Post siempre seguirá la siguiente estructura.
  1. Introducción: Una breve explicación del algoritmo que se va a presentar.
  2. Explicación: Explicación del funcionamiento del algoritmo mediante texto e imágenes.
  3. Implementación: Desarrollo del algoritmo siguiendo la estructura explicada en el apartado anterior. En código estará programado en el lenguaje: Java.
  4. Análisis: Al final se realizará un análisis de la eficiencia del algoritmo presentándolo de forma matemática y mostrando al orden algorítmico.

Los algoritmos que van a ser explicados para la resolución de este problema serán:

  1. SelectionSort.
  2. Insertion Sort.
  3. MergeSort.
  4. QuickSort.
  5. Heap (Binary heap).
  6. Select(k-esimo).

Tras la finalización del problema se realizará un ultimo post resumen con los resultados de todos los algoritmos.

Un saludo! Para cualquier duda ponerla en los comentarios. Nos vemos en el siguiente post!

Problema extraído de la asignatura de Diseño de Algoritmos (DA) de la Universidad del País Vasco. EHU/UPV. Facultad de Informática. Especialización en Computación.

Leave a Reply

Your email address will not be published.