Martin Raymundo Herrera Medina

José Alfredo Vázquez Rosi les

Jordany Salazar Aparicio

ORDENAMIENTO EN LENGUAJE C

Programación

Benemérita Universidad Autónoma de Puebla

Facultad de ciencias de la electrónica

Su finalidad es organizar ciertos datos en un orden creciente o decreciente mediante una regla prefijada.

Atendiendo al tipo de elemento que se quiera ordenar puede ser:

Ordenación interna: Los datos se encuentran en memoria (ya sean arreglos, listas, etc.), y son de acceso aleatorio o directo.

Los métodos de ordenación interna se aplican principalmente a arreglos unidimensionales. Ordenación externa: Los datos están en un

dispositivo de almacenamiento externo y su ordenación es más lenta que la interna.

ALGORITMOS DE ORDENACIÓN

ALGORITMOS DE ORDENACIÓN INTERNA

selecciónburbuja

Inserción directa

shell

megasortquicksort

Este método consiste en buscar el elemento más pequeño del arreglo y ponerlo en primera posición, para esto se compara un elemento con los demás intercambiando posiciones de acuerdo a un criterio. Luego, entre los restantes, se busca el elemento más pequeño y se coloca en segundo lugar, y así sucesivamente hasta colocar el último elemento.

Ejemplo:

SELECCIÓN

5 43 2X [4] :

0 1 2 3

x[0]>x[1] ? Cierto. El 5 pasa a la posición x[1]. Y el 4 pasa a la posición x[0].

4 53 20 1 2 3

x[0]>x[2] Cierto. El 4 pasa a la posición x[2] y el 3 a la posición x[0].

x[0]>x[2] Cierto. El 3 pasa a la posición x[3] y el 2 a la posición x[0].

3 54 2

2 54 3

x[1] >x[2]. Cierto. El 5 pasa a la posición x[2] y el 4 a x[1].

x[1] >x[3]. Cierto. El 4 pasa a la posición x[3] y el 3 a x[1].

x[2] >x[3]. Cierto. El 5 pasa a la posición x[3] y el 4 a x[2].

Ya hemos conseguido acomodar al elemento mas pequeño en su lugar

2 45 3

2 35 4

2 34 5Pseudocódigo :Para i=0; i<(tam. del arreglo)-1; i incrementa para j=1; j<tam del arreglo; j incrementa si x[i]>x[j] temporal=x[i]; x[i]=x[j]; x[j]=temporal; fin si; fin para;fin para;

BURBUJA

Consiste en comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que estén todos ordenados.Ejemplo:

X [4] : 54320 1 2 3

Comparamos pares de elementos:x[0]>x[1] cierto. El 5 se cambia a x[1] y el 4 a x[0].

4532x[1]>x[2] cierto. El 5 se cambia a x[2] y el 3 a x[1].

x[2]>x[3] cierto. El 5 se cambia a x[3] y el 2 a x[2].

4352

4325

x[0]>x[1] cierto. El 4 se cambia a x[1] y el 3 a x[0].

3425

x[0]>x[1] cierto. El 4 se cambia a x[1] y el 2 a x[0].

3245

x[1]>x[2] cierto. El 4 se cambia a x[2] y el 2 a x[1].

2345

Se repite el ciclo hasta tener todos los números en orden. Pseudocódigo

n=0;mientras n<tam del arreglo -1 para i=0; i< tam del arreglo-1; i incrementa si x [i] > x [i-1] temporal = x [i]; x [i] = x [i-1]; x [i-1] = temporal; fin si; fin para; n=n+1;fin mientras;

INSERCIÓN DIRECTA

Este método consiste en buscar el elemento más pequeño del arreglo y ponerlo en primera posición; luego, entre los restantes, se busca el elemento más pequeño y se coloca en segundo lugar, y así sucesivamente hasta colocar el último elemento.

Pseudocódigo

para i = 1; i < tam del arreglo; i++ temp= x [i]; para j = i – 1; j >= 0 && x [ j ] > temp; j - -

x [ j +1] = x [ j ]; x [ j ] = temp; fin para;

fin para;

5 3 2

3 5 2

3 2 5

2 3 5

temp= 3X[0]>temp .Cierto se intercambian posiciones

temp= 2X[1]>temp .Cierto se intercambian posiciones

