Algoritmos de Ordenamiento - Intercambio y Selección

Algoritmos de Ordenamiento

Describir los conceptos y especificaciones principales acerca de las listas.

Algoritmos de búsqueda

1. Método de la intercambio

2. Método de la selección

Temas: Objetivo:

ORDENAMIENTO

¿Qué es y como funciona?

ALGORITMO DE ORDENAMIENTO

Es la clasificación de datos que refiere a la disposición de un conjunto (estructura) de datos en algún orden determinado con respecto a uno de los campos de los elementos del conjunto.

ALGORITMO DE ORDENAMIENTO

Cuando tenemos un conjunto de n elementos: a1, a2,…, an y queremos obtener el mismo conjunto pero de tal forma que:

• Ordenamiento por intercambio

• Ordenamiento por burbuja

• Ordenamiento por inserción

• Ordenamiento por selección

DIRECTOS

• Ordenamiento por mezcla (Mergesort)

• Ordenamiento rápido (Quicksort)

• Ordenamiento por Montículos (Heap sort)

INDIRECTOS

• Ordenamiento por Incrementos (Shell sort)

• Ordenamiento por Cubetas (Bin sort)

• Ordenamiento por Resíduos (RadVIII)

OTROS

​CLASIFICACIÓN

Antes de realizar la búsqueda binaria es necesario que el arreglo esté ordenado de menor a mayor o en orden alfabético.

BÚSQUEDA

Se basa en leer varias veces la lista a ordenar, a cada una de estas lecturas se le llama "pase" o "pasada".

ALGORITMO

Multiple Choice

Es la clasificación de datos que refiere a la disposición de un conjunto (_________) de datos en algún orden determinado con respecto a uno de los campos de los elementos del conjunto.

• recurso

• estructura

• filas

• reglas

Multiple Choice

Son ejemplos de la clasificación "Directos":

• Ordenamiento por mezcla (Shellsort)

• Ordenamiento rápido (Quicksort)

• Ordenamiento por burbuja

• Ordenamiento por Incrementos (Shell sort)

Multiple Choice

Son ejemplos de la clasificación "Indirectos":

• Ordenamiento por mezcla (Shell sort)

• Ordenamiento rápido (Quicksort)

• Ordenamiento por burbuja

• Ordenamiento por Incrementos (Shell sort)

Multiple Choice

Son ejemplos de la clasificación "Mixto/Otros":

• Ordenamiento por mezcla (Shell sort)

• Ordenamiento rápido (Quicksort)

• Ordenamiento por burbuja

• Ordenamiento por Incrementos (Shell sort)

Método de intercambio

• ​Este algoritmo se basa en leer varias veces la lista a ordenar, a cada una de estas lecturas se le llama pase o pasada.

• Recorrer el arreglo hasta n-1

• Recorrer los elementos siguientes para realizar cambios

• Si numero anterior es mayor a actual realiza cambios

​Efectua cambio si:

numAnt > numActual

Método de Intercambio

8 - 4 - 9 - 2 - 1 - 6 - 5

¿Cuántos pases?

¿Cuántos intercambios por cada pase?

Realiza el procedimiento en tu libreta

Open Ended

De la siguiente sucesión de números: 8 - 4 - 9 - 2 - 1 - 6 - 5

¿Cuántos pases?

Open Ended

De la siguiente sucesión de números: 8 - 4 - 9 - 2 - 1 - 6 - 5

¿Cuántos intercambios por cada pase?

Ejemplo: Pase 1 - 5 cambios; Pase 2 - 3 cambios

Ejemplo en C++

Método de selección

Este algoritmo requiere operaciones para ordenar una lista de n elementos:

• Buscas el elemento más pequeño de la lista.

• Intercambio con el primer elemento.

• Busca el segundo elemento más pequeño de la lista.

• Lo intercambia con el elemento que ocupa la segunda posición en la lista.

• Repites este proceso hasta que hayas ordenado toda la lista.

​Efectua cambio si:

numActual < min

Método de Selección

10 - 2 - 7 - 8 - 1 - 6 - 4 - 5

¿Cuántos pases?

¿Cuántos intercambios por cada pase?

Realiza el procedimiento en tu libreta

Open Ended

De la siguiente sucesión de números: 10 - 2 - 7 - 8 - 1 - 6 - 4 - 5

¿Cuántos pases?

Open Ended

De la siguiente sucesión de números: 10 - 2 - 7 - 8 - 1 - 6 - 4 - 5

¿Cuántos intercambios por cada pase?

Ejemplo: Pase 1 - 5 cambios; Pase 2 - 3 cambios

Ejemplo en C++