Computacion Metodo De Ordenamiento 576jm

¿Qué es ordenamiento? Es la operación de arreglar los registros de una tabla en algún orden secuencial 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 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). Algoritmos de ordenamiento: Internos:

Inserción directa. Inserción binaria. Inserción directa. Selección directa. Selección directa. Burbuja. Shake. Intercambio directo. Shell. Inserción disminución incremental. Heap. Tournament. Ordenamiento de árbol. Quick sort. Sort particionado. Merge sort. Radix sort.

Cálculo de dirección. Externos: Straight merging. Natural merging. Balanced multiway merging. Polyphase sort. Distribution of initial runs. 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. A continuación se describirán 4 grupos de algoritmos para ordenar información: 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 HASHING. Algoritmos de intercambio: En este tipo de algoritmos se toman los elementos de dos en dos, se comparan y se INTERCAMBIAN si no están en el orden adecuado. Este proceso se repite hasta que se ha analizado todo el conjunto de elementos y ya no hay intercambios. Entre estos algoritmos se encuentran el BURBUJA y QUICK SORT

Algoritmos de selección: En este tipo de algoritmos se SELECCIONA o se busca el elemento más pequeño (o más grande) de todo el conjunto de elementos y se coloca en su posición adecuada. Este proceso se repite para el resto de los elementos hasta

que

todos

son

analizados.

Entre estos algoritmos se encuentra el de SELECCION DIRECTA. Algoritmos de enumeración: En este tipo de algoritmos cada elemento es comparado contra los demás. En la comparación se cuenta cuántos elementos son más pequeños que el elemento que se está analizando, generando así una ENUMERACION. El número generado para cada elemento indicará su posición. Los métodos simples son: Inserción (o por inserción directa), selección, burbuja y shell, en dónde el último es una extensión al método de inserción, siendo más rápido. Los métodos más complejos son el quick-sort (ordenación rápida) y el heap sort.

Métodos de Ordenación Un método de ordenamiento consiste en un algoritmo que recibe como entrada a un conjunto de datos que son necesarios de ordenar según cierto(s) criterio(s). El objetivo fundamental de éstos métodos es el de facilitar la búsqueda de datos según estos mismos criterios. Muchas veces es necesario además de buscar elementos dentro de en un vector, ordenarlos. Este ordenamiento puede ser de mayor a menor si estamos manejando números y en orden alfabético si se trata de nombres o caracteres. Existe una gran variedad de métodos de ordenamiento que nos permiten organizar con rapidez los elementos que se encuentran dentro de

un vector o archivo. La elección de un determinado método de ordenamiento depende del tamaño del vector que se desea ordenar Métodos de Ordenación Elementales Los métodos de ordenación elementales proporcionan: 

Una terminología básica.



Un mecanismo básico que puede extenderse a otros métodos más generales, sofisticados y con mejor desempeño. Típicamente, los métodos de ordenación elementales tienen peor

desempeño que los sofisticados, pero existen muchas aplicaciones en las que es mejor utilizar un método de ordenación elemental. Por ejemplo, cuando el algoritmo se utiliza pocas veces y/o se ordenan pocos elementos. Como regla general se tiene que los métodos elementales necesitan cerca de

pasos para ordenar

elementos organizados al azar.

En general, no se recomienda su uso para ordenar: 

Archivos grandes.



Archivos clasificados aleatoriamente. Por su parte, métodos más avanzados pueden lograr desempeños de

orden

,

,

. Más aún, se puede demostrar que ningún método de

ordenación puede utilizar menos de

comparaciones entre claves

cuando éstas están organizadas al azar. Terminología En el contexto de los métodos de ordenación, cada elemento de dato tiene su clave, y los métodos de ordenación trabajan ordenando los elementos de dato según sus claves. Por lo regular, los métodos comparan

las claves e intercambian los elementos de dato. En lugar de desplazar físicamente los elementos de datos, con frecuencia, sólo se intercambian índices, punteros o referencias. Esto se denomina ordenación indirecta. Un método de ordenación que trabaja sobre un conjunto de datos que se encuentra en memoria (e.g., un arreglo, una lista) se dice que es un método de ordenación interna. Por el contrario, si el conjunto de datos almacenados en archivos no pueden ser cargados en memoria (por ejemplo, por razones de tamaño) y el método de ordenación opera sobre los archivos, se dice que es de ordenación externa. Evidentemente, en la ordenación interna se accede a los elementos de dato más fácilmente, mientras que en la ordenación externa se accede a los elementos de dato de forma secuencial o al menos en grades bloques. Los métodos de ordenación se pueden clasificar de acuerdo a sus requerimientos de memoria. Los métodos in situ son aquellos que requieren ninguna o muy poca memoria extra. En el otro extremo, existen métodos que requieren mucha memoria extra. Una característica que puede ser importante es la estabilidad del método de ordenación. Un algoritmo de ordenación es estable si elementos de dato con la misma clave conservan su orden relativo luego de su aplicación. Típicamente, los métodos elementales son estables mientras que la mayoría de los algoritmos sofisticados no lo son. Entre los métodos de ordenación elementales están Selección e Inserción, los cuales son descritos a continuación: Método de Ordenación por Selección El método de ordenamiento por selección consiste en encontrar el menor de todos los elementos del arreglo e intercambiarlo con el que está en la primera posición. Luego el segundo más pequeño, y así sucesivamente hasta ordenar todo el arreglo.

