PDF de programación - 11-Ordenar

11-Ordenar

11.1 Definiciones
11.2 Selección
11.3 Intercambio
11.4 Inserción
11.5 Shellsort
11.6 Quicksort
11.7 Mergesort

11: Ordenar

2

Definiciones

 Se desea ordenar un set de estructuras, que

contienen información, de acuerdo al valor de un
campo de la estructura denominado clave.

 Ordenamiento interno, es aquel que ordena un arreglo

de estructuras; y externo es aquel que ordena un
archivo de estructuras.

 Ordenamiento in situ, es aquel que no requiere espacio

adicional (se ordena en el mismo arreglo o archivo).

11: Ordenar

3

Definiciones II

 Suelen tenerse dos medidas de eficiencia: C(n) el

número de comparaciones de claves, y M(n) el número
de movimientos de datos, necesarios para lograr el
ordenamiento.

 Los métodos mas simples de ordenamiento suelen ser

de complejidad O(n2).

 Suelen ser el punto de partida de los métodos más

elaborados que suelen ser O(n*log2(n)).

11: Ordenar

4

Definiciones III

 En los diversos algoritmos de ordenamiento es

importante considerar su complejidad en el peor caso
y en promedio.

 Si se requiere un ordenamiento ascendente, cada vez
que en el arreglo se tenga: i < j con a[i] > a[j] se tiene
una inversión.

 Los algoritmos de ordenamiento eliminan todas las

inversiones.

11: Ordenar

5

11-Ordenar

11.1 Definiciones
11.2 Selección
11.3 Intercambio
11.4 Inserción
11.5 Shellsort
11.6 Quicksort
11.7 Mergesort

11: Ordenar

6

Selección

 Algoritmo Selection sort:
Repetir hasta que quede un arreglo de un elemento:
Seleccionar el elemento de la última posición del
arreglo. Sea j su cursor.
Buscar el elemento con la mayor clave en el resto del
arreglo.
Intercambiar el elemento de la última posición del
arreglo con el de mayor clave.
Disminuir el rango del arreglo en uno.

11: Ordenar

7

Selección: tipos

 Los siguientes tipos que serán usados en las funciones:

 typedef int Tipo; /* tipo de item del arreglo */
 typedef int Indice; /* tipo del índice */

 Ordenaremos ascendentemente: desde Inf hasta Sup.

11: Ordenar

8

Selección: código
void selectsort(Tipo a[], Indice Inf, Indice Sup)
{ Indice i, j, max; Tipo temp;

for (j=Sup; j>Inf; j--) {

max=j;
temp=a[j];
for(i=j-1; i>=Inf; i--) {

if (a[i]>temp) {

max=i;
temp=a[i];

// Selecciona el ultimo: a[j]
// Busca el mayor entre los
// otros elementos

}

}

a[max]=a[j];
a[j]=temp;
}

}

// Intercambia el mayor con a[j]

11: Ordenar

9

Selección: ejemplos
 Ejemplos: aleatorio y peor caso de datos de entrada

11: Ordenar

10

Selección: complejidad
 El for interno se realiza: (n-1)+(n-2) +…+ 1 veces. Ya que la primera
vez hay que buscar el mayor en un subarreglo de (n-1)
componentes; la segunda vez se busca el mayor en un subarreglo de
(n-2) componentes; y así sucesivamente.
 Suma que tiene por resultado: n*(n-1)/2.
 A esto se debe agregar la selección, que es O(1), y el intercambio
(que también es O(1)); acciones que se repiten (n-1) veces.
 La complejidad es T(n) = n*(n-1)/2 +(n-1) y entonces O(n2).
 Otra forma de calcular la complejidad es la observación de que el
algoritmo se rige por la relación de recurrencia: T(n) = T(n-1) + (n-1)
con T(0) = 0, ya que cada vez se reduce el tamaño del arreglo en
uno, pero con un costo para reducirlo de (n-1) operaciones O(1).
 Se logra igual resultado que el anterior: O(n2).

