ORDENAMIENTO
Algoritmos y Estructuras de Datos II
Lic. Ana María Company
INTRODUCCIÓN
En algunos casos se necesita tener ordenados,
siguiendo algún criterio, los datos con los que se
trabaja para facilitar su tratamiento.
La ordenación(clasificación) es la operación de
organizar un conjunto de datos en algún orden
dado, por ejemplo:
• Creciente/decreciente
(ascendente/descendente) en datos numéricos
• En orden alfabético (A - Z / Z – A)
MÉTODOS DIRECTOS
o Selección directa
o Inserción directa (Baraja)
o Intercambio directo (Burbuja)
SELECCIÓN DIRECTA
También conocido como Obtención sucesiva de
menores.
Se recorre el vector y se selecciona en cada recorrido
el menor elemento para situarlo en su lugar
correspondiente.
El esquema básico del algoritmo es:
1. Se sitúa en v1 el menor valor entre v1; …; vn
Para ello se intercambian los valores de v1 y vm
siendo vm= mín{vk} con k = 1;…;n.
Ej: para un vector V (4, 5, 7, 1, 9, 8, 2)
4571982
SELECCIÓN DIRECTA
2. Se sitúa en v2 el menor valor entre v2; …; vn
• Para ello se intercambian los valores de v2 y vm
siendo vm= mín{vk} con k = 2;…;n.
Siguiendo el ejemplo, en este paso se realiza el siguiente intercambio:
1574982
…
j-1. Se sitúa en vj-1 el menor valor entre vj-1; …; vn
Para ello se intercambian los valores de vj-1 y vm
siendo vm= mín{vk} con k = j-1;…;n.
…
n-1. Se sitúa en vn-1 el menor valor entre vn-1; …; vn
Para ello se intercambian los valores de vn-1 y vn si es necesario
Para el ejemplo, el estado final es: 1245789
SELECCIÓN DIRECTA - Ejemplo
INSERCIÓN DIRECTA
También conocido como Baraja
Se recorre el vector V insertando el elemento vi en su lugar correcto
entre los ya ordenados v1; …; vi-1.
El esquema general de este algoritmo es:
1. Se considera v1 como primer elemento.
2. Se inserta v2 en su posición correspondiente en relación a v1 y
v2.
3. Se inserta v3 en su posición correspondiente en relación a v1;
… ; v3.
...
i. Se inserta vi en su posición correspondiente en relación a v1;
… ; vi.
...
n. Se inserta vn en su posición correspondiente en relación a v1;
… ; vn.
INSERCIÓN DIRECTA - Ejemplo
INTERCAMBIO DIRECTO (Burbuja)
Compara cada elemento de un vector V con el
siguiente, intercambiándolos de posición si están
en el orden equivocado.
Será necesario recorrer varias veces todo el vector
hasta que no se necesiten más intercambios.
INTERCAMBIO DIRECTO (Burbuja)
• Se realizan (n-1) pasadas, transportando en
cada pasada el menor o mayor elemento
(según sea el caso) a su posición ideal.
• Al final de las (n-1) pasadas los elementos del
arreglo estarán ordenados.
• También se conoce a este algoritmo como
método de la Burbuja, por la forma en que se
mueven los elementos durante los
intercambios, como si fueran pequeñas
"burbujas".
INTERCAMBIO DIRECTO (Burbuja)
Pasos:
1. Comparar elemento en la 1ra posición con el
elemento en la 2da posición, si están ordenados, se
deja como está, caso contrario se realiza el
intercambio.
2. Se comparan los dos elementos siguientes
adyacentes: elemento de la 2da posición con el
elemento de la 3ra posición, y de nuevo se
intercambia si es necesario.
3. El proceso continúa hasta que cada elemento del
arreglo haya sido comparado con sus elementos
adyacentes y hayan sido intercambiados en los casos
necesarios.
INTERCAMBIO DIRECTO - Ejemplo
BIBLIOGRAFÍA
Mark Allen Weiss - Estructuras de Datos y Algoritmos - Florida
International University - Año: 1995 - Editorial: Addison-Wesley
Iberoamericana .
Joyanes Aguilar, Luis - Programación en Pascal - 4ª Edición - Año:
2006 - Editorial: McGraw-Hill/Interamericana de España, S.A.U.
Cristóbal Pareja Flores, Manuel Ojeda Aciego, Ángel Andeyro
Quesada, Carlos Rossi Jiménez - Algoritmos y Programación en
Pascal.
Joyanes Aguilar, Luis - Fundamentos de la Programación. Algoritmos,
Estructuras de Datos y Objetos - 3ª Edición - Editorial: McGraw-Hill
