CLASE NÚMERO 12

ALGORITMOS DE BÚSQUEDA Y ORDENAMIENTO

Discutiremos el problema de ordenar un array de elementos. A los efectos de simplificar asumiremos que los arrays contienen solo enteros aunque obviamente estructuras más complicadas son posibles. Asumiremos también que el ordenamiento completo se puede realizar en memoria principal o sea la cantidad de elementos es relativamente pequeo (menos de un millón).

 Preliminares Los algoritmos que describiremos reciben como argumentos un array que pasa los elementos y un entero que representa la cantidad de elementos. Asumiremos que N (el número de elementos) es un n´umero legal. Para alguno de los programas que veremos ser´a conveniente utilizar un sentinela en posición 0, por lo cual nuestros array irán del 0 al N. Los datos irán del 1 al N.

Ordenamiento por inserción (Insertion Sort) Es uno de los algoritmos m´as simples. Consiste en N − 1 pasadas. En las pasadas 2 a N se cumplir´a que los elementos de las posiciones 1 a P est´an ordenados. En la pasada P movemos el elemento P-esimo a su lugar correcto, este lugar es encontrado en las posiciones de los elementos 1 a P.

Con frecuencia el programador trabajar´a con grandes cantidades de información almacenada en arreglos. Podría ser necesario determinar si algún arreglo contiene un valor que sea igual a cierto valor clave. El proceso para encontrar un elemento particular en un arreglo se llama búsqueda. Estudiaremos dos técnicas de búsqueda: una técnica simple llamada busqueda lineal y una m´as eficiente llamada busqueda binaria. Ambos programas se pueden implementar recursivamente o no. En este capítulo veremos la implementación no recursiva. 

Empezamos la clase viendo algunos blogs, en donde varios compañeros tenían la tarea y algunos no la hicieron.

El profesor nos puso a repasar a cerca de las dimensiones y con ello nos puso a hacer, con todo el tiempo de la clase, el juego ahorcado en PSeint, algoritmo y prueba de escritorio.

A la final ninguno pudo terminar el pseudocódigo y solo pudimos presenta el algoritmo del juego.