sort - curso 08

5/8/2018 Sort - Curso 08 - slidepdf.com

http://slidepdf.com/reader/full/sort-curso-08 1/53

1Programación II

ClasificaciónIntroducción.

– Existe un orden lineal definido para los elementos del

conjunto a clasificar, por ejemplo, “menor que”.

– La clasificación puede dividirse en interna interna interna interna y externa.externa.externa.externa.

– Estabilidad del método.

– Los algoritmos más simples (“directos”) requieren tiempos de

O(n 2

), otros O(nlogn) (“indirectos”) y algunos, para clases especiales de datos, O(n).

– Los objetos a clasificar contienen un elemento del tipo para el

cual se define la relación de ordenación.



2Programación II

ClasificaciónClasificación interna.

– Ordenar un conjunto de elementos de forma tal que

los valores de sus claves formen una secuencia no

decreciente.– Usar con cuidado el almacenamiento disponible.

– Medida de eficiencia: contar número de

comparaciones de claves C y de movimientos de elementos M.



3Programación II

ClasificaciónClasificación interna.

– podemos agrupar los métodos de la siguiente forma:

» Métodos específicos:

Numeración o cuenta Por urnas

Por residuos

» Clasificación por inserción.» Clasificación por intercambio.

» Clasificación por selección



4Programación II

ClasificaciónClasificación por inserción.

– en el i-ésimo recorrido se inserta el i-ésimo elemento en el lugar correcto entre los (i-1) elementos anteriores, los

cuales fueron ordenados previamente.

– Después de hacer la inserción, se encuentran clasificados

los elementos A[1], ..., A[i].

for i = 2 to n domover Ri hacia la posición j <= i tal que

Ri < Rk para j<=k<i , y

Ri <= R j-1 o j=1.



5Programación II

Clasificación Algoritmo de inserción directa.

Inserción Directabegin

Desde i = 2 hasta n do

Aux K[i]

j i - 1

mientras (j > 0) y Aux < K[j] hacer

K[j+1] K[j]

j j - 1fin mientras

K[j+1] Aux

fin desde

end



6Programación II

ClasificaciónInserción binaria e inserción a dos vías

– El algoritmo de inserción directa se mejora utilizando

búsqueda binaria para encontrar el lugar donde insertar.

– Lo que se reduce en este caso es la cantidad de

comparaciones, la cual, además, será independiente del orden

inicial de los elementos; los movimientos siguen igual.

– El orden sigue siendo n 2 .

– Inserción a dos vías: el primer elemento se sitúa en el centro

del área de salida, y el espacio para los siguientes se obtiene

moviendo a la derecha o izquierda, según sea conveniente.



7Programación II

ClasificaciónMétodo de Shell (Shellsort) o clasificación por disminución de

incrementos.– Si el algoritmo mueve los elementos sólo una posición por vez su tiempo

de ejecución será proporcional a N 2 .

– Buscamos un mecanismo para que los elementos puedan dar grandes saltos en vez de pequeños pasos.

– Ejemplo: primero dividimos los 16 registros en 8 grupos de dos, (R 1,

R 9 ),(R 2 , R 10 ),...,(R 8 , R 16 ) y clasificamos cada grupo por separado.

– A continuación dividimos los elementos en 4 grupos de 4, y clasificamos

cada grupo por separado.

– Continuamos así hasta tener un sólo grupo con los 16 elementos.



8Programación II

Clasificación

503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703

503 087 154 061 612 170 765 275 653 426 512 509 908 677 897 703

503 087 154 061 612 170 512 275 653 426 765 509 908 677 897 703

154 061 503 087 512 170 612 275 653 426 765 509 897 677 908 703

061 087 154 170 275 426 503 509 512 612 653 677 7033 765 897 908

8

4

2

1

Clasificación por disminución de incrementos.



9Programación II

Clasificación Algoritmo de clasificación de Shell

8 4 2 1

H

t 1

Shell Sort

begin

for s:= t downto 1 do

k:= H[s]

for i = k + 1 to n do

Aux:= K[i]

j := i - k

while (j > 0) and Aux < K[j] do

