Administracion
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 memoriaprincipal. 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ñode 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 decomparaciones 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 deOrdenamiento
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:
n(n − 1) n 2 n
=
−
2
22
M min = 0
n −1
n −1
i =1
i =1
M max = ∑ ( n − i ) = ∑ i =
n(n − 1) n 2 n
=
−
2
22
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
96
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
22
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...
Regístrate para leer el documento completo.