Arturo Díaz Pérez

Análisis y Complejidad de Algoritmos

Métodos de Ordenamiento Arturo Díaz Pérez ¬ ® ¯ ° ± ²

Tipos de ordenamiento y medidas de eficiencia Algoritmos básicos QuickSort HeapSort BinSort RadixSort Arboles de Decisión

Análisis y Diseño de Algoritmos

Sorting-1

Tipos de Ordenamiento F Ordenamiento interno. ß Se lleva a cabo completamente en memoria principal. Todos los objetos que se ordenan caben en la memoria principal de la computadora

F Ordenamiento externo. ß No cabe toda la información en memoria principal y es necesario ocupar memoria secundaria. El ordenamiento ocurre transfiriendo bloques de información a memoria principal en donde se ordena el bloque y este es regresado, ya ordenado, a memoria secundaria

Análisis y Diseño de Algoritmos

Análisis y Complejidad de Algoritmos

Sorting-2

1

Arturo Díaz Pérez

Formulación

ß Registros: ß Llaves: ß Obtener la secuencia ß tal que,

r1, r2, ..., rn k1, k2, ..., kn

ri1 , ri2 ,..., rin ki1 ≤ ki2 ≤ ... ≤ kin

Análisis y Diseño de Algoritmos

Sorting-3

Criterios de Eficiencia F Criterios de eficiencia ß El número de pasos ß El número de comparaciones entre llaves para ordenar n registros. /De utilidad cuando la comparación entre llaves es costosa ß El número de movimientos de registros que se requieren para ordenar n registros. /De utilidad cuando el movimiento de registros es costoso

Análisis y Diseño de Algoritmos

Análisis y Complejidad de Algoritmos

Sorting-4

2

Arturo Díaz Pérez

Métodos Simples de Ordenamiento F Métodos simples ß Método de Burbujeo ß Método de Inserción ß Método de Selección

Sorting-5

Análisis y Diseño de Algoritmos

Método de Burbujeo 25

3

12

19

2

1

9

6

1

25

3

12

19

2

6

9

2

25

3

12 19

6

9

3

25

6

12

19

9

6

25

9

12 19

9

25

12 19

12

25 19

void Burbujeo( int A[], int n) { int i,j; for( i=0; i < n-1; i++ ) for( j=n-1; j > i; j--) if( A[j] < A[j-1] ) Intercambia( &A[j], &A[j-1] ); }

19 25

Análisis y Diseño de Algoritmos

Análisis y Complejidad de Algoritmos

Sorting-6

3

Arturo Díaz Pérez

Método de Burbujeo void Burbujeo( int A[], int n) { int i,j; for( i=0; i < n-1; i++ ) for( j=n-1; j > i; j--) if( A[j] < A[j-1] ) Intercambia( &A[j], &A[j-1] ); } n −1

n −1

i =1

i =1

Comparaciones:

c = ∑ (n − i ) = ∑ i =

Movimientos:

M min = 0 n −1

n −1

i =1

i =1

n(n − 1) n 2 n = − 2 2 2

M max = ∑ ( n − i ) = ∑ i =

n(n − 1) n 2 n = − 2 2 2

Sorting-7

Análisis y Diseño de Algoritmos

Método de Selección 25

3

12

19

2

1

9

6

1

3

12

19

2

25

9

6

2

12

19

3

25

9

6

3

19

12

25

9

6

6

12

25

9

19

9

25

12

19

12

25

19

19

25

Análisis y Diseño de Algoritmos

Análisis y Complejidad de Algoritmos

void Selección( int A[], int n ) { int i, j, imin; for( i=0; i < n-1; i++ ) { imin = i; for( j = i+1; j > n; j++ ) if( A[j] < A[imin] ) imin = j; intercambia( &A[i], &A[imin] ); } }

Sorting-8

4

Arturo Díaz Pérez

Método de Selección void Selección( int A[], int n ) { int i, j, imin; for( i=0; i < n-1; i++ ) { imin = i; for( j = i+1; j > n; j++ ) if( A[j] < A[imin] ) imin = j; intercambia( &A[i], &A[imin] ); } }

