No Se
Páginas: 11 (2549 palabras)
Publicado: 16 de mayo de 2012
MÉTODOS DE ORDENACIÓN
CLASE N°3
Leissi M. Castañeda León lcl@upnorte.edu.pe https://sites.google.com/site/leissicl/
Que veremos hoy?
1. 2.
Introducción Ordenación Interna
Ordenación por intercambio directo (Burbuja) Ordenación por el método de intercambio directo con señal Ordenación por el método de la sacudida (shaker sort) Ordenación por inserción directa Ordenación por el método deinserción binaria Ordenación por selección directa Ordenación por el método de Shell Ordenación por el método QuickSort Ordenación por el método HeapSort (montículo)
3.
Ordenación Externa
2
Introducción
ORDENAR significa reagrupar o reorganizar un conjunto de datos u objetos en un secuencia específica. Los procesos de ordenación y búsqueda son frecuentes en nuestra vida. Vivimos en unmundo desarrollado, automatizado, acelerado, donde la información representa un elemento de vital importancia. Los objetos ordenado aparecen por doquier: Directorio telefónico, registros de pacientes de un hospital, registros de huéspedes de un hotel, listados de alumnos en una clase, índice de libros en una biblioteca, etc.; son tan sólo algunos ejemplos.
3
Introducción
¿Cuándo esconviente usar un método de ordenación? Rpta: Cuando se requiere hacer una cantidad considerable de búsquedas y es importante el factor tiempo. Imagine que ocurriría si se deseara encontrar un libro en una biblioteca con más de 100 000 volúmenes y éstos estuvieran desordenados o registrados en el orden en el que fueron reciibidos.
4
Ordenación
Formalmente se define ordenación de la siguientemanera: Sea A una lista de N elementos: A1, A2, A3,..., AN Ordenar significa permutar estos elementos de tal forma que los mismos queden de acuerdo con una distribución preestablecida.
Ascendente: A1 ≤ A2 ≤ A3 ≤ … ≤ AN Descendente: A1 ≥ A2 ≥ A3 ≥ ... ≥ AN
5
Ordenación
En el procesamiento de datos, a los métodos de ordenación se les clasifica en dos grandes categorías, según donde hayan sidoalmacenados:
Ordenación de arreglos Ordenación de archivos
La primera categoría se denomina también ordenación interna (dado que los elementos del arreglo se encuentran en memoria principal) y la segunda ordenación externa (dado que los elementos se encuentra en archivos almacenados en dispositivos de almacenamiento secundario, como: discos, cintas, etc.)
6
Analogía con la vida real:
Sepodría decir que para la máquina: Ordenación Interna: representa lo que para un humano significa ordenar un conjunto de cartas que se encuentran todas visibles y extendidas sobre la mesa. Ordenación Externa: representa lo que para un humano significa ordenar cartas que están dispuestas una debajo otra y en donde sólo se visualiza la primera.
7
2. Ordenación Interna
8
Ordenación InternaSe explicarán con arreglos unidimensionales, pero su uso puede extenderse a otros tipos de arreglos y estructuras de datos. Dentro de la ordenación interna los métodos se clasifican en dos tipos:
Métodos directos: tienen la característica de que su implementación es relativamente sencilla y de fácil comprensión, aunque son ineficientes cuando N (el número de elementos del arreglo) es medio ogrande. Métodos logarítmicos: son más complejos que los directos. Su elaboración es más sofisticada y, al ser menos intuitivo (más abstracta), resultan más difíciles de entender. Pero son más eficientes cuando el número de elementos es medio o grande.
9
Ordenación Interna
Notar que la eficiencia entre los distintos métodos va estar dada por el tiempo de ejecución (depende del número decomparaciones y movimientos). Los métodos directos más conocidos son:
Ordenación por intercambio Ordenación por inserción Ordenación por selección
10
2.1. Ordenación por intercambio directo (Burbuja)
11
Ordenación por intercambio directo (Burbuja)
Es el más utilizado entre los estudiantes principiantes de computación por su fácil comprensión y programación. Se podría señalar que es...
CLASE N°3
Leissi M. Castañeda León lcl@upnorte.edu.pe https://sites.google.com/site/leissicl/
Que veremos hoy?
1. 2.
Introducción Ordenación Interna
Ordenación por intercambio directo (Burbuja) Ordenación por el método de intercambio directo con señal Ordenación por el método de la sacudida (shaker sort) Ordenación por inserción directa Ordenación por el método deinserción binaria Ordenación por selección directa Ordenación por el método de Shell Ordenación por el método QuickSort Ordenación por el método HeapSort (montículo)
3.
Ordenación Externa
2
Introducción
ORDENAR significa reagrupar o reorganizar un conjunto de datos u objetos en un secuencia específica. Los procesos de ordenación y búsqueda son frecuentes en nuestra vida. Vivimos en unmundo desarrollado, automatizado, acelerado, donde la información representa un elemento de vital importancia. Los objetos ordenado aparecen por doquier: Directorio telefónico, registros de pacientes de un hospital, registros de huéspedes de un hotel, listados de alumnos en una clase, índice de libros en una biblioteca, etc.; son tan sólo algunos ejemplos.
3
Introducción
¿Cuándo esconviente usar un método de ordenación? Rpta: Cuando se requiere hacer una cantidad considerable de búsquedas y es importante el factor tiempo. Imagine que ocurriría si se deseara encontrar un libro en una biblioteca con más de 100 000 volúmenes y éstos estuvieran desordenados o registrados en el orden en el que fueron reciibidos.
4
Ordenación
Formalmente se define ordenación de la siguientemanera: Sea A una lista de N elementos: A1, A2, A3,..., AN Ordenar significa permutar estos elementos de tal forma que los mismos queden de acuerdo con una distribución preestablecida.
Ascendente: A1 ≤ A2 ≤ A3 ≤ … ≤ AN Descendente: A1 ≥ A2 ≥ A3 ≥ ... ≥ AN
5
Ordenación
En el procesamiento de datos, a los métodos de ordenación se les clasifica en dos grandes categorías, según donde hayan sidoalmacenados:
Ordenación de arreglos Ordenación de archivos
La primera categoría se denomina también ordenación interna (dado que los elementos del arreglo se encuentran en memoria principal) y la segunda ordenación externa (dado que los elementos se encuentra en archivos almacenados en dispositivos de almacenamiento secundario, como: discos, cintas, etc.)
6
Analogía con la vida real:
Sepodría decir que para la máquina: Ordenación Interna: representa lo que para un humano significa ordenar un conjunto de cartas que se encuentran todas visibles y extendidas sobre la mesa. Ordenación Externa: representa lo que para un humano significa ordenar cartas que están dispuestas una debajo otra y en donde sólo se visualiza la primera.
7
2. Ordenación Interna
8
Ordenación InternaSe explicarán con arreglos unidimensionales, pero su uso puede extenderse a otros tipos de arreglos y estructuras de datos. Dentro de la ordenación interna los métodos se clasifican en dos tipos:
Métodos directos: tienen la característica de que su implementación es relativamente sencilla y de fácil comprensión, aunque son ineficientes cuando N (el número de elementos del arreglo) es medio ogrande. Métodos logarítmicos: son más complejos que los directos. Su elaboración es más sofisticada y, al ser menos intuitivo (más abstracta), resultan más difíciles de entender. Pero son más eficientes cuando el número de elementos es medio o grande.
9
Ordenación Interna
Notar que la eficiencia entre los distintos métodos va estar dada por el tiempo de ejecución (depende del número decomparaciones y movimientos). Los métodos directos más conocidos son:
Ordenación por intercambio Ordenación por inserción Ordenación por selección
10
2.1. Ordenación por intercambio directo (Burbuja)
11
Ordenación por intercambio directo (Burbuja)
Es el más utilizado entre los estudiantes principiantes de computación por su fácil comprensión y programación. Se podría señalar que es...
Leer documento completo
Regístrate para leer el documento completo.