Algoritmos de ordenación no recursivos

3. Conceptos
   preliminares
4. Cuándo aplicar un
   método
5. Tipos de
   ordenamientos
6. Clasificación de los
   algoritmos de ordenamiento
7. Algoritmo
   burbuja
8. Algoritmo
   inserción
9. Algoritmo
   selección
10. Algoritmo
    Shake
11. Algoritmo
    Shell
12. Ejercicios
    de aplicación
13. Bibliografía

INTRODUCCION

El ordenamiento es una labor común que realizamos
cotidianamente, es un proceso tan
común en nuestras vidas que no nos detenemos a meditar
mucho en ello. Ordenar es meramente colocar información de una manera especial
basándonos en un criterio de ordenamiento.

En la ciencia de
la computación el ordenamiento de datos
también cumple un rol muy importante, ya sea como un fin
en sí o como parte de otros procedimientos
más complejos. Se han desarrollado muchas técnicas
en este ámbito, cada una con características
específicas, y con ventajas y desventajas sobre las
demás. El propósito principal de un ordenamiento es
el de facilitar la búsqueda de
información.

El ordenar un grupo de datos
significa mover los datos o sus referencias para que queden en
una secuencia tal que represente un orden, el cual puede ser
numérico, alfabético o incluso alfanumérico,
ascendente o descendente.

Conceptos
Preliminares

Antes de comenzar a ver cada algoritmo
vamos a ponernos de acuerdo en algunos conceptos, para que no
haya confusiones:

• Clave: La parte de un registro por la
  cual se ordena la lista. Por ejemplo, una lista de registros con
  campos nombre, dirección y teléfono se puede ordenar
  alfabéticamente de acuerdo al nombre. En este caso los
  campos dirección y teléfono no se toman en cuenta
  en el ordenamiento.
• Criterio de ordenamiento o de
  comparación: El criterio que utilizamos para asignar
  orden a los registros con base en una o más claves. De
  esta manera decidimos si un registro es mayor o menor que
  otro.
• Registro: Un grupo de datos que forman la
  lista. Pueden ser datos primitivos enteros, caracteres, reales,
  etc., o grupos de
  ellos, que en C++ equivalen a estructuras
  de datos.

Cuándo APLICAR un
método

Cuando se requiere hacer una cantidad considerable de
búsquedas y es importante el factor tiempo.

Al estudiar algoritmos de
todo tipo, no sólo de ordenamiento, es bueno tener una
forma de evaluarlos antes de pasarlos a código.
De esta manera podremos decidir cuál se adapta mejor a los
requerimientos de nuestro programa.
Así que veamos estos aspectos:

• Estabilidad: Cómo se comporta con
  registros que tienen claves iguales. Algunos algoritmos
  mantienen el orden relativo entre éstos y otros no.
  Veamos un ejemplo. Si tenemos la siguiente lista de
  datos:

(Nombre, Edad)

Pedro 19, Juan 23, Felipe 15, Marcela 20, Juan 18,
Marcela 17

Ordenada alfabéticamente por el nombre con un
algoritmo estable quedaría así:

Felipe 15, Marcela 20, Marcela 17, Juan 23, Juan
18, Pedro 19

Un algoritmo no estable podría dejar a Juan
18 antes de Juan 23, o a Marcela 20
después de Marcela 17.

• Tiempo de ejecución: La complejidad del
  algoritmo, que no tiene que ver con dificultad del algoritmo,
  mas bien con el rendimiento o la eficiencia del
  algoritmo. Es una función
  independiente de la implementación o de los factores
  externos. Tendremos que identificar una operación
  fundamental que realice nuestro algoritmo, que en este caso es
  comparar. Ahora contamos cuántas veces el algoritmo
  necesita comparar. Si en una lista de n términos realiza
  n comparaciones la complejidad es O(n). Una medida de
  eficiencia es:

• Contar el número de comparaciones
• Contar el número de movimientos de
  ítems
• Estos están en función del
  número de elementos a ser ordenados.
• Un buen algoritmo de ordenamiento requiere de O(n log
  n) comparaciones.

• Requerimientos de memoria: El
  algoritmo puede necesitar memoria adicional para realizar su
  labor. En general es preferible que no sea así, pero es
  común en la programación tener que sacrificar memoria
  por rendimiento.

Tipos de ordenamientos

internos