K[j+k] := K[j]

j := j - k

end while

K[j+k]:= Aux

end {for i}

end {for s}

end



10Programación II

Clasificación Análisis del algoritmo de Shell.

– Para elegir una buena secuencia de incrementos es necesario analizar el tiempo de ejecución en función de estos incrementos.

– No se conoce la mejor secuencia para grandes valores de N.

– Los incrementos no deben ser múltiplos de sí mismos, de forma que las cadenas se mezclen entre sí lo más a menudo posible.

– Secuencias razonables (en orden inverso) :

» 1, 4, 13, 40, 121 ...

» 1, 3, 7, 15, 31 ...

– El orden es de n 1.26

.



11Programación II

ClasificaciónInserción en Lista.

– Un método efectivo para mejorar un algoritmo dado es examinar cuidadosamente la estructura de los datos a

clasificar.

– ¿ Cuál es la estructura más adecuada para la inserción directa ?

– La inserción directa implica dos operaciones básicas:» exploración de un conjunto ordenado para hallar la posición en la que hay que

insertar.

» inserción del elemento en el lugar hallado.

– La mejor estructura es la lista encadenada simple.



12Programación II

Clasificación Algoritmo de inserción en lista encadenada.

– L es un vector que contiene los campos de enlace.

– La lista es circular.InsercionEnLista

beginL0 = N; LN = 0

for j = N-1 downto 1 do

begin

p = L0; q = 0

while K j > Kp and p > 0 doq = p; p = Lq

Lq = j

L j = p

end

end



13Programación II

Clasificación

j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

KJ - 503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703

Lj 16 0

Lj 16 0 15

Lj 14 16 0 15

Lj

Lj

Lj

Lj

Lj

Lj

Lj

Lj

Lj

Lj

Lj

Lj

Lj

Ejemplo de inserción en lista.



14Programación II

ClasificaciónInserción en listas múltiples.

– Si se conoce de antemano el rango de las claves, y

éstas se encuentran uniformemente distribuidas en el

entorno, se pueden utilizar varias listas abarcando cada una un subrango.

– Se mantienen varias listas en vez de una.

– Se requiere espacio para las M cabeceras de listas.

– Dentro de cada lista se utiliza el método anterior.



15Programación II

ClasificaciónEjemplo de listas múltiples.

– M = 4.

– Rangos: 0 - 249, 250 - 499, 500 - 749, 750 - 999

Conjunto original:

503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703

Resultado final:

Lista 1: 061 087 154 170

Lista 2: 275 426

Lista 3: 503 509 512 612 653 677 703

Lista 4: 765 897 908



16Programación II

ClasificaciónMétodos de Inserción, resumen.

– Inserción directa : N 2 / 4 comparaciones y N 2 /4 movimientos.– Inserción binaria: NlogN comparaciones y N 2 /4 movimientos.

– Inserción a dos vías: NlogN comparaciones y N 2 /8

movimientos.

– Shell: N 1.2 comparaciones y movimientos.

– Lista: N 2 / 4 comparaciones, 0 movimientos y 2N cambios de

enlace.

– Listas múltiples: mejora comparaciones a N 2 / M.



17Programación II

ClasificaciónMétodos de Intercambio.

– Llamados así porque el intercambio o trasposición de

elementos es su característica dominante. El

algoritmo se basa en el principio de comparar e intercambiar pares subsiguientes de elementos, hasta

que todos estén ordenados.

– Burbuja.– Cocktail.

– Quicksort.



18Programación II

Análisis del tiempo de ejecución:– Intercambia lleva un tiempo constante.

– Los pasos 2 a 4 llevan un tiempo c 1(n-1).

– Estos se ejecutan desde i = 1 hasta N-1.– Para tener en cuenta los incrementos y pruebas de i, se agrega un

término de c 2 n.

– El total resulta

ClasificaciónBurbuja. Burbuja

begin

(1) for i = 1 to N-1 do

(2) for j = N downto i +1 do

(3) if K j < K j-1 then

(4) intercambia (R j, R j-1)

end

( )c n c n c n c c n

i

n

2 1