temp= 2X[0]>temp .Cierto se intercambian posiciones

ORDENAMIENTO SHELL SORT Esta forma de ordenación es muy parecida a la

ordenación con burbuja. La diferencia es que usando el método de burbuja se realiza una comparación lineal, y shellsort trabaja con una segmentación entre los datos, acomodándolos en un arreglo unidimensional y subsecuentemente ordenando las columnas. Por lo tanto es un buen método, pero no el mejor para implementarlo en grandes arreglos. 

Este proceso se repite cada vez con un arreglo menor, es decir, con menos columnas, en la ultima repetición solo tiene una columna, cada que se realiza el proceso se ordena mas los datos, hasta que en su ultima repetición están completamente ordenados. Sin embargo el numero de operaciones para ordenar en cada repetición esta limitado debido al pre-ordenamiento que se obtuvo en las repeticiones anteriores.

EJEMPLO:

Algoritmo ______________________________________…void Shel lSort(Lista)/ /Lista es un vector que contiene los elementos a ser ordenados.  1. Declarar variables enteras: i , j , incremento = 3, temp 2. Repetir mientras incremento > 0: 3. Repetir mientras i sea menor al tamaño de la Lista 4. j = i , temp = Lista[ i]  5. Repetir mientras j >= incremento y Lista[ j - incremento] > temp 6. Lista[ j] = Lista[ j - incremento], j = j - incremento7. [ f in de c ic lo del paso 5]8. Lista[ j] = temp9. [ f in de c ic lo del paso 3] 10. si incremento/2 != 0 entonces:11. incremento = incremento/212. si incremento == 1 entonces:13. incremento = 014. si no, entonces:15. incremento = 116. [ f in de c ic lo del paso 2]17. Sal ir

ORDENACION EXTERNA

Es un término genérico para los algoritmos de ordenamiento que pueden manejar grandes cantidades de información. El ordenamiento externo se requiere cuando la información que se tiene que ordenar no cabe en la memoria principal de una computadora (típicamente la RAM) y un tipo de memoria más lenta (típicamente un disco duro) tiene que utilizarse en el proceso.

Existen otros tipos de memoria externa que son los usb, de almacenamiento entre otros.

ORDENACION

La Ordenación externa de los datos están en un dispositivo de almacenamiento externo (Archivos) y su ordenación es más lenta que la interna.

Aquí primero se crea un archivo en notepad o encualquier editor de texto, después se busca el archivo que ene este caso es “países” en el disco duro con extensión TXT y los muestra en la tabla y lo abrimos como se muestra en el algoritmo.

ORDENACION

Aquí se muestra como se puede editar un texto txt, abriéndolo y ordenándolo como se muestra en la figura y algoritmo siguiente.

Combinación de dos estructuras de datos ordenadas para crear una estructura ordenada de mayor tamaño.

Arreglos enteros ordenados: a[1],…, a[M] b[1],…, b[N]

Fusionarlos en: c[1],…, c[M+N]

MERGE SORT (ORDENAMIENTO POR

FUSION)

Si la longitud de la lista es 0 ó 1, entonces ya

está ordenada. En otro caso:

Dividir la lista desordenada en dos sublistas

de aproximadamente la mitad del tamaño.

Ordenar cada

sublista recursivamente aplicando el

ordenamiento por mezcla.

Mezclar las dos sublistas en una sola lista

ordenada.

QUICK SORT (ORDENAMIENTO RÁPIDO)

Es el algoritmo de ordenamiento más eficiente de

todos, se basa en la técnica de "Divide y Vencerás",

que permite en promedio, ordenar n elementos en

un tiempo proporcional a n*log(n).

ALGORITMO FUNDAMENTAL:

Elegir un elemento de la lista de elementos a

ordenar, al que llamaremos pivote.

Resituar los demás elementos de la lista a

cada lado del pivote, de manera que a un

lado queden todos los menores que él, y al

otro los mayores.

La lista queda separada en dos sublistas, una

formada por los elementos a la izquierda del

pivote, y otra por los elementos a su derecha.

Repetir este proceso de forma recursiva para

cada sublista mientras éstas contengan más

de un elemento. Una vez terminado este

proceso todos los elementos estarán

ordenados.

IMPLEMENTACIÓN