Los datos a ordenar están en memoria la principal
RAM, por lo que
se asume que el tiempo que se requiere para acceder cualquier
elemento sea el mismo.

externos

Los datos a ordenar están en la memoria
secundaria, es decir, disco duro,
disco extraíble, por lo que se asume que el tiempo que se
requiere para acceder a cualquier elemento depende de la
última posición consultada.

Clasificación de
los algoritmos de ordenamiento

Los métodos
simples son: Inserción Directa, Selección, Burbuja
y Shell, en dónde el último es una extensión
al método de
Inserción, siendo más rápido. Los
métodos más complejos son Quick Sort y
Heap.

Algoritmo Burbuja

Bubble Sort recorre el arreglo intercambiando los
elementos adyacentes que estén desordenados. Recorre el
arreglo tantas veces hasta que ya no haya cambios.
Prácticamente lo que hace es tomar el elemento mayor y lo
coloca en las últimas posiciones o tomar el menor y
colocarlo en las primeras posiciones.

PSEUDOCÓDIGO

ALGORITMO BURBUJA

INICIO

ENTERO X, Z, ARREGLO[N]

X ß 0

MIENTRAS(X < N)

{

Z ß N

MIENTRAS(Z >= 0)

{

SI(ARREGLO[Z] < ARREGLO[Z-1])

{

INTERCAMBIO(ARREGLO[Z],ARREGLO[Z-1])

}

Z ß Z –
1

}

X ß X + 1

}

FIN

CÓDIGO EN
C++

void burbuja(void)

{

int x, z, aux, ARREGLO[N];

x = 0;

while(x < N)

{

z = N;

while(z >= 0)

{

if(ARREGLO[z] < ARREGLO[z – 1])

{

aux = ARREGLO[z];

ARREGLO[z] = ARREGLO[z – 1];

ARREGLO[z – 1] = aux;

}

z–;

}

x++;

}

}

Tiempo de ejecución: El ciclo interno se
ejecuta n veces. El ciclo externo también se ejecuta n
veces, la complejidad es n * n = O(n2). El comportamiento
del caso promedio depende del orden de entrada de los datos, pero
es sólo un poco mejor que el del peor caso, y sigue siendo
O(n2).

Estabilidad: No intercambia registros con claves
iguales.

Ventajas:

• Fácil implementación.
• No requiere memoria adicional.

Desventajas:

• Muy lento.
• Muchas comparaciones.
• Muchos intercambios.

Algoritmo Inserción

Este método consiste en insertar un elemento en
una parte ya ordenada del vector y comenzar de nuevo con los
elementos restantes. Este también es un algoritmo lento,
pero puede ser de utilidad para
listas semiordenadas, pues en ese caso realiza pocos
desplazamientos.

PSEUDOCÓDIGO

ALGORITMO INSERCIÓN

INICIO

ENTERO X, Z, AUX, ARREGLO[N]

LOGICO B

PARA(X ß 1, HASTA N,
X ß X + 1)

{

AUX ß
ARRAY[X]

Z ß X – 1

B ß FALSO

MIENTRAS(B = FALSO Y Z >= 0)

{

SI(AUX < ARREGLO[Z])

{

ARREGLO[Z + 1] ß
ARREGLO[Z]

Z ß Z –
1

}

SI NO

{

B ß
VERDAD

}

}

ARREGLO[Z + 1] ß
AUX

}

FIN

CÓDIGO EN
C++

void insercion(void)

{

int x,z, aux, ARREGLO[N];

bool b;

for(x = 1; x < N; x++)

{

aux = ARREGLO[x];

z = x – 1;

flag = false;

while(b == false && z >= 0)

{

if(aux < ARREGLO[z])

{

ARREGLO[z + 1] = ARREGLO[z];

z–;

}

else

b = true;

}

ARREGLO[z + 1] = aux;

}

}

Ejemplo:

Tiempo de Ejecución: Para una
lista de n elementos el ciclo externo se ejecuta n-1 veces. El
ciclo interno se ejecuta como máximo 1, 2, 3 veces a la
tercera iteración, etc., esto tratándose del pero
caso posible. Esto produce una complejidad
O(n2).

Estabilidad: No intercambia
registros con claves iguales. Por lo tanto es estable.

Ventajas:

• Fácil implementación.
• Requerimientos mínimos de memoria.

Desventajas:

• Lento.
• Numerosas comparaciones.