Agregar a favoritos      Ayuda      Português      Ingles     

Algoritmos de ordenación no recursivos

Enviado por Rolf Pinto López



Partes: 1, 2

  1. Conceptos preliminares
  2. Cuándo aplicar un método
  3. Tipos de ordenamientos
  4. Clasificación de los algoritmos de ordenamiento
  5. Algoritmo burbuja
  6. Algoritmo inserción
  7. Algoritmo selección
  8. Algoritmo Shake
  9. Algoritmo Shell
  10. Ejercicios de aplicación
  11. 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.

Inserción Directa

Inserción Directa

Inserción Binaria

Selección Directa

Selección Directa

Intercambio Directo

Burbuja

Shake

Inserción Disminución Incremental

Shell

Ordenamiento De Árbol

Heap

Tournament

Sort Particionado

Quick Sort

Merge Sort

Radix Sort

Cálculo De Dirección

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.

Straight Merging

Natural Merging

Balanced Multiway Merging

Polyphase Sort

Distribution Of Initial Runs

 

Clasificación de los algoritmos de ordenamiento

Algoritmos de inserción:

Inserción Directa

Shell

Inserción Binaria

Hashing

Algoritmos de intercambio:

Burbuja

Shake

Quick Sort

Algoritmos de selección:

Selección Directa ü

Algoritmos de enumeración:

Merge

Radix

Heap

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:

[0]

15

15

10

10

10

10

10

10

10

10

10

10

10

10

7

[1]

10

ð 15

15

15

15

14

14

14

14

11

11

11

11

ð 10

10

[2]

14

14

14

ð 15

15

15

15

ð 14

14

14

14

14

ð 11

11

11

[3]

11

11

11

11

11

11

ð 15

15

15

15

15

ð 14

14

14

14

[4]

7

7

7

7

7

7

7

7

7

7

ð 15

15

15

15

15

ê

ê

ê

ê

ê

X

1

2

3

4

5

Z

0

-1

1

0

2

1

0

3

2

1

0

-1

4

B

F

F

T

F

T

F

F

AUX

10

14

11

7

?

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.

Partes: 1, 2

Página siguiente 

Comentarios


Trabajos relacionados

Ver mas trabajos de Programacion

 

Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.


Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

Iniciar sesión

Ingrese el e-mail y contraseña con el que está registrado en Monografias.com

   
 

Regístrese gratis

¿Olvidó su contraseña?

Ayuda