Sorting2

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
objetosque 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 Complejidadde 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 cuandola 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ónSorting-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 yComplejidad 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...