Metodos De Ordenamiento

Ordenamiento: Un algoritmo de
ordenamiento es un algoritmo que
pone elementos de una lista o un
vector en una secuencia dada por
una relación de orden, es decir, el
resultado de salida ha de ser un
reordenamiento de la entrada.

Hay dos categorías importantes sobre algoritmos de ordenación.
1.
2.

Ordenación Interna: Cantidad de Registros es pequeña por lo tanto el proceso
es enmemoria.
Ordenación Externa: Demasiados registros por lo tanto se deben usar
almacenamiento en disco.

Un método de ordenación se denomina estable si el orden relativo de los
elementos no se altera por el proceso de ordenamiento.

Tipos de algoritmos
1. Algoritmos iterativos.
Estos métodos son simples de entender y de programar ya
que son iterativos, simples ciclos y sentencias que hacenque el vector pueda ser ordenado. Dentro de los
Algoritmos iterativos encontramos:

Burbuja
Inserción
Selección
.

Ordenamiento por inserción
Consta de tomar uno por uno los elementos de un
arreglo y recorrerlo hacia su posición con respecto a
los anteriormente ordenados. Así empieza con el
segundo elemento y lo ordena con respecto al
primero. Luego sigue con el tercero y lo coloca ensu
posición ordenada con respecto a los dos anteriores,
así sucesivamente hasta recorrer todas las
posiciones del arreglo.
El orden de complejidad es de O(n2) y cuando los datos
se encuentran mas ordenados la complejidad es
O(n).

Ordenamiento por inserción

Ordenamiento por Selección
Consiste en encontrar el menor de todos los
elementos del arreglo e intercambiarlo con el que
estáen la primera posición. Luego el segundo más
pequeño, y así sucesivamente hasta ordenar todo
el arreglo.
El orden de complejidad siempre es de O(n2).

Ordenamiento de la Burbuja
Prácticamente lo que hace es tomar el elemento mayor y lo va recorriendo
de posición en posición hasta ponerlo en su lugar.
Se llama de la burbuja porque los elementos flotan hasta su posición
correcta como loharían las burbujas de una bebida gaseosa.
El orden de complejidad es de O(n2) y cuando los datos se encuentran
mas ordenados la complejidad es O(n).

Método de Burbuja

2. Algoritmos Recursivos.
Estos métodos son aun mas complejos,
requieren de mayor atención y conocimiento
para ser entendidos. Son rápidos y efectivos,
utilizan generalmente la técnica Divide y
vencerás, que consisteen dividir un
problema grande en varios pequeños para
que sea mas fácil resolverlos.
Mediante llamadas recursivas a si mismos, es
posible que el tiempo de ejecución y de
ordenación sea mas optimo.
Ordenamiento Rápido (Quicksort)
 Ordenamiento por Mezclas (Merge)


Ordenamiento rápido (Quicksort)
La idea básica del algoritmo es elegir un elemento llamado pivote, y
ejecutar unasecuencia de intercambios tal que todos los
elementos menores que el pivote queden a la izquierda y todos
los mayores a la derecha.
Lo único que requiere este proceso es que todos los elementos a la
izquierda sean menores que el pivote y que todos los de la
derecha sean mayores luego de cada paso, no importando el
orden entre ellos, siendo precisamente esta flexibilidad la que
hace eficiente alproceso. Hacemos dos búsquedas, una desde la
izquierda y otra desde la derecha, comparando el pivote con los
elementos que vamos recorriendo, buscando
los menores o iguales y los mayores respectivamente.
El orden de complejidad es de O(n log n) En el peor caso O(n2)

Ordenamiento rápido (Quicksort)
En la siguiente figura podemos ver como funciona:

Ventajas y Desventajas del (Quicksort)Ventajas:
 Muy Rápido
 No requiere de memoria adicional
Desventajas:
 Implementación un poco mas complicada
 Recursividad (utiliza Muchos recursos)

Ordenamiento rápido (Quicksort)
En la siguiente figura podemos ver como funciona:

4
3
1
Izq

5
2

6

1

2
Izq

7

3
Izq

7
1

4
Izq
Der

5
3

5

6

7

Der

Der

Der

Nótese los índices Izq...