Procedimiento Selection Sort Paso 1: [Para cada pos. del arreglo] For i <- 1 to N do Paso 2: [Inicializa la pos. del menor] menor <- i Paso 3: [Recorre todo el arreglo] For j <- i+1 to N do Paso 4: [Si a[j] es menor] If a[j] < a[menor] then Paso 5: [Reasigna el apuntador al menor] min = j Paso 6: [Intercambia los datos de la pos. min y posición i] Swap(a, min, j). Paso 7: [Fin] End. Ejemplo: El arreglo a ordenar es a = ['a','s','o','r','t','i','n','g','e','x','a','m','p','l','e']. Se empieza por recorrer el arreglo hasta encontrar el menor elemento. En este caso el menor elemento es la primera 'a'. De manera que no ocurre ningún cambio. Luego se procede a buscar el siguiente elemento y se encuentra la segunda 'a'. Esta se intercambia con el dato que está en la segunda posición, la 's', quedando

el

arreglo

así

después

de

dos

recorridos:

a

=

['a','a','o','r','t','i','n','g','e','x','s','m','p','l','e']. El siguiente elemento, el tercero en orden de menor mayor es la primera 'e', la cual se intercambia con lo que está en la tercera posición, o sea, la 'o'. Le sigue la segunda 's', la cual es intercambiada con la 'r'. El arreglo ahora se ve de la siguiente manera: a = ['a','a','e','e','t','i','n','g','o','x','s','m','p','l','r']. De esta manera se va buscando el elemento que debe ir en la siguiente posición hasta ordenar todo el arreglo. El número de comparaciones que realiza este algoritmo es:

Para el primer elemento se comparan n-1 datos, en general para el elemento i-ésimo se hacen n-i comparaciones, por lo tanto, el total de comparaciones es: la sumatoria para i de 1 a n-1 (n-i) = 1/2 n (n-1). El algoritmo de ordenación por selección de una lista tiene los siguientes pasos: 1. Encontrar el mayor elemento de la lista 2. Intercambiar el mayor elemento con el elemento del subíndice 1 3. A continuación se busca el mayor elemento en la sublista de subíndices de 2 hasta n y se intercambia con el elemento de subíndice 2; por consiguiente, se sitúa el segundo elemento mayor en la posición 2 4. A continuación se busca el elemento mayor en la sublista de 3 hasta n, y así sucesivamente. Ordenamiento por selección en forma descendente for i:= 1 to N-1 do for j:= i+1 to N do if v[ i ] < v[ j ] then begin aux := v[ j ]; v[ j ] := v[ i ]; v[ i ] := aux; end; Si desea realizar el ordenamiento de forma ascendente, se sigue el mismo criterio pero en lugar de intercambiar al encontrar un mayor

se

intercambia al encontrar un menor. Esto se traduce en cambiar la condición de > a <. El método descrito anteriormente realiza cambios cada vez que encuentra un elemento menor o mayor según sea el caso.

Esto puede

mejorarse

al realizar un solo cambio, después de haber determinado el

mayor / menor elemento y su posición.

A continuación se presenta una corrida en frío del algoritmo a fin de observar el movimiento de los valores en el arreglo hasta quedar ordenados. que se intercambia una sola vez por cada iteración.

Note

Los elementos a

reubicarse están indicados con las flechas, el elemento resaltado indica la posición del índice.

Supongamos que tenemos un arreglo con los datos, entonces el procedimiento es como sigue: 1. Se sitúa en el primer elemento (i=0). 2. Se busca el elemento más pequeño de arreglo (desde i hasta el final). 3. Se intercambia el elemento más pequeño con el que está en la posición i. 4. Se incrementa i (i++). Nótese que se gasta la mayor parte del tiempo en intentar en encontrar el elemento mínimo.