1

1

1

2

2 111

2

1

2

+ − = + −

=

−

∑



19Programación II

ClasificaciónIntercambio alternado: vibración o cocktail:

ShakerSortbegin

L:= 2; R:= n; k:= n

repeat

for j:= R downto L do

if Kj-1 > Kj then intercambia(Rj-1, Rj); k:= j;L:= k+1

for j:= L to R do

if Kj-1 > Kj then intercambia(Rj-1, Rj); k:= j;

R:= k-1

until L > Rend



20Programación II

ClasificaciónQuicksort.

– Es tal vez el algoritmo más eficiente para clasificación interna.– Su orden es de N log N.

– La idea es clasificar un conjunto de elementos R 1..R N tomando

uno de ellos, de clave K v , como pivote, procurando que sea la mediana del conjunto, de forma que esté precedido y sucedido por

más o menos la mitad de los elementos del conjunto.

– Se permutan los elementos de forma que, para algún valor de j,todos los que tienen clave menor que K v se encuentran a la

izquierda de j jj j, y los de clave mayor o igual están a la derecha.



21Programación II

Clasificación3 1 4 1 5 9 2 6 5 3

2 1 1 4 5 9 3 6 5 3

2 1 1 4 5 9 3 6 5 3

1 1 2 4 3 3 9 6 5 5

1 1 2 4 3 3 9 6 5 5

3 3 4 5 6 5 9

3 3 4 5 6 5 9

5 5 6

5 5 6

Nivel 1

Nivel 2

Nivel 3

Nivel 4

Nivel 5



22Programación II

ClasificaciónDesarrollo del algoritmo de Quicksort.

– El algoritmo opera sobre un conjunto de elementos R 1,..R N

definido de manera externa.

– El procedimiento quicksort(i,j) ordena desde R i hasta R j en

el mismo lugar.(1) if existen al menos dos K distintas entre Ki y Kj then

begin

(2) v = mayor clave encontrada entre las dos primeras distintas

(3) permutar Ri,.,Rj de forma que, para alguna k tal que i+1 <= k < j,Ki,..,Kk-1 < v y Kk,..Kj >= v

(4) quicksort(i,k-1)

(5) quicksort(k,j)

end



23Programación II

ClasificaciónDesarrollo del Quicksort.

– Aplicar la línea (3) del algoritmo, permutando en el lugar.

» Introducimos dos cursores, L y R, en los extremos izquierdo y derecho del conjunto considerado, respectivamente.

» Los elementos a la izquierda de L (R i ,..R L-1 ) siempre tendrán claves menores que el pivote, y los elementos a la derecha de R(R R+1,..,R j ) tendrán claves mayores o iguales que el pivote.

» Los elementos del centro estarán mezclados.claves < pivote claves >= pivote

i jL R

claves mezcladas



24Programación II

ClasificaciónDesarrollo del Quicksort, pasos del algoritmo.

– Rastrear.

» Mover L a la derecha en los registros cuyas claves sean menores que

el pivote. Mover R a la izquierda en las claves mayores o iguales

que el pivote.– Probar.

» Si L > R ( L = R +1), entonces el conjunto ya se ha dividido, salir.

– Desviar.» Si L < R , intercambiar R L con R R .Después de hacerlo, K L es menor

que el pivote y K R es mayor o igual.



25Programación II

ClasificaciónQuicksort - partición.

function particion( i, j: integer; pivote: TipoClave): integer;

{divide A[i], .., A[j] para que las claves menores que pivote estén a la izquierda y las mayores

o iguales a la derecha. Devuelve el lugar donde se inicia el grupo de la derecha.}

var

L,R : integer; {cursores de acuerdo a la descripción anterior}

begin

L := i;R := j;

repeat

intercambia(A[L],A[R]);

{ahora se inicia la fase de rastreo}

while A[L].clave < pivote do

L := L + 1;

while A[R].clave >= pivote do

R := R - 1;

until L > R

particion :=L;

end; {particion}

(1)(2)

(3)

(4)

(5)(6)

(7)

(8)

(9)



26Programación II

ClasificaciónQuicksort: programa.

