Análisis y complejidad de algoritmos

Análisis y Complejidad de Algoritmos

Métodos de Ordenamiento
¬ ® ¯ ° ± ² 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 lamemoria 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

Sorting-2

Análisis y Complejidad deAlgoritmos

1

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ónentre 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

Sorting-4

Análisis y Complejidad de Algoritmos

2

Arturo Díaz Pérez

Métodos Simples de Ordenamiento
F Métodos simples
ß Método de Burbuja ß Método de Inserción ß Método de SelecciónAnálisis y Diseño de Algoritmos

Sorting-5

Método de Burbuja
25 1 3 25 2 12 3 25 3 19 12 3 25 6 2 19 1 2 9 6 6 19 6 9 9 9

12 19 6 25 9 12 9 25 12

12 19 12 19 25 19 19 25

void Burbuja( 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] ); }

Análisis y Diseño de Algoritmos

Sorting-6

Análisis y Complejidadde Algoritmos

3

Método de Burbuja
void Burbuja( 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 i =1 n −1 i =1

Comparaciones: Movimientos:

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

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

M min = 0
M max = ∑ ( n − i ) = ∑ i =
i =1 i =1 n −1 n −1

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

Análisis yDiseño de Algoritmos

Sorting-7

Método de Selección
25 1 3 3 2 12 12 12 3 19 19 19 19 6 2 2 3 12 12 9 1 25 25 25 25 25 12 9 9 9 9 9 12 25 19 6 6 6 6 19 19 19 25
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] ); } }

Análisis y Diseño de Algoritmos

Sorting-8Análisis y Complejidad de Algoritmos

4

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] ); } }

Comparaciones:

C = ∑n − i = ∑i =
i=1 i =1

n−1

n−1

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

Movimientos:

M = n −1
Sorting-9

Análisis y Diseño deAlgoritmos

Método de Inserción

25 3 3 3 2 1 1 1

3 25 12 12 3 2 2 2

12 12 25 19 12 3 3 3

19

2

1

9

6

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-} } }

19 25 19 12 9 6 2 25 19 12 9 1 25 19 12 9 25 19 6 25

Análisis y Diseño de Algoritmos

Sorting-10

Análisis yComplejidad de Algoritmos

5

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
Cmax = ∑ ( n − i ) = ∑ i =
i =1 i =1 n −1 n −1

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

Movimientos:

M min = 0
M max = ∑ i =
i =1 n −1

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