Métodos de ordenamiento
Páginas: 6 (1253 palabras)
Publicado: 6 de marzo de 2014
Métodos de ordenamiento
La importancia del orden
Desde hace muchos años se conoce la importancia de guardar información y recuperarla. Hoy, gracias a los sistemas de cómputo, pueden almacenarse grandes cantidades de información, por lo que se hace necesario contar con medios eficaces para hallar la que es de utilidad cuando ésta es requerida. Los métodos de ordenamiento mantienen el controlde tus datos para que sea más fácil y rápido el acceso a ellos. Para esto existen varios métodos los cuales elegiremos de acuerdo a dos factores con respecto a ¿Qué se desea optimizar?: Espacio en memoria o El tiempo de ejecución, para ello existen principalmente dos tipos de ordenamiento:
Interno: Es el tipo de ordenamiento en el cual los datos a ordenar están localizados en la memoria principalde la computadora.
Externo: Existe cuando los datos a ordenar están localizados en algún dispositivo externo.
Por ordenación de archivos se entiende, entonces, la ordenación o clasificación de éstos, ascendente o descendentemente, de acuerdo con un campo determinado al que se denominará campo clave.
Complejidad
Cada algoritmo de ordenamiento por definición tiene operaciones y cálculosmínimos y máximos que realiza (complejidad), entre mas comparaciones e intercambios mas complejo es el algoritmo.
Ordenamiento interno
Los métodos de ordenamiento interno trabajan en memoria principal y sus implementaciones son muy variadas, de manera que la elección del algoritmo adecuado debe realizarse con criterios de eficiencia (tiempo y ejecución) y en función de la memoria disponible.Dividiremos los métodos en dos grandes grupos:
Directos (burbuja, selección e inserción).
Logarítmicos (Shell sort, Merge sort, Heap sort, Quick sort, Radix).
En el caso de listas pequeñas, los métodos directos se desempeñan de manera relativamente eficientes, ya que la codificación del algoritmo correspondiente no es compleja. Su uso es muy frecuente. Sin embargo, en arreglos grandes lasordenaciones directas resultan ineficientes y se necesitara un método logarítmico para su solución.
Ordenamiento externo
La ordenación de archivos se lleva a cabo cuando el volumen de los datos a tratar es demasiado grande y los mismos no caben en la memoria principal de la computadora. Al ocurrir esta situación no pueden aplicarse los métodos de ordenación interna, de modo que debe pensarse en otrotipo de algoritmos para ordenar datos almacenados en archivos.
Métodos de ordenamiento interno
1. Burbuja
La idea básica de este método de ordenamiento es la de comparar pares de valores de llaves e intercambiarlos si no están en sus posiciones relativas correctas.
1. Comparar el primer y segundo elemento, intercambiarlos si el primero es mayor que el segundo; luego se compara el primero conel tercero, intercambiándose en caso necesario, y el proceso se repite hasta llegar al último elemento. De este modo, tras la primera iteración la casilla primera conservara el elemento más pequeño de esa iteración.
2. Se repite el paso anterior, pero ahora con el segundo y tercero, en caso de ser necesario se intercambian, y así hasta llegar a comparar el segundo con el ultimo. N-1 iteraciones2. Burbuja mejorado
Es un versión mejorada del algoritmo de burbuja en donde se integra una variable que funge como switch (bandera) que permite detectar el momento en que ya no se presenten mas intercambios aunque su mejora no suele ser tan importante pues el algoritmo sigue comportándose como una ordenación de n-1.
3. Selección directa
La idea básica es encontrar el elemento máspequeño (grande), en orden ascendente de la lista, e intercambiarlo con el elemento que ocupa la primera posición en la lista, a continuación se busca el siguiente elemento más pequeño y se transfiere a la segunda posición. Se repite el proceso hasta que el último elemento ha sido transferido a su posición correcta.
En el primer paso del ordenamiento se efectúan n-1 comparaciones, en el...
La importancia del orden
Desde hace muchos años se conoce la importancia de guardar información y recuperarla. Hoy, gracias a los sistemas de cómputo, pueden almacenarse grandes cantidades de información, por lo que se hace necesario contar con medios eficaces para hallar la que es de utilidad cuando ésta es requerida. Los métodos de ordenamiento mantienen el controlde tus datos para que sea más fácil y rápido el acceso a ellos. Para esto existen varios métodos los cuales elegiremos de acuerdo a dos factores con respecto a ¿Qué se desea optimizar?: Espacio en memoria o El tiempo de ejecución, para ello existen principalmente dos tipos de ordenamiento:
Interno: Es el tipo de ordenamiento en el cual los datos a ordenar están localizados en la memoria principalde la computadora.
Externo: Existe cuando los datos a ordenar están localizados en algún dispositivo externo.
Por ordenación de archivos se entiende, entonces, la ordenación o clasificación de éstos, ascendente o descendentemente, de acuerdo con un campo determinado al que se denominará campo clave.
Complejidad
Cada algoritmo de ordenamiento por definición tiene operaciones y cálculosmínimos y máximos que realiza (complejidad), entre mas comparaciones e intercambios mas complejo es el algoritmo.
Ordenamiento interno
Los métodos de ordenamiento interno trabajan en memoria principal y sus implementaciones son muy variadas, de manera que la elección del algoritmo adecuado debe realizarse con criterios de eficiencia (tiempo y ejecución) y en función de la memoria disponible.Dividiremos los métodos en dos grandes grupos:
Directos (burbuja, selección e inserción).
Logarítmicos (Shell sort, Merge sort, Heap sort, Quick sort, Radix).
En el caso de listas pequeñas, los métodos directos se desempeñan de manera relativamente eficientes, ya que la codificación del algoritmo correspondiente no es compleja. Su uso es muy frecuente. Sin embargo, en arreglos grandes lasordenaciones directas resultan ineficientes y se necesitara un método logarítmico para su solución.
Ordenamiento externo
La ordenación de archivos se lleva a cabo cuando el volumen de los datos a tratar es demasiado grande y los mismos no caben en la memoria principal de la computadora. Al ocurrir esta situación no pueden aplicarse los métodos de ordenación interna, de modo que debe pensarse en otrotipo de algoritmos para ordenar datos almacenados en archivos.
Métodos de ordenamiento interno
1. Burbuja
La idea básica de este método de ordenamiento es la de comparar pares de valores de llaves e intercambiarlos si no están en sus posiciones relativas correctas.
1. Comparar el primer y segundo elemento, intercambiarlos si el primero es mayor que el segundo; luego se compara el primero conel tercero, intercambiándose en caso necesario, y el proceso se repite hasta llegar al último elemento. De este modo, tras la primera iteración la casilla primera conservara el elemento más pequeño de esa iteración.
2. Se repite el paso anterior, pero ahora con el segundo y tercero, en caso de ser necesario se intercambian, y así hasta llegar a comparar el segundo con el ultimo. N-1 iteraciones2. Burbuja mejorado
Es un versión mejorada del algoritmo de burbuja en donde se integra una variable que funge como switch (bandera) que permite detectar el momento en que ya no se presenten mas intercambios aunque su mejora no suele ser tan importante pues el algoritmo sigue comportándose como una ordenación de n-1.
3. Selección directa
La idea básica es encontrar el elemento máspequeño (grande), en orden ascendente de la lista, e intercambiarlo con el elemento que ocupa la primera posición en la lista, a continuación se busca el siguiente elemento más pequeño y se transfiere a la segunda posición. Se repite el proceso hasta que el último elemento ha sido transferido a su posición correcta.
En el primer paso del ordenamiento se efectúan n-1 comparaciones, en el...
Leer documento completo
Regístrate para leer el documento completo.