procedure quicksort( i,j: integer);{clasifica los elementos A[i],..,A[j] del arreglo externo A}

var

pivote : TipoClave; {el valor del pivote}

IndicePivote : integer; {el índice de un elemento de A donde clave es el pivote}

k : integer; {índice al inicio del grupo de elementos >= pivote}

begin

IndicePivote := EncuentraPivote(i,j);

if IndicePivote <> 0 then {no hacer nada si todas las claves son iguales}

begin

pivote := A[IndicePivote].clave;

k := particion(i,j,pivote);quicksort(i,k-1);

quicksort(k,j);

end;

end; {quicksort}

(1)

(2)

(3)

(4)(5)

(6)



27Programación II

Quicksort(AQuicksort(AQuicksort(AQuicksort(A:::: TarrayTarrayTarrayTarray;;;; i, ji, ji, ji, j integerintegerintegerinteger) (Otra implementación)) (Otra implementación)) (Otra implementación)) (Otra implementación)

varvarvarvar L,R,tempL,R,tempL,R,tempL,R,temp:::: integerintegerintegerinteger;;;;

beginbeginbeginbeginL := iL := iL := iL := i ;;;; R := jR := jR := jR := j;;;;

pivote := Apivote := Apivote := Apivote := A[[[[((((LLLL ++++RRRR) / 2) / 2) / 2) / 2]]]]

WhileWhileWhileWhile (L <= R)(L <= R)(L <= R)(L <= R)

WhileWhileWhileWhile (A(A(A(A[[[[LLLL]]]] < pivote< pivote< pivote< pivote AndAndAndAnd L < j)L < j)L < j)L < j) L := L + 1L := L + 1L := L + 1L := L + 1;;;; WendWendWendWend;;;;

WhileWhileWhileWhile (pivote < A(pivote < A(pivote < A(pivote < A[[[[RRRR]]]] AndAndAndAnd R > i)R > i)R > i)R > i) R := RR := RR := RR := R –––– 1111;;;; WendWendWendWend;;;;

IfIfIfIf (L <= R)(L <= R)(L <= R)(L <= R) ThenThenThenThen

temptemptemptemp := A:= A:= A:= A[[[[LLLL] ;] ;] ;] ; AAAA[[[[LLLL]]]] := A:= A:= A:= A [[[[RRRR];];];]; AAAA[[[[RRRR]]]] :=:=:=:= temptemptemptemp;;;;

L := L + 1L := L + 1L := L + 1L := L + 1;;;; R := RR := RR := RR := R ---- 1111

EndEndEndEnd IfIfIfIfWendWendWendWend

IfIfIfIf (i < R)(i < R)(i < R)(i < R) ThenThenThenThen QuicksortQuicksortQuicksortQuicksort (A, i, R)(A, i, R)(A, i, R)(A, i, R);;;;

IfIfIfIf (L < j)(L < j)(L < j)(L < j) ThenThenThenThen QuicksortQuicksortQuicksortQuicksort (A, L, j)(A, L, j)(A, L, j)(A, L, j);;;;

EndEndEndEnd;;;;

Clasificación



28Programación II

ClasificaciónQuicksort: Análisis del tiempo de ejecución.

– El algoritmo insume en promedio un tiempo O(NlogN) y en el peor caso, O(N 2 ).

– Primero se mostrará que la función partición lleva un

tiempo proporcional al número de elementos que deberá separar, es decir, O(j-i+1);

– El número esperado de intercambios en la partición

será de (j-i+1)/6.

– Ahora debemos evaluar cuántas pasadas se efectúan.



29Programación II

ClasificaciónQuicksort: Análisis del tiempo de ejecución.

– En el mejor de los casos se elige siempre la mediana, y entonces tendremos log(N) pasadas, lo cual da NlogN

comparaciones y 1/6 (NlogN ) intercambios.

– El caso promedio resulta peor que el mejor caso por un

factor de 2 Ln2 .

– El peor caso se da cuando elegimos siempre el pivote en un extremo del conjunto, y se realizan entonces N

particiones, por lo cual el algoritmo resulta O(N 2 ).



