- Qué es ordenamiento? Tipos de ordenamientos. Internos y externos. Eficiencia en tiempo de ejecuecuencial de acuerdo a un criterio de ordenamiento.
El ordenamiento se efectúa con base en el valor de algún campo en un registro.
El propósito principal de un ordenamiento es el de facilitar las búsquedas de los miembros del conjunto ordenado.
Ej. de ordenamientos:
Dir. telefónico, tablas de contenido, bibliotecas y diccionarios, etc.
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.
¿Cuándo conviene usar un método de ordenamiento?
Cuando se requiere hacer una cantidad considerable de búsquedas y es importante el factor tiempo.
Tipos de ordenamientos:
Los 2 tipos de ordenamientos que se pueden realizar son: los internos y los externos.
Los internos:
Son aquellos en los que los valores a ordenar están en memoria principal, por lo que se asume que el tiempo que se requiere para acceder cualquier elemento sea el mismo (a[1], a[500], etc).
Los externos:
Son aquellos en los que los valores a ordenar están en memoria secundaria (disco, cinta, cilindro magnético, etc), por lo que se asume que el tiempo que se requiere para acceder a cualquier elemento depende de la última posición accesada (posición 1, posición 500, etc).
Eficiencia en tiempo de ejecución:
Una medida de eficiencia es: Contar el # de comparaciones (C)
Contar el # de movimientos de items (M) Estos están en función de el #(n) de items a ser ordenados.
Un "buen algoritmo" de ordenamiento requiere de un orden nlogn comparaciones.
La eficiencia de los
algoritmos se mide por el número de comparaciones e intercambios que tienen que hacer, es decir, se toma n como el número de elementos que tiene el arreglo o vector a ordenar y se dice que un algoritmo realiza O(n2) comparaciones cuando compara n veces los n elementos, n x n = n2
Algoritmos de ordenamiento:
...
