Administracion

Solo disponible en BuenasTareas
  • Páginas : 5 (1168 palabras )
  • Descarga(s) : 0
  • Publicado : 30 de agosto de 2012
Leer documento completo
Vista previa del texto
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 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...
tracking img