30Programación II

ClasificaciónClasificación por selección.

– Se basa en los siguientes pasos:» Hallar la menor clave del conjunto; transferir el registro correspondiente al área de

salida y sustituir la clave por el valor infinito.

» Repetir el paso anterior, esta vez se seleccionará la segunda menor clave.

» Continuar repitiendo el primer paso hasta que se hayan seleccionado la totalidad de los registros.

– El método requiere que estén presentes todos los elementos antes de que

se pueda empezar la clasificación y genera la salida final uno a uno en

secuencia.

– Se puede usar para la salida la misma área de memoria del conjunto

original de datos, moviendo el elemento a su posición definitiva, y se

evita el uso del infinito.



31Programación II

Métodos de clasificación por selección:

– Selección directa. O(N 2 )

– Selección cuadrática. O( )

– Selección en árbol. O(NlogN) – Heapsort. O(NlogN)

Clasificación

N N



32Programación II

Clasificación Algoritmo de selección directa.

SelecciónDirectafor i := 1 to N - 1 do

begin

IndiceMenor := i

ClaveMenor := Ki

for j = i + 1 to N doif K j < ClaveMenor then

begin

ClaveMenor = K j

IndiceMenor = j

endintercambia(Ri, RIndiceMenor)

end



33Programación II

Selección cuadrática.

– La idea es dividir el conjunto en raíz(N) grupos de raíz(N) elementos cada uno.

– Cada selección, después de la primera, necesita como máximo comparaciones dentro del grupo

más comparaciones entre los “vencedores”

del grupo.– El tiempo total de ejecución resulta O( ).

– Esta idea conduce a la selección en árbol.

Clasificación

N −1

N −1

N N



34Programación II

ClasificaciónSelección en árbol.

503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703

503 512 908 897 653 509 677 765

512 908 653 765

908 765

908



Programación II

Clasificación Arboles parcialmente ordenados.

– La clave de un nodo cualquiera v vv v no es mayor que la de sus hijos.Nótese que los nodos con claves pequeñas no necesitan estar a niveles

más altos que los de claves mayores.

– En el nivel más bajo, si no está completa, has hojas faltantes serán

del extremo derecho, es decir que el nivel se completa de izquierda a

derecha .

6

3

10

5

98

9

18 910



Programación II


– Consideramos dos operadores: SuprimeMinimo e Inserta .» SuprimeMinimo. Se devuelve el elemento con menor clave, que se

encuentra en la raíz. Se debe ahora arreglar el árbol para que se siga

cumpliendo la propiedad de árbol parcialmente ordenado. Para ello se toma la hoja de más a la derecha del nivel más bajo y se coloca en

la raíz. Luego se lleva este elemento lo más abajo posible,

intercambiándolo con el hijo que tenga la prioridad más baja, hasta

que el elemento se encuentre en una hoja o en una posición en la cual las claves de los hijos sean iguales o mayores.



Programación II


– INSERTA.

» Se coloca el nuevo elemento lo más a la izquierda posible

en el nivel más bajo, creando un nuevo nivel si éste ya se

encuentra completo.

» Si el nuevo elemento tiene una clave menor que la de su

padre, se intercambia con éste. Este proceso de

comparación e intercambio se repite hasta que el elemento

llegue a la raíz o alcance una posición en la cual tenga

clave mayor que la de su padre.



Programación II

Clasificación Heapsort. El peor caso y el caso promedio son O(nlogn).

– El algoritmo se puede representar en forma abstracta por medio de las cuatro operaciones INSERTA, SUPRIMEMIN y VACIA.

– L es la lista de elementos a clasificar y S un conjunto de elementos que

se usa para guardar los ya clasificados.

COM

Mientras no(vacia(L)) hacer

Inserta(Elimina(Primero(L),L),APO);

Fin mientras;

Mientras no(Vacio(APO)) hacerInserta(SuprimeMin(APO),FIN(L),L);

Fin mientras;

FIN



Programación II

ClasificaciónRepresentación de los árboles parcialmente

ordenados mediante arreglos.– Montículo (heap).

