1

NOMBRE DEL ALUMNO:

EDGAR RIVAS RIVAS

NOMRE DEL DOCENTE :

DIONISIO PÉREZ PÉREZ

CARRERA:

ING. EN SISTEMAS COMPUTACIONALES

UNIDAD 5

MÉTODOS DE ORDENAMIENTO

2

Ordenar significa reagrupar o reorganizar un conjunto de datos u objetos en una

secuencia específica.

Formalmente se define ordenación de la siguiente manera:

Sea A una lista de N elementos:

A1, A2, A3, …, AN

Ordenar significa permutar estos elementos de tal forma que queden de acuerdo

con la distribución preestablecida.

Ascendente: A1 ≤ A2 ≤ A3 ≤ … ≤ AN

Descendente: A1 ≥ A2 ≥ A3 ≥ … ≥ AN

En el procesamiento de datos los métodos de ordenación se les clasifica en dos

grandes categorías, según, donde hayan sido almacenados:

Ordenación de Arreglos

Ordenación de Archivos

ORDENACIÓN INTERNA

También se le denomina ordenación interna ya que los elementos o componentes

del arreglo se encuentran en la memoria principal de la computadora.

ORDENACIÓN EXTERNA

Se le llama ordenación externa ya que los elementos se encuentran en archivos

almacenados en dispositivos de almacenamiento secundario como discos, cintas,

tambores, etc.

3

PRESENTACION………………………………………………………………………1

INTRODUCCIÓN……………………………………………………………………….2

ÍNDICE…………………………………………………………………………………...3

5.1 ALGORITMOS DE ORDENAMIENTO INTERNOS……………………………4

5.1.1 BURBUJA…………………………………………………………………………4 5.1.2 QUICKSORT………………………………………………………………………6 5.1.3 SHELLSORT………………………………………………………………………8 5.1.4 RADIX……………………………………………………………………………..10 5.2 ALGORITMOS DE ORDENAMIENTO EXTERNOS……………………………11 5.2.1 INTERCALACIÓN………………………………………………………………..11 5.2.2 MEZCLA DIRECTA………………………………………………………………12 5.2.3 MEZCLA NATURAL……………………………………………………………..14

CONCLUSIÓN…………………………………………………………………………..15

BIBLIOGRAFÍA………………………………………………………………………….16

4

5.1 ALGORITMOS DE ORDENAMIENTO INTERNOS

5.1.1 BURBUJA.

El método de burbuja también se le puede llamar como Método de "intercambio

directo". El algoritmo ordena los elementos del arreglo utilizando el método de la

burbuja . Transporta en cada pasada el elemento más pequeño hacia la parte de

izquierda del arreglo.

Este ordenamiento es eficiente sólo en listas pequeñas (10 elementos).

El método de burbuja va comparando cada elemento del arreglo con el siguiente;

si un elemento es mayor que el que le sigue, entonces se intercambian; esto

producirá que en el arreglo quede como su último elemento, el más grande. Este

proceso deberá repetirse recorriendo todo el arreglo hasta que no ocurra ningún

intercambio. Los elementos que van quedando ordenados ya no se comparan.

"Baja el más pesado".

Este método se basa en el principio de comparar pares de elementos adyacentes

e intercambiarlos entre sí hasta que estén todos ordenados.

A continuación se muestra el código del método de la burbuja

método de ordenamiento burbuja

public void burbuja ()

{inicio del método burbuja

for(int i=nElementos-1;i>1;i--)primer

for recorre

el arreglo

{

for(int j=1;j<=i;j++)for interno compara

{

if (datos[j-1]>datos[j])

intercambiar(j-i,j);

}fin del for interno

}fin del primer for recorre

}//fin del método burbuja

5

6

5.1.2 QUICKSORT.

QUICKSORT (ORDENAMIENTO RAPIDO)

Es un algoritmo basado en la técnica de “divide y vencerás” que permite en

promedio ordenar n elementos en un tiempo proporcional a n lóg. n. el algoritmo

original es recursivo, pero se utilizan versiones interactivas para mejorar su

ordenamiento.

