Metodos de Ordenacion en c++




TRABAJO DE INVESTIGACION DE
Los Metodos de Ordenacion
de C++



Tacna – Perú
2013
Contenido



Métodos de Ordenación
Introducción:
Las tres operaciones muy importantes en programación de computadoras son: Ordenación, búsqueda y mezcla; son esenciales para un gran número de programas de proceso de datos y se estima que en estas operaciones las computadoras por término mediogastan gran parte de su tiempo.
Uno de los procesos más comunes y útiles en el proceso de datos, es la clasificación u ordenación de los mismos. Se considera ordenar al proceso de reorganizar un conjunto de objetos en una secuencia determinada.
Ordenar es simplemente colocar información de una manera espacial basándonos en un criterio de ordenamiento. En la computación el ordenamiento de datostambién cumple un rol muy importante, ya sea como un fin es si o como parte de otros procedimientos más complejos.
Ordenación:
La Ordenación o clasificación de datos es una operación consistente en disponer un conjunto (escritura) de datos en algún determinado orden con respecto a uno de los campos de elementos del conjunto. Por lo general, todos los algoritmos de ordenación funcionan de una formasimilar; toman una lista de elementos, en nuestro caso un array, comparan sus elementos siguiendo una estrategia definida y, según el resultado de dicha comparación los datos se mueven de un lugar a otro hasta conseguir una lista (array) final ordenado.
Una colección de datos (estructura) puede ser almacenada en un archivo, un array (vector o tabla), un array de registros, una lista enlazada oun árbol. Cuando los datos están almacenados enun array, una lista enlazada o un árbol, se denomina ordenación interna. Si los datos están almacenadosen un archivo, el proceso de ordenación se llama ordenación externa.
Una lista se dice que está ordenada por la clave k si la lista está en orden ascendente o descendente con respecto a esta clave. La lista se dice que está en orden ascendente si:
i< j implica que k[i] j implica que k[i] >= k[j]
para todos los elementos de la lista. Por ejemplo, para una guía telefónica, la lista está clasificada en orden ascendente por el campo clave k, donde k[i] es el nombre del abonado (apellidos, nombre).
4
5
14
21
32
45
orden ascendente
75
70
35
16
14
12
orden descendente
Zacarías
Rodríguez
Martínez
López
García
orden descendenteLos métodos (algoritmos) de ordenación son numerosos, por ello se debe prestar especial atención en su elección. ¿Cómo se sabe cuál es el mejor algoritmo? La eficiencia es el factor que mide la calidad y rendimiento de un algoritmo. En el caso de la operación de ordenación, dos criterios se suelen seguir a la hora de decidir qué algoritmo el más eficiente:
1) tiempo menor de ejecución encomputadora
2) menor número de instrucciones.
Sin embargo, no siempre es fácil efectuar estas medidas: puede no disponerse de instrucciones para medida de tiempo y las instrucciones pueden variar, dependiendo del lenguaje y del propio estilo del programador. Por esta razón, el mejor criterio para medir la eficiencia de un algoritmo es aislar una operación específica clave en la ordenación y contar elnúmero de vecesque se realiza. Así, en el caso de los algoritmos de ordenación, se utilizará como medida de su eficiencia el número de comparaciones entre elementos efectuados. El algoritmo de ordenación A será más eficiente que el B, si requiere menor número de comparaciones.
Así, en el caso de ordenar los elementos de un vector, el número de comparaciones será función delnúmero de elementos(n) del vector (array). Por consiguiente, se puede expresar el número de comparaciones en términos de n (por ejemplo, n+4, o bien n2en lugar de números enteros.
Los métodos de ordenación se suelen dividir en dos grandes grupos:
Directos burbuja, selección, inserción.
Indirectos(avanzados) Shell, ordenación rápida, ordenación por mezcla.
En el caso de listas pequeñas, los métodos directos se...