n−1

n−1

i=1

i =1

C = ∑n − i = ∑i =

Comparaciones:

Movimientos:

n(n − 1) n2 n = − 2 2 2

M = n −1 Sorting-9

Análisis y Diseño de Algoritmos

Método de Inserción

25

3

12

19

3

25

12

3

12

25

19

3

12

19

25

2

2

3

12

19

25

1

1

2

3

12

19

25

9

1

2

3

9

12

19

25

1

2

3

6

9

12

19

2

Análisis y Diseño de Algoritmos

Análisis y Complejidad de Algoritmos

1

9

6

void Inserción( int A[], int n ) { int i,j;

6

for( i=1; i < n; i++ ) { j:= i; while( j > 0 && A[j] < A[j-1] ) { Intercambia( &A[j], &A[j-1] ); j-} } }

25

Sorting-10

5

Arturo Díaz Pérez

Método de Inserción void Inserción( int A[], int n ) { int i,j; for( i=1; i < n; i++ ) { j:= i; while( j > 0 && A[j] < A[j-1] ) { Intercambia( &A[j], &A[j-1] ); j-} } }

Comparaciones:

Cmin = n − 1 n −1

n −1

i =1

i =1

Cmax = ∑ ( n − i ) = ∑ i =

n( n − 1) n 2 n = − 2 2 2

M min = 0

Movimientos:

n −1

M max = ∑ i = i =1

n ( n − 1) n 2 n = − 2 2 2 Sorting-11

Análisis y Diseño de Algoritmos

QuickSort F Dado un arreglo desordenado de n elementos 1 2 3

n-1 n

A

ß selecciona un valor v del arreglo, llamado pivote, y rearregla los elementos del arreglo de manera que todos los elementos menores que v queden colocados antes que v y todos los elementos mayores o iguales que v queden colocados después que v. 1 2

j-1

1 2

< v Análisis y Diseño de Algoritmos

Análisis y Complejidad de Algoritmos

n

j v

n

>v Sorting-12

6

Arturo Díaz Pérez

QuickSort 1 2

n

j-1

1 2

j v

n

< v >v void quicksort( int A[], int i, int j ) { if( desde A[i] hasta A[j] existen al menos dos llaves distintas ) { Seleccionar un pivote, v Permutar A[i], ...,A[j], tal que, para algún k entre i+1 y j, A[i], ..., A[k-1] < v y A[k], . . . , A[j] ≥ v quicksort( A, i, k-1 ); quicksort( A, k, j ); } } Sorting-13

Análisis y Diseño de Algoritmos

QuickSort: Pivote i

j

int pivote( int A[],int i,int j ) { int k, r; for( k = i+1; k 0 ) return k; } /* No hay llaves diferentes */ return -1; } Análisis y Diseño de Algoritmos

Análisis y Complejidad de Algoritmos

Sorting-14

7

Arturo Díaz Pérez

QuickSort: Particionamiento j

i 0 ) intercambia ( &A[r], &A[2*r] ); r = j; } else { /* r tiene dos hijos */ if( comp( A[r], A[2*r] ) > 0 && comp( A[2*r], A[2*r+1] ) 0 && comp( A[2*r+1], A[2*r] ) A[n-k+2] > . . . > A[n] void HeapSort( A, n ) . . { int i; for( i = n/2; i >= 1; i-- ) /* Inicialmente, establece la propiedad del árbol parcialmente ordenado */ desciende ( A, i, n); for( i = n; i >= 1; i-- ) { /* Quita el menor elemento */ intercambia( &A[1], &A[i] ); /* reestablece el árbol parcialmente ordenado */ desciende( A, 1, i-1 ); } } Análisis y Diseño de Algoritmos

Análisis y Complejidad de Algoritmos

Sorting-34

17

Arturo Díaz Pérez

Ordenamiento Lineal F Supongamos que las llaves son enteros en el rango de 1 a n, y que no existen llaves iguales. ß Si A y B son arreglos de tipo adecuado y los n elementos que van a ser ordenados están inicialmente en A, se pueden colocar en el arreglo B en el orden de sus llaves mediante for( i = 1; i