Metodos De Ordenamiento Y Busqueda
Páginas: 13 (3029 palabras)
Publicado: 21 de septiembre de 2012
MÉTODOS DE ORDENAMIENTO Y DE BUSQUEDA
1. ¿QUÉ ES ORDENAMIENTO?
Generalmente, se considera ordenar (clasificar) el proceso de reorganización de un conjunto dado de objetos en una secuencia especificada. El objetivo de este proceso es facilitar la búsqueda posterior de los elementos del conjunto ordenado. La búsqueda de información es una operación básica en el proceso de datos, de ahí quepor extensión, la ordenación se convierta también en una actividad fundamental en dicho procesamiento de datos.
El tema de la ordenación es idóneo para mostrar como los problemas se pueden resolver utilizando una gran variedad de algoritmos, todos con el mismo objetivo, pero cada uno presentando ciertas ventajas sobre los otros. Resulta un tema interesante para enfatizar la necesidad deanalizar el funcionamiento de los algoritmos. 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.
Normalmente, la función de ordenación viene explícitamente reflejada en los objetos a ordenar como un campo de información más sobre cada elemento. De maneraque, en general, cada elemento del conjunto tendrá más de un campo de información (estructura de registro) y uno de esos campos indicará como se clasifican los elementos. El campo que especifica la relación de orden recibe el nombre de clave. El problema de la clasificación consiste entonces en ordenar una secuencia de registros de manera que sus claves formen una cadena no decreciente.
¿Cuándoconviene usar un método de ordenamiento?
Cuando se requiere hacer una cantidad considerable de búsquedas y es importante el tiempo.
1. 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 serequiere 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).
2. EFICIENCIA EN TIEMPODE 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 Internos:
← Inserción directa.
← Inserción binaria.
← Intercambio directo.
← Shake.
← Shell.
← Ordenamiento de árbol.
← Heap.
←Tournament.
← Sort particionado.
← Burbuja
← Quick sort.
← Merge sort.
← Radix sort.
← Cálculo de dirección.
3.- CLASIFICACIÓN DE LOS ALGORITMOS DE ORDENAMIENTO DE INFORMACIÓN:
El hecho de que la información está ordenada, nos sirve para poder encontrarla y accesarla de manera más eficiente ya que de lo contrario se tendría que hacer de manera secuencial.
Acontinuación se describirán 4 grupos de algoritmos para ordenar información:
a) Algoritmos de inserción:
En este tipo de algoritmo los elementos que van a ser ordenados son considerados uno a la vez. Cada elemento es INSERTADO en la posición apropiada con respecto al resto de los elementos ya ordenados.
Entre estos algoritmos se encuentran el de INSERCION DIRECTA, SHELL SORT, INSERCION BINARIA y...
1. ¿QUÉ ES ORDENAMIENTO?
Generalmente, se considera ordenar (clasificar) el proceso de reorganización de un conjunto dado de objetos en una secuencia especificada. El objetivo de este proceso es facilitar la búsqueda posterior de los elementos del conjunto ordenado. La búsqueda de información es una operación básica en el proceso de datos, de ahí quepor extensión, la ordenación se convierta también en una actividad fundamental en dicho procesamiento de datos.
El tema de la ordenación es idóneo para mostrar como los problemas se pueden resolver utilizando una gran variedad de algoritmos, todos con el mismo objetivo, pero cada uno presentando ciertas ventajas sobre los otros. Resulta un tema interesante para enfatizar la necesidad deanalizar el funcionamiento de los algoritmos. 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.
Normalmente, la función de ordenación viene explícitamente reflejada en los objetos a ordenar como un campo de información más sobre cada elemento. De maneraque, en general, cada elemento del conjunto tendrá más de un campo de información (estructura de registro) y uno de esos campos indicará como se clasifican los elementos. El campo que especifica la relación de orden recibe el nombre de clave. El problema de la clasificación consiste entonces en ordenar una secuencia de registros de manera que sus claves formen una cadena no decreciente.
¿Cuándoconviene usar un método de ordenamiento?
Cuando se requiere hacer una cantidad considerable de búsquedas y es importante el tiempo.
1. 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 serequiere 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).
2. EFICIENCIA EN TIEMPODE 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 Internos:
← Inserción directa.
← Inserción binaria.
← Intercambio directo.
← Shake.
← Shell.
← Ordenamiento de árbol.
← Heap.
←Tournament.
← Sort particionado.
← Burbuja
← Quick sort.
← Merge sort.
← Radix sort.
← Cálculo de dirección.
3.- CLASIFICACIÓN DE LOS ALGORITMOS DE ORDENAMIENTO DE INFORMACIÓN:
El hecho de que la información está ordenada, nos sirve para poder encontrarla y accesarla de manera más eficiente ya que de lo contrario se tendría que hacer de manera secuencial.
Acontinuación se describirán 4 grupos de algoritmos para ordenar información:
a) Algoritmos de inserción:
En este tipo de algoritmo los elementos que van a ser ordenados son considerados uno a la vez. Cada elemento es INSERTADO en la posición apropiada con respecto al resto de los elementos ya ordenados.
Entre estos algoritmos se encuentran el de INSERCION DIRECTA, SHELL SORT, INSERCION BINARIA y...
Leer documento completo
Regístrate para leer el documento completo.