11: Ordenar

11

11-Ordenar

11.1 Definiciones
11.2 Selección
11.3 Intercambio
11.4 Inserción
11.5 Shellsort
11.6 Quicksort
11.7 Mergesort

11: Ordenar

12

Intercambio

 Se comparan e intercambian pares adyacentes de ítems, hasta

que todos estén ordenados.

 Los mas conocidos son bubble y shakesort. Son algoritmos muy

poco eficientes, estan aqui solo para ilustrar.

 Algoritmo Bubblesort:
Comenzar con i=0;
Repetir hasta que quede arreglo de tamaño uno:

Efectúa una pasada hacia arriba, hasta la última posición:

if (a[i] > a[i+1])

swap (a[i], a[i+1]); // intercambiar el mayor hacia arriba

i++;

Disminuir en uno el tamaño del arreglo partiendo por arriba.

11: Ordenar

13

Bubblesort: código
#define SWAP(a, b) { t=a; a=b; b=t; }
#define compGT(a, b) (a > b)
/* Ordena ascendente. Desde indice Inf hasta Sup */
void bubbleSort( Tipo a[], Indice Inf, Indice Sup ) {

Indice i, j; Tipo t; //temporal
for(i=Inf ; i<= Sup; i++) {

// Recorre el arreglo con i

for(j=Inf+1; j<=(Sup-(i-Inf)); j++) { // Recorre con j, compara

y

if( compGT( a[j-1], a[j] ) )

intercambio

// ordena por

SWAP(a[j-1], a[j]);

// el mayor queda arriba.

}

}

}
11: Ordenar
 El for interno se realiza: (n-1)+(n-2) +…1. Entonces es O(n2).

14

Bubblesort: complejidad

 Algoritmo shakesort o bubblesort de dos pasadas (ambos son O(n2)):
Comenzar con i=0;
Repetir hasta que quede arreglo de tamaño uno:
Efectúa una pasada hacia arriba, hasta la última posición:

if (a[i] > a[i+1])

swap (a[i], a[i+1]);
i++; (más pesado en última posición)

Disminuye en uno el tamaño del arreglo (por arriba)
Efectúa una pasada hacia abajo, hasta el inicio del arreglo:

if (a[i-1] > a[i])

swap (a[i], a[i-1]);
i--; (más liviano en primera posición)

Acorta en uno el tamaño del arreglo (por abajo).

11: Ordenar

15

11-Ordenar

11.1 Definiciones
11.2 Selección
11.3 Intercambio
11.4 Inserción
11.5 Shellsort
11.6 Quicksort
11.7 Mergesort

11: Ordenar

16

Inserción

 Algoritmos Inserción:

En la etapa i-ésima se inserta a[i] en su lugar correcto entre:
a[0], a[1],…, a[i-1] que están previamente ordenados.
Hay que desplazar los elementos previamente ordenados, uno a
uno, hasta encontrar la posición donde será insertado a[i].

 En el peor caso: si a[0] es mayor que a[i] hay que efectuar i

copias.

 En el mejor caso si a[i-1] es menor que a[i], no hay

desplazamientos.

 Si existen claves repetidas, éstas conservan el orden original, se

dice que el algoritmo de ordenamiento es estable.

11: Ordenar

17

Inserción: código

typedef int Tipo; /* tipo de item del arreglo */
typedef int Indice; /* tipo del índice */
#define compGT(a, b) (a > b)
void InsertSort(Tipo *a, Indice inf, Indice sup) {

Tipo t; Indice i, j; /*Ordena ascendentemente */
for (i = inf + 1; i <= sup; i++) {

t = a[i]; //se marca el elemento que será insertado.

/* Desplaza elementos hasta encontrar punto de inserción */

for (j = i-1; j >= inf && compGT(a[j], t); j--)

a[j+1] = a[j];

a[j+1] = t; /* lo inserta */
}

}

