Algoritmos de ordenacion

Algoritmos de ordenación y búsqueda
Objetivos:
Tener una visión general de los métodos de ordenación y búsqueda más comunes. Programar varios métodos de ordenación y búsqueda en lenguaje C.Informática Aplicada 06-07

1

Algoritmos de ordenación
Se parte de un vector de elementos desordenados (números enteros, cadenas…) Se pretende ordenar los elementos del vector según algún criterio.Parámetros a tener en cuenta:
Tiempo utilizado por el algoritmo para realizar la ordenación. Memoria del ordenador utilizada durante la ordenación.

Algunos algoritmos de ordenación realizan delorden de N2 operaciones. Si N es el número de elementos a ordenar. Son métodos directos, de pocas líneas de código, de tal forma que si N es pequeño, son lo suficientemente eficaces. Los algoritmos deordenación más eficientes realizan del orden de N·log2N operaciones.
Informática Aplicada 06-07 2

Un método simple: Método de ordenación burbuja
Consiste en recorrer sucesivamente el vectorcomparando los elementos consecutivos e intercambiándolos (si no están en orden). Vamos a ordenar números enteros, de izquierda a derecha.
10 2 41 56 3 1 57 23 45 22

El resultado que buscamos es elsiguiente:
1 2 3 10 22 23 41 45 56 57

Informática Aplicada 06-07

3

Un método simple: Método de ordenación burbuja
Realizamos una pasada por el vector, comparando los elementos del vector porparejas. Si no se cumple el orden los intercambiamos. Primera pasada:
10 2 41 56 3 1 57 23 45 22

Intercambiamos 2-10 2 10 41 56 3 1 57 23 45 22 2 10 41 3 56 1 57 23 45 22 Intercambiamos 3-56 Etc…Los elementos mayores “suben” como burbujas. Fin de la primera pasada: 2 10 41 3 1 56 23 23 45 22 57 ¿Cuántas pasadas debemos dar?
Informática Aplicada 06-07 4

Método burbuja
voidOrdenarBurbuja(int n, int *pvector) { int i, j, aux; for(j = 1; j < n; j++) { for(i = 0; i < n - j; i++) { if(pvector[i] > pvector[i+1]) { // Si el elemento de la derecha es menor: aux = pvector[i] pvector[i] =...