– Si hay n nn n nodos, se utilizan las primeras n nn n posiciones de un

arreglo A. A[1] contiene la raíz. El hijo izquierdo del nodo A[i], si existe, se encuentra en A[2i], y el hijo derecho, si

existe, en A[2i+1].

– Los nodos del árbol llenan A[1], A[1],…, A[1] nivel a nivel,desde arriba, y de izquierda a derecha dentro de cada nivel.

El árbol de ejemplo se puede almacenar en un arreglo así:

3, 5, 9, 6, 8, 9, 10, 10, 18, 9



Programación II

ClasificaciónHeapsort

– El conjunto S SS S siempre estará almacenado como un heap en la parte superior del arreglo A AA A, como A[1],.. A[i] si S SS S tiene i ii i elementos. El

elemento más pequeño siempre estará en A[1]. Los elementos que se van

eliminando de S SS S se pueden almacenar en A[i+1],.., A[n], clasificados en

orden inverso, es decir, A[i+1] >= A[i+2] >=... A[n].

– la operación SuprimeMinimo puede realizarse entonces intercambiando

A[1] con A[i].

– Como el nuevo A[1] viola la propiedad del árbol parcialmente ordenado,debe descender en el árbol hasta su lugar, para lo cual se usa el

procedimiento ArmaHeap.



41Programación II

Clasificación Algoritmo de Heapsort

Procedure HeapSort;var i: integer;

begin

for i := n div 2 downto 1 do

ArmaHeap(i,n);for i := n downto 2 do

begin

Intercambia(R1,Ri);

ArmaHeap(1,i-1);

end;end;

Procedure ArmaHeap(primero, ultimo: integer);

var r: integer;

begin

r := primero;

while r <= ultimo div 2 do

if ultimo = 2*r then

begin

if Kr > K2r then Intercambia(Rr, R2r);

r := ultimo;

end

else {r tiene dos hijos}

Intercambia si corresponde con 2r o 2r + 1

r := 2*r o 2*r + 1, según haya intercambiado

Si no intercambia, r := ultimo;

end;



42Programación II

ClasificaciónBinsort (clasificación por urnas).

– Los algoritmos de clasificación ya vistos tienen una cota mínima de O(nlogn).

– Si se conoce el rango de los valores de las claves se puede pasar a O(n).

– Ej: Si el tipo de clave es entero con rango 1..n, y

existen n claves diferentes, entonces es posible diseñar un algoritmo de clasificación de orden n.



43Programación II

ClasificaciónBinsort.

– Solución con dos arreglos: el original A y otro como área de salida B.

– Solución con una sola área.

for i = 1 to n do

B[A[i]] := A[i];

for i = 1 to n do

while A[i] <> i do

intercambia(A[i], A[A[i]]);

3 1 4 10 5 9 2 6 7 8

Ejemplo:



44Programación II

ClasificaciónBinsort

– Problema con los duplicados: en el algoritmo anterior asumimos que no existían.

– Para manejarlos, podemos hacer que el arreglo B contenga

cabezales a listas en las cuales se almacenan los registros con claves duplicadas.

– Se pueden usar punteros al último de cada lista, y éste a su

vez puede apuntar al primer elemento de la lista siguiente, para poder recorrer todo el conjunto sin tener que utilizar las

cabeceras.



45Programación II

Clasificación Algoritmo de Binsort con listas.

– Orden:» Las sentencias (1) y (2) llevan tienen un tiempo de ejecución de

O(n)

» Las (3) y (4) O(m), donde m es el número de claves diferentes.

» El total del algoritmo es de O(m+n).

procedure binsort;

vari : integer;

v: TipoClave;

begin

for i := 1 to n do

Inserta(A[i], AlFinal(B[A[i]]))for i := u to v-1 do

Concatena(Ultimo(B[i]), Primero(B[i+1]));

end;

(1)

(2)(3)

(4)



46Programación II

ClasificaciónRadix o Clasificación por residuos.

– Asumimos un TipoClave constituído por k elementos,f1,f2,..,fk, de tipos t1, t2,...,tk.

– Se desea clasificar los registros en orden lexicográfico.