A continuación se presenta una implementación en Java del método de ordenación por selección: /** * Clase que implementa métodos de ordenación elementales. */ public class Sorting { static public void selectionSort(Comparable array[]) { // No se incluye validación de parámetro de entrada. int min; for (int i = 0; i < array.length; i++) { min = i; for (int j = i + 1; j < array.length; j++) { if (array[j].compareTo(array[min]) < 0) { min = j; } Sort.swap(array, min, i); } } private static void swap(Comparable[] array, int i, int j) { Comparable tmp = array[i]; array[i] = array[j]; array[j] = tmp;

El método de ordenación por selección: 1. Está basado en el enfoque de fuerza bruta. 2. Funciona bien con archivos pequeños. 3. Cada elemento se mueve sólo una vez. Método de Ordenación por Inserción Este método toma cada elemento del arreglo para ser ordenado y lo compara con los que se encuentran en posiciones anteriores a la de él dentro del arreglo. Si resulta que el elemento con el que se está comparando es mayor que el elemento a ordenar, se recorre hacia la siguiente posición superior. Si por el contrario, resulta que el elemento con el que se está comparando es menor que el elemento a ordenar, se detiene el proceso de comparación pues se encontró que el elemento ya está ordenado y se coloca en su posición (que es la siguiente a la del último número con el que se comparó). Procedimiento Insertion Sort Este procedimiento recibe el arreglo de datos a ordenar a[] y altera las posiciones de sus elementos hasta dejarlos ordenados de menor a mayor. N representa el número de elementos que contiene a[]. Paso 1: [Para cada pos. del arreglo] For i <- 2 to N do Paso 2: [Inicializa v y j] v <- a[i] j <- i. Paso 3: [Compara v con los anteriores] While a[j-1] > v AND j>1 do Paso 4: [Recorre los datos mayores] Set a[j] <- a[j-1], Paso 5: [Decrementa j] set j <- j-1. Paso 6: [Inserta v en su posición] Set a[j] <- v. Paso 7: [Fin] End.

Ejemplo: Si el arreglo a ordenar es a = ['a','s','o','r','t','i','n','g','e','x','a','m','p','l','e'], el algoritmo va a recorrer el arreglo de izquierda a derecha. Primero toma el segundo dato 's' y lo asigna a v y i toma el valor de la posición actual de v. Luego compara esta 's' con lo que hay en la posición j-1, es decir, con 'a'. Debido a que 's' no es menor que 'a' no sucede nada y avanza i. Ahora v toma el valor 'o' y lo compara con 's', como es menor recorre a la 's' a la posición de la 'o'; decrementa j, la cual ahora tiene la posición en dónde estaba la 's'; compara a 'o' con a [j-1], es decir, con 'a'. Como no es menor que la 'a' sale del for y pone la 'o' en la posición a[j]. El resultado hasta este punto es el arreglo siguiente: a = ['a','o','s','r',....] Así se continúa y el resultado final es el arreglo ordenado: a = ['a','a','e','e','g','i','l','m','n','o','p','r','s','t','x'] Considere que los elementos están uno tras otro, el método consiste en insertar cada elemento en el lugar apropiado entre los elementos que ya han sido considerado (manteniéndolos ordenados). Es similar a la forma en que se ordena un juego de cartas. Por ejemplo: EJEMPLOAORDENAR EJ EJE EEJM EEJMP EEJMPL E E J L M P ...

A continuación se muestra una implementación en Java del método de ordenación por inserción: static public void insertionSort(Comparable array[]) { // No se incluye validación de parámetro de entrada. int min; for (int i = 1; i < array.length; i++) { Comparable tmp = array[i]; int j; for (j = i; j > 0 && tmp.compareTo(array[j-1]) < 0; j--) { array[j] = array[j-1]; } array[j] = tmp; Características de Rendimiento de los Métodos de Ordenación Elementales 

La simple inspección de las implementaciones anteriores sirve de evidencia de que los métodos elementales son cuadráticos (tanto en el peor caso como en el caso medio) y no necesitan memoria extra (in situ).



La

ordenación

aproximadamente número

de

comparaciones comparaciones

por selección utiliza y

intercambios. está

por: Si

entonces el número de comparaciones es igual a

El dado

Por otra parte, puede haber máximo

intercambios. Estos

resultados son independientes del conjuntos de datos de entrada, entonces se dice que el método de selección es insensible a los datos de entrada. 

La

ordenación

aproximadamente

por inserción utiliza

comparaciones y

intercambios en el

caso medio y dos veces más en el peor caso ( y

comparaciones

intercambios). Nótese que cuando el archivo está ordenado la

ordenación por inserción es lineal (

).

Muchas veces se abusa de los métodos de ordenación de propósito general, en especial en estos casos donde el método de inserción

supera

a

los

métodos

sofisticados.

Por

ejemplo,

supongamos que se desea añadir algunos elementos a una lista ordenada para obtener una lista ordenada más grande. Para ello: 1. Añada los nuevos elementos al final del archivo. 2. Llame al método de ordenación por inserción. 

Se puede demostrar que cualquier algoritmo de ordenación que intercambie elementos adyacentes tiene un tiempo de ejecución promedio

(cota inferior).

Conclusión

El Ordenamiento es la operación de arreglar los registros de una tabla en algún orden secuencial de acuerdo a un criterio de ordenamiento, se puede decir que el propósito principal de un ordenamiento es el de facilitar las búsquedas de los del conjunto ordenado y para realizar este ordenamiento existen varias métodos los cuales consisten en un algoritmo que recibe como entrada a un conjunto de datos que son necesarios de ordenar según cierto(s) criterio(s). El objetivo fundamental de éstos métodos es el de facilitar la búsqueda de datos según estos mismos criterios. Entre los métodos están por Selección y por Inserción. El método de ordenación por selección tiene como función principal encontrar el menor de todos los elementos del arreglo e intercambiarlo con el que está en la primera posición; mientras que el método por inserción consiste en tomar cada elemento del arreglo para ser ordenado y lo compara con los que se encuentran en posiciones anteriores a la de él dentro del arreglo.