11: Ordenar

18

Inserción: ejemplos
 Ejemplos: aleatorio y peor caso de datos de entrada

11: Ordenar

19

Inserción: complejidad
 En el peor caso, el for interno se efectúa: 1 + 2 + 3 +…+(n-1).
 Esto en caso que el arreglo esté previamente ordenado en forma

descendente. En el primer recorrido del for interno hay que mover
un elemento; en la segunda pasada, hay que mover dos elementos; y
así sucesivamente, hasta mover (n-1) para dejar espacio en la
primera posición, para insertar el último.

 Esto tiene complejidad T(n) = n*(n-1)/2 + (n-1) = O(n2). Se agregan

(n-1) movimientos por el almacenamiento del elemento que será
insertado, más la escritura para la inserción; ambas son O(1).

 En el mejor de los casos con un arreglo previamente ordenado en

forma ascendente, el for interno no se realiza nunca; ya que no son
necesarios los desplazamientos que éste efectúa; el lazo externo
debe efectuarse (n-1) vez. Este caso es de complejidad: T(n) =
O(n). Mientras más ordenado parcialmente esté el arreglo, mejor
será el comportamiento del algoritmo de inserción.

11: Ordenar

20

Inserción Binaria
 Una posible mejora del algoritmo es la consideración de que el

subarreglo en el cual se insertará el elemento está previamente
ordenado.

 En este caso, en lugar de efectuar una búsqueda secuencial de la
posición de inserción, se puede realizar una búsqueda binaria. Sin
embargo esto disminuye el número de comparaciones y no el de
movimiento de los datos (que suele ser de mayor costo).

11: Ordenar

21

Inserción Binaria: código
int BinaryInsertSort(Tipo *a, Indice inf, Indice sup)
{ int op=0;
Tipo t;
Indice i, j, right, left, m;
for (i = inf + 1; i <= sup; i++) {
t = a[i];
left=inf ;
right=i-1;
while (left<=right) {
m=(left+right)/2;
if ( t <a[m]) right=m-1;
else left=m+1;
}


// Desplazar elementos
for (j = i-1; j >= left ; j--)
{
a[j+1] = a[j];
op++;
}
/* inserte */
a[left] = t;
op++;
}
return(op);
}

11: Ordenar

22

11-Ordenar

11.1 Definiciones
11.2 Selección
11.3 Intercambio
11.4 Inserción
11.5 Shellsort
11.6 Quicksort
11.7 Mergesort

11: Ordenar

23

Shellsort
 Es uno de los algoritmos más rápidos para ordenar

arreglos de algunas decenas de componentes. Es una
generalizacion del Insertion sort.

 Es un método adaptivo que funciona mejor si los
arreglos están casi ordenados. El análisis de su
complejidad es difícil.
 Algoritmo Shellsort:

Se ordenan elementos que están a una distancia h entre ellos en

pasadas consecutivas.

Al inicio h es un valor elevado y disminuye con cada pasada.
Sea hk cuando la distancia de comparación es k. La pasada se

denomina fase hk. El algoritmo termina con h1.

11: Ordenar

24

Shellsort II
 Después de la fase hk los elementos que están a distancia hk entre
ellos están ordenados: a[i] < a[i + hk] < a[i + 2hk ] < a[i + 3hk] < … para
todo i.

 El ordenamiento burbuja ordena en fase h1. Necesariamente

shellsort tiene que llegar a ordenar la fase h1, pero su ventaja es
que el número de intercambios en la fase h1 es menor que los
intercambios necesarios en inserción o por burbuja.

 La razón de esto es que si a una lista ordenada de fase hk se la

somete a un ordenamiento de fase hk-1 sigue hk ordenada.

11: Ordenar

25

Shellsort: código
// El algoritmo original hace que hk sea el anterior dividido por dos.
void shellsortShell(Tipo a[], Indice n)
{ Indice