DESCRIPCION DEL ALGORITMO.

Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.

Resituar los demás elementos de la lista de cada lado del pivote, de manera de

que a su lado izquierdo queden todos los menores y al derecho los mayores. En

ese momento, el pivote ocupa exactamente el lugar que le corresponde en la lista

ordenada.

La lista queda separada en 2 sublistas.

Repetir este proceso de forma recursiva para cada sablista mientras estas

contengan más de i elemento.

A)

5 3 7 6 2 1 4

1 2 3 4 5 6 7

A [1]>A [7] se cambia

B)

B [2]> B [7]

B [3]> B [7] se cambia

C)

4 3 5 6 2 1 7

1 2 3 4 5 6 7

4 3 7 6 2 1 5

1 2 3 4 5 6 7

7

C [3]>C [6] se cambia

D)

D [4]> D [6] se cambia

E)

4 3 1 5 2 6 7

1 2 3 4 5 6 7

E [4]> E [5] se cambia

F)

F [4] < F [1] se cambia

G)

G) [1]> G [3] se cambia

H)

H [3] < H [2] se cambia

I)

Se junta el vector I y el vector F y queda de la siguiente manera.

4 3 1 6 2 5 7

1 2 3 4 5 6 7

4 3 1 2 5 6 7

1 2 3 4 5 6 7

2 3 1 4

1 2 3 4

1 2 3 4

1 2 3 4

1 2 3 4

1 2 3 4

8

5.1.3 SHELLSORT.

El método de Shell es una versión mejorada del método de inserción directa. Y

recibe el nombre en honor a su autor, Donald Shell.

El método también se conoce como de inserción con incrementos decrecientes.

En el método de ordenación por inserción directa cada elemento se compara para

su ubicación correcta en el arreglo con los elementos que se encuentren en la

parte izquierda del si mismo. Si el elemento a insertar es mas pequeño que el

grupo de elementos que se encuentran a su izquierda, es necesario efectuar

entonces varias comparaciones antes de su ubicación.

Shell propone que las comparaciones entre elementos se efectúen con saltos de

mayor tamaño pero con incrementos decrecientes, así, los elementos quedaran

ordenados en el arreglo más rápidamente.

EJEMPLO DE 16 ELEMENTOS.

15 67 08 16 44 27 12 35 56 21 13 28 60 36 07 10

Se dividen los elementos en 8 grupos:

La ordenación produce:

15 21 08 16 44 27 07 10 56 67 13 28 60 36 12 35

Se dividen los elementos en 2 grupos:

9

La ordenación produce:

15 21 07 10 44 27 08 16 56 36 12 28 60 67 13 35

Se dividen los elementos en 2 grupos:

La ordenación produce:

07 10 08 16 12 21 13 27 15 28 44 35 56 36 60 67

Dividimos los elementos en un solo grupo:

La ordenación queda de la siguiente manera:

07 08 10 12 13 15 16 21 27 28 35 36 44 56 60 67

10

5.1.4 RADIX

Es un algoritmo que ordena números enteros de forma individual, es decir del

menos significativo al mas significativo.

Este ordenamiento consta de 10 dígitos de (0-9), su ordenamiento es del más

significativo al menos significativo de “menor a mayor”

Cola--------------------------------------------------------------------------------------------------------

---------------------------vector original

Asignamos los

elementos en

colas basadas en el digito menos significativo de cada uno de ellos.

0 1 2 3 4 5 6 7 8 9

12,92 33 25 86 57,37 48

Después de la primera pasada, la ordenación queda:

12 92 33 25 86 57 37 48

Colas basadas en el digito más significativo.

0 1 2 3 4 5 6 7 8 9

12 25 33,37 48 57 86 92

Vector ordenado.

12 25 33 37 48 57 86 92

0 1 2 3 4 5 6 7 8 9 25 57 48 37 12 92 86 33

11

5.2 ALGORITMOS DE ORDENAMIENTO EXTERNOS

ALGORITMO DE ORDENACION EXTERNA

19 27 2 8 36 5 20 15 6

a) 19 27 2 8 36

b) 5 20 15 6

5 19 20 27 2 15 6 8 36