– Ejemplos:

type

TipoClave = record

dia : 1..31;mes: 1..12;

año: 1900..2050;

end;

type

TipoClave = array[1..10] of char;



47Programación II

Clasificación Algoritmo de Radix.

– Se clasifica la lista A de n registros con claves que consisten de kcampos. El procedimiento usa k arreglos Bi de tipo array[ti] of

TipoLista.procedure RadixSort;

begin

for i := k downto 1 do

begin

for cada valor v de tipo ti do Vaciar(Bi[v]); {limpiar las urnas}

for cada registro R de A do

mover R desde A hasta el final de la urna Bi[v];

f or cada valor v de tipo ti do

concatena Bi[v] en el extremo de A.

end;

end;

(1)

(2)

(3)

(4)

(5)

(6)



48Programación II

ClasificaciónEjemplo de Radix.TipoClave = record

k1: 0..9;k2: 0..5;

k3: 0..3;

A : array[1..n] of TipoClave;

8 3 3 7 2 1 1 5 2 6 0 1 2 2 1 6 5 3 9 4 0

1 2 3 4 5 6 7 8

3 1 3

B3 B2 B1

0

1

2

3

0

1

2

3

4

5

0

1

2

34

5

6

7

8

9



49Programación II

Clasificación Análisis de algoritmo de Radix.

– El ciclo de la línea (2) tarda un tiempo O(s i ), donde si es el número de valores diferentes del tipo ti.

– El ciclo de las líneas (3) y (4) lleva un tiempo O(n).– El ciclo de las líneas (5) y (6) lleva un tiempo O(s i ).

– El tiempo total entonces es :

O s n O k n s O n si i

i

k

i

i

k

i

k ( ) ( * ) ( )+ = + = +

= ==

∑ ∑∑1 11



50Programación II

ClasificaciónClasificación por cuenta.

– El método se basa en la idea de que la clave j en la secuencia clasificada final es mayor que (j-1) del resto de las claves.

– ((comparar K j con K i ) para 1 <= j <= N) para 1<=i<=N

– ((comparar K j con K i ) para 1 <= j <= N) para 1<=i<=N

– Algoritmo de Cuenta por Comparación:

» Clasifica R 1, ..., R N según las claves K 1, ... K N manteniendo una

tabla auxiliar Cuenta[1],...Cuenta[N] para contar el número de claves menores que una clave dada.

» Al terminar el algoritmo, Cuenta[j] + 1 indica la posición final del

registro R j .



51Programación II

Clasificación

El algoritmo no implica movimiento de registros.

¿Qué pasa con las claves iguales?

¿Cuál es el orden de ejecución del algoritmo?

CuentaPorComparación

begin

for i = 1 to N

cuenta[i] = 0

for i = N downto 2

for j = i-1 downto 1

if Ki < K j then incrementar cuenta[j]

else incrementar cuenta[i]end

end



52Programación II

ClasificaciónCuenta por distribución .

– Aplicable en caso de que existan muchas claves iguales, y cuando están en el ámbito u<=Kj<=v, donde (v-u) es pequeño.

– Supongamos que todas las claves están entre 1 y 100.

– En la primer pasada contamos cuántas ocurrencias de cada clave hay,en la segunda pasada movemos los elementos al lugar apropiado en el

área de salida.

– todas las claves iguales para u<= Kj <= v

– clasifica los registros R1,..,RN, usando tabla auxiliar Cuenta[u], ...,Cuenta[v].

– Al final del algoritmo los elementos se mueven al área de salida S 1,...,

S N , en el orden deseado.



53Programación II

ClasificaciónCuentaPorDistribución

COM

Desde i = u hasta v hacer cuenta[i] 0 findesde

Desde i = 1 hasta N hacer incrementar (cuenta[K[i]]) findesde

Desde i = u +1 hasta v hacer

cuenta[i] cuenta[i] + cuenta[i-1]

findesde

Desde j = N hasta 1 hacer

i cuenta[K[j]]

S[i] R[j]

cuenta[K[j]] i-1

findesdeFIN

sort - curso 08

Documents