a)5 19 2 15 36

a)20 27 6 8

5 19 20 27 2 6 8 15 36

a)5 19 20 27 36

a)2 6 8 15

2 5 6 8 15 19 20 27 36

a)2 5 6 8 15 19 20 27

b)36

2 5 6 8 15 19 20 27 36

5.2.1 INTERCALACIÓN

En este método de ordenamiento existen dos archivos con llaves ordenadas, los

cuales se mezclan para formar un solo archivo.

La longitud de los archivos puede ser diferente.

El proceso consiste en leer un registro de cada archivo y compararlos, el menor es

almacenando en el archivo de resultado y el otro se compara con el siguiente

elemento del archivo si existe. El proceso se repite hasta que alguno de los

archivos quede vacío y los elementos del otro archivo se almacenan directamente

en el archivo resultado.

Ordenar un fichero d a partir del propio fichero y de dos ficheros auxiliar a y b.

(Ordenar en memoria en bloques de 3)

12

Fichero d.

19 27 2 8 36 5 20 15 6

Paso 1.

Memoria fichero a = 2, 19, 27

Memoria fichero b = 5, 8, 36

Memoria fichero c = 6, 15, 20

Paso 2.

Mezclar los bloques ordenados de los ficheros a y b en d.

Fichero d.

2 5 8 19 27 36 6 15 20

Paso 3.

Fichero a: 2, 5, 8, 19, 27, 36

Fichero b: 6, 15, 20

Paso 4.

Fichero d.

2 5 6 8 15 19 20 27 36

5.2.2 MEZCLA DIRECTA

ƒ Algoritmo de Mezcla Directa:

ƒ Dividir una secuencia inicial de datos en dos subcadenas y mezclar elemento a

elemento de forma ordenada.

ƒ El proceso se repite hasta que la secuencia inicial queda totalmente ordenada.

ƒ Pasos:

13

ƒ 1) Se divide la secuencia inicial de datos del fichero a en dos mitades b y c

ƒ 2) Se mezclan b y c combinando elementos aislados para formar pares

ordenados

ƒ 3) La secuencia resultante se almacena en el fichero a y se repiten los pasos 1)

y 2) para formar cuádruplos ordenados.

ƒ 4) Se repiten los pasos anteriores para formar octetos ordenados, y así

sucesivamente.

ƒ Ejemplo de mezcla

Directa:

ƒ Las comillas simples („)

indican fin de tupla.

14

5.2.3 MEZCLA NATURAL

Es una mejora del algoritmo de mezcla directa puesto que en vez de considerar

tramos de tamaño fijo se toman en cuenta para la ordenación en todo momento

tramos de longitud máxima.

Al igual que la mezcla directa se debe hacer un proceso de partir el archivo

original para mezclarlo, posteriormente mientras en el archivo C haya elementos a

mezclar.

P1

2^0 = 1

C

0 200 2 752 3 7 18 1 56 0

A1= 0 2 3 18 56

A2= 200 752 7 1 0

C1

0 200 2 752 3 7 1 18 0 56

P2

2^1 = 2

A1= 0 200 3 7 0 56

A2= 2 752 1 18

C2

0 2 200 752 1 3 7 18 0 56

P3

2^2 = 4

A3= 0 2 200 752 0 56

B3= 1 3 7 18

C3

0 1 2 3 7 18 200 752 0 57

P

15

El método burbuja es uno de los más simples en cuanto a lógica de ordenamiento,

pero también es el que tiene una estructura algorítmica más larga y con más

procesos para una computadora que el método Shell. Este último llega a ser muy

eficaz, ya que aparte de ir comparando números como el burbuja, el Shell no lo

hace de arriba para abajo o viceversa según el arreglo, sino que al principio

compara a partir del número de espacios en el arreglo dividido entre dos, y el

número que se encuentre en esa posición se empieza a comparar con el último,

dando esto, la minimización de

iteraciones.

16

WWW.GOOGLE.COM

http://estructuradedatositp.wikispaces.com/5.2.1.+Algoritmo+de+ordenamiento+ext

erno+INTERCALACION