Upload
nel-lr
View
228
Download
0
Embed Size (px)
Citation preview
8/16/2019 120283Tarea Sobre Ordenacion Algo3
http://slidepdf.com/reader/full/120283tarea-sobre-ordenacion-algo3 1/16
UNIVERSIDAD NACIONAL SAN ANTONIO
ABAD DEL CUSCO
TRABAJO DE INVESTIGACION SOBRE ALGORITMO DE
ORDENACION
FACULTAD:
FACULTAD DE INGENIERÍA ELÉCTRICA, ELECTRÓNICA, INFORMATICA Y MECÁNICA.
CARRERA:
INGENIERIA INFORMATICA Y DE SISTEMAS
CURSO:
ALGORITMICA III
DOCENTE:
IVAN MEDRANO VALENCIA
ALUMNO: CODIGO:
• NELSON LOPEZ RAMOS 120283
SEMESTRE 201!1
CUSCO!PERU
201
8/16/2019 120283Tarea Sobre Ordenacion Algo3
http://slidepdf.com/reader/full/120283tarea-sobre-ordenacion-algo3 2/16
TABLA DE RESUMEN DE ALGORITMOS DE ORDENACION
(ESTABILIDAD E IN SITU)
Semestre 2016-1
TAREA 1
Algoritmo deOrdenación
Mejor Caso eor Caso Caso rome!"o Esta#"$"!a! IN SITU
I%sert"o%Sort Estable Si
Se$e&t"o%Sort No Estable Si
B'##$eSort Estable Si
Se$$Sort Depende (*) Depende (*) No Estable Si
ea*Sort No Estable Si
Mer+eSort Estable No
,'"&Sort No Estable Si
Co'%t"%+Sort Estable No
Ra!".Sort Estable No
TAREA 2
8/16/2019 120283Tarea Sobre Ordenacion Algo3
http://slidepdf.com/reader/full/120283tarea-sobre-ordenacion-algo3 3/16
ALOR!T"OS DE ORDENA#!ONORDENACION OR SACUDIDA (SA/ER SORT)
Ordenamiento de b$rb$%a bidireccional o por sac$dida&El ordenamiento de b$rb$%a bidireccional (s'aer sort coctail sort en ingls)es $n algoritmo de ordenamiento +$e s$rge como $na me%ora delalgoritmo ordenamiento de b$rb$%a&
La manera de traba%ar de este algoritmo es ir ordenando al mismo tiempo por losdos e,tremos del -ector& De manera +$e tras la primera iteración tanto el menorcomo el ma.or elemento estar/n en s$s posiciones 0inales& De esta manera sered$ce el nmero de comparaciones a$n+$e la comple%idad del algoritmo sig$esiendo O(n)&
3acemos $n recorrido ascendente (del primer elemento al ltimo) cogemos el
primer elemento . lo comparamos con el sig$iente si el sig$iente es menor lopasamos al p$esto anterior de esta 0orma al 0inal de la lista nos +$eda elma.or& 4na -e5 terminada la serie ascendente 'acemos $n recorrido descendente(del ltimo elemento al primero) pero esta -e5 nos +$edamos con los menores a los+$e -amos adelantando posiciones en -e5 de retrasarlas como 'icimos en la serieascendente& Repetimos las series alternati-amente pero red$ciendo el /mbito ens$s e,tremos p$es .a tendremos all6 los -alores m/s ba%os . m/s altos de lalista 'asta +$e no +$eden elementos en la serie7 en el pse$docódigo de e%emplo83asta (i5+ 9 der)&
A contin$ación se m$estra el pse$do:código del algoritmo8
;rocedimiento Ordenacion<Sac$dida (-8-ector tam8entero)
=ariables i % i5+ der ltimo8 tipoposicion7
a$,8 tipoelemento7
!nicio
>>L6mites s$perior e in0erior de elementos ordenados
i5+ ?: 2
der ?: tam
ltimo ?: tam
Repetir
>>@$rb$%a 'acia la i5+$ierda >>Los -alores menores -an a la i5+$ierda
>>der -a dismin$.endo en 1 'asta llegar a i5+
;ara i ?: der 'asta i5+ 'acer
Si -(i:1) 9 -(i) entonces
a$, ?: -(i)
-(i) ?: -(i:1)
-(i:1) ?: a$,
ltimo ?: i
Bin<si
Bin<para
8/16/2019 120283Tarea Sobre Ordenacion Algo3
http://slidepdf.com/reader/full/120283tarea-sobre-ordenacion-algo3 4/16
i5+ ?: ltimoC1
>>@$rb$%a 'acia la derec'a
>>Los -alores ma.ores -an a la derec'a ;ara % ?: i5+ 'asta der 'acer
Si -(%:1) 9 -(%) entonces
a$, ?: -(%)
-(%) ?: -(%:1)
-(%:1) ?: a$,
ltimo ?: %
Bin<si
Bin<para
der ?: ltimo:1
3asta (i5+ 9 der)
Bin
ORDENAMIENTO CON ARBOL BINARIO
Ordenamiento con /rbol binario
El ordenamiento con /rbol binario es $n algoritmo de ordenamiento el c$al ordenas$s elementos 'aciendo $so de $n /rbol binario de bs+$eda& Se basa en irconstr$.endo poco a poco el /rbol binario introd$ciendo cada $no de loselementos los c$ales +$edar/n .a ordenados& Desp$s se obtiene la lista de loselementos ordenados recorriendo el /rbol en in:orden&
#omple%idad
!nsertar elementos en $n /rbol binario de bs+$eda tiene $na
comple%idad O(log n)& Entonces agregar n elementos a $n /rbol c$al+$iera da comores$ltado $na comple%idad O(n log n)& Adem/s recorrer los elementos del /rbolen in:orden tiene comple%idad O(n)&
#aracter6sticas
• Tiene $n b$en rendimiento&
• Es estable (no cambia el orden relati-o de elementos ig$ales)&
• No re+$iere espacio de almacenamiento e,tra&
• ;$ede ordenar listas tal c$al las recibe&
8/16/2019 120283Tarea Sobre Ordenacion Algo3
http://slidepdf.com/reader/full/120283tarea-sobre-ordenacion-algo3 5/16
ORDENAMIENTO CON GNOME SORT
El algoritmo de ordenación conocido como gNome<sort tiene $na 'istoria dein-ención c$asi paralela& D$rante $n tiempo e,istió la polmica sobre s$
in-ención 0inalmente atrib$ida a 3amid Sarba5i:A5ad +$ien lo desarrolló en elao 2 . al +$e llamó St$pid sort (Ordenamiento estpido)&
#$ando Dic r$ne lo in-entó (m/s apropiadamente lo rein-entó) . doc$mentó1 no'alló e-idencias de +$e e,istiera . en palabras s$.as di%o de lFt'e simplest sort algorit'mF2 (es el algoritmo m/s simple) . +$i5/s tenga ra5ónp$es lo describió en sólo c$atro l6neas de código& Dic r$ne se basó enlos gnomos de %ard6n 'olands en cómo se colocan en los maceteros (-er lare0erencia anterior) . de a'6 tambin el nombre +$e le dio&
Netamente es $n algoritmo de b$rb$%a con $na clara partic$laridad8 recorre elarra. a ordenar como $na cremallera en $n -ai-n o bien p$ede ser de0inido como$n ordenamiento de b$rb$%a bidireccional +$e a s$ -e5 son llamadostambin coctail s'aer(agitador de cocteles) por la 0orma en +$e traba%a&&&
#$mple estrictamente 'ablando con la comple%idad O(n)&
Descripción
El algoritmo empie5a comparando la primera pare%a de -alores si est/n en ordenincrementa el p$ntero . de n$e-o reali5a la comparación si no est/n en orden sepasa el menor a la i5+$ierda . el ma.or a la derec'a . se red$ce el p$nteroa'ora la comparación es con el elemento anterior si no 'a. $n elemento anteriorse pasa al sig$iente elemento& #$ando el p$ntero alcan5a el e,tremo s$periordel arra. .a est/ totalmente ordenado&
#$ando compara 'acia arriba -a sin 'acer intercambios es +$e el par ba%o e,amenest/ ordenado entre s6 . c$ando compara 'acia aba%o -a 'aciendo intercambios&El proceso aparece como $n 5ig5ag$eo contin$o a $n lado . otro&
La operación empie5a por el p$ntero en el p$nto m/s ba%o . c$ando llega ale,tremo s$perior 'a terminado de ordenar el arra.&
;ara reali5ar $n ordenamiento in-erso basta cambiar la decisión de intercambio delos elementos es decir de%ar los ma.ores aba%o . los menores arriba&
8/16/2019 120283Tarea Sobre Ordenacion Algo3
http://slidepdf.com/reader/full/120283tarea-sobre-ordenacion-algo3 6/16
;se$docódigo
i G 1 "ientras i H len: 1 Si iI1 o aJi:1K H aJiK
i G iC1 Sino temp G aJi:1K aJi:1K G aJiK aJiK G temp i G i:1 Si i I i G 1 Binsi Binsi Bin"ientras
ORDENAMIENTO EINE (COMB SORT)
En ciencias de la comp$tación el comb sort (combIpeine) es $n algoritmo de
ordenamiento relati-amente simple diseado por lod5imier5 DobosieMic5 en 1&;osteriormente 0$e redesc$bierto . pop$lari5ado por Step'en Lace. . Ric'ard@o, en $n art6c$lo p$blicado por la re-ista @.te en abril de 11& El algoritmocomb sort me%ora el algoritmo de ordenamiento de b$rb$%a . ri-ali5a en -elocidadcon algoritmos m/s comple%os como el P$icsort& La idea b/sica eseliminar tort$gas o pe+$eos -alores cerca del 0inal de la lista .a +$e en elalgoritmo de ordenamiento de b$rb$%a esto red$ce la -elocidad de ordenamientotremendamente& (Los cone%os grandes -alores alrededor del inicio de la lista noplantean $n problema en el algoritmo de ordenamiento de b$rb$%a&)
En el ordenamiento de b$rb$%a c$ando dos elementos c$ales+$iera se comparansiempren tienen $n espacio (distancia entre ellos) de 1& La idea b/sica del
algoritmo comb sort es +$e el espacio p$eda ser m$c'o ma.or de $no&El ordenamiento S'ell tambin se basa en esta idea pero es $na modi0icación delalgoritmo de ordenamiento por inserciónm/s +$e del algoritmo de ordenamiento deb$rb$%a&
El espacio se inicia como la longit$d de la lista a ordenar di-idida porel 0actor de encogimiento (generalmente 1Q7 -ase deba%o) . la lista se ordenacon este -alor (redondeado a la ba%a a $n entero si es necesario) para elespacio& Desp$s el espacio se di-ide por el 0actor de encogimiento de n$e-o lalista se ordena con este n$e-o espacio . el proceso se repite 'asta +$e elespacio es 1& En este momento el algoritmo comb sort contin$a $sando $n espaciode 1 'asta +$e la lista est/ completamente ordenada& La etapa 0inal del
ordenamiento es as6 e+$i-alente al algoritmo de ordenamiento de b$rb$%a pero en
8/16/2019 120283Tarea Sobre Ordenacion Algo3
http://slidepdf.com/reader/full/120283tarea-sobre-ordenacion-algo3 7/16
este momento la ma.or6a de las tort$gas .a 'an sido tratadas de manera +$e $nalgoritmo de ordenamiento de b$rb$%a ser/ e0iciente&
Bactor de encogimiento
El 0actor de encogimiento tiene $n gran e0ecto en la e0iciencia del algoritmocomb sort& En el art6c$lo original los a$tores s$gierieron 1Q desp$s de probaralg$nas listas aleatorias . encontrarlo generalmente el m/s e0ecti-o& 4n -alorm$. pe+$eo red$ce la -elocidad del algoritmo por+$e se deben 'acer m/scomparaciones mientras +$e $n -alor demasiado grande p$ede +$e no elimines$0icientes tort$gas para +$e sea pr/ctico&
El te,to describe $na me%ora del algoritmo comb sort $sando el -alor
base como 0actor de encogimiento& Tambincontiene $na implementación en pse$docódigo con $nas tablas de espacios
prede0inidos&
#ombsort11
#on $n 0actor de encogimiento alrededor de 1Q sólo 'a. tres posibles maneras de+$e la lista de espacios acabe8 ( Q 2 1) (1 U Q 2 1) o (11 Q 2 1)& Sólo el ltimo de estos dos 0inales mata todas las tort$gasantes de +$e el espacio se con-ierta en 1& ;or lo tanto se p$eden 'acer me%orassigni0icati-as en la -elocidad si el espacio se establece en 11 siempre +$e sea o 1& A esta -ariación se le llama #ombsort11&
Si se $sa c$al+$iera de las sec$encias +$e comien5a por o 1 el paso 0inal con
$n espacio de 1 es menos probable +$e 'a.a ordenado los datos completamentenecesitando otro paso con $n espacio de 1& Los datos est/n ordenados c$ando no se'acen intercambios d$rante $n paso con espacio I 1&
E%emplo en pse$docódigo del algoritmo combsort11
0$nction combsort11(arra. inp$t)
gap8I inp$t&si5e >>iniciali5ar tamao de espacio
loop $ntil gap I 1 and sMaps I
>>act$ali5ar el -alor del espacio para el sig$iente rastreo
i0 gap 9 1
gap8I gap > 1&Q
i0 gap I 1 or gap I
gap8I 11
end i0
end i0
8/16/2019 120283Tarea Sobre Ordenacion Algo3
http://slidepdf.com/reader/full/120283tarea-sobre-ordenacion-algo3 8/16
i8I
sMaps8I >>-ase ordenamiento de b$rb$%a para $na e,plicación
>>$n nico FrastreoF sobre la lista de entrada
loop $ntil i C gap 9I arra.&si5e
i0 arra.JiK 9 arra.JiCgapK
sMap (arra.JiK arra.JiCgapK)
sMaps8I sMaps C 1
end i0
i8I i C 1
end loop
end loop
end 0$nction
ORDENAMIENTO OR CASILLEROS (BUC/ET SORT)
8/16/2019 120283Tarea Sobre Ordenacion Algo3
http://slidepdf.com/reader/full/120283tarea-sobre-ordenacion-algo3 9/16
Los elementos se distrib$.en en c$bos
L$ego se ordenan los elementos de cada c$bo
El ordenamiento por casilleros (b$cet sort o bin sort en ingls) es$n algoritmo de ordenamiento +$e distrib$.e todos los elementos a ordenar entre
$n nmero 0inito de casilleros& #ada casillero sólo p$ede contener los elementos+$e c$mplan $nas determinadas condiciones& En el e%emplo esas condiciones soninter-alos de nmeros& Las condiciones deben ser e,cl$.entes entre s6 parae-itar +$e $n elemento p$eda ser clasi0icado en dos casilleros distintos& Desp$scada $no de esos casilleros se ordena indi-id$almente con otro algoritmo deordenación (+$e podr6a ser distinto segn el casillero) o se aplicarec$rsi-amente este algoritmo para obtener casilleros con menos elementos& Setrata de $na generali5ación del algoritmo ;igeon'ole sort& #$ando los elementos aordenar est/n $ni0ormemente distrib$idos la comple%idad comp$tacional de estealgoritmo es de O(n)&
El algoritmo contiene los sig$ientes pasos8
1& #rear $na colección de casilleros -ac6os
2& #olocar cada elemento a ordenar en $n nico casillero
Q& Ordenar indi-id$almente cada casillero
& de-ol-er los elementos de cada casillero concatenados por orden
8/16/2019 120283Tarea Sobre Ordenacion Algo3
http://slidepdf.com/reader/full/120283tarea-sobre-ordenacion-algo3 10/16
;se$docódigo
0$nción b$cet:sort(elementos n)
casilleros G colección de n listas
para i I 1 'asta longit$d(elementos) 'acer
c G b$scar el casillero adec$ado
insertar elementosJiK en casilleroJcK
0in para
para i I 1 'asta n 'acer
ordenar(casillerosJiK)
0in para
de-ol-er la concatenación de casillerosJ1K&&& casillerosJnK
A+$6 elementos es la lista de datos a ordenar . n el nmero de casilleros +$e+$eremos $sar& ;ara b$scar el casillero adec$ado para $n elemento se p$ede$tili5ar la tcnica +$e m/s con-enga segn cómo +$eramos ordenar los datos& La0$nción ordenar p$ede ser c$al+$ier 0$nción de ordenamiento incl$so lapropia b$cet:sort&
8/16/2019 120283Tarea Sobre Ordenacion Algo3
http://slidepdf.com/reader/full/120283tarea-sobre-ordenacion-algo3 11/16
ORDENA"!ENTO ;OR #4ENTAS (#O4NT!N SORT)
#o$nting Sort (Ordenamiento ;or #$entas)Ordenamiento por c$entasEl ordenamiento por c$entas (co$nting sort en ingls) es $n algoritmo deordenamiento en el +$e se c$enta el nmero de elementos de cada clase para l$egoordenarlos& Sólo p$ede ser $tili5ado por tanto para ordenar elementos +$e seancontables (como los nmeros enteros en $n determinado inter-alo pero no losnmeros reales por e%emplo)&
El primer paso consiste en a-erig$ar c$/l es el inter-alo dentro del +$e est/nlos datos a ordenar (-alores m6nimo . m/,imo)& Desp$s se crea $n -ector denmeros enteros con tantos elementos como -alores 'a.a en el inter-alo
Jm6nimo m/,imoK . a cada elemento se le da el -alor ( apariciones)& Trasesto se recorren todos los elementos a ordenar . se c$enta el nmero deapariciones de cada elemento ($sando el -ector +$e 'emos creado)& ;or ltimobasta con recorrer este -ector para tener todos los elementos ordenados&
E%emplo
#onsidrese la sig$iente lista de nmeros8
Lista sin ordenar8 2 U Q 2 U Q 2 2
;ara ordenarla con este algoritmo seg$imos estos pasos8
• @$scar el m6nimo . el m/,imo
"6nimo I 2
"/,imo I
• #rear el -ector a$,iliar
-a$, I n$e-o -ector (2) de enteros
• Recorrer la lista de nmeros . contar elementos debe 0i%arse como el -alor
en la lista de entrada se $sa como 6ndice en el -ector a$,iliar
Al 0inal
-A$,(2) I por+$e aparece -eces en la lista
-A$,(Q) I 2 F F 2 F F
8/16/2019 120283Tarea Sobre Ordenacion Algo3
http://slidepdf.com/reader/full/120283tarea-sobre-ordenacion-algo3 12/16
-A$,() I por+$e no aparece en la lista ning$na -e5
-A$,(U) I 2 por+$e aparece 2 -eces en la lista
-A$,() I por+$e no aparece en la lista ning$na -e5
-A$,() I 1 por+$e aparece 1 -e5 en la lista
• Recorriendo el -ector a$,iliar obtenemos la lista de nmeros ordenada
lista=alores() I 2 El -alor 2 se repite -eces&
lista=alores(1) I 2
lista=alores(2) I 2
lista=alores(Q) I 2
:
lista=alores() I Q El -alor Q se repite 2 -eces lista=alores(U) I Q
:
lista=alores() I U El -alor U se repite 2 -eces
lista=alores() I U
:
lista=alores() I El -alor sólo aparece 1 -e5
:
:
Lista ordenada I 2 2 2 2 Q Q U U
#aracter6sticas
Se trata de $n algoritmo estable c$.a comple%idad comp$tacional es O(nC)
siendo n el nmero de elementos a ordenar . el tamao del -ector a$,iliar
(m/,imo : m6nimo)&
La e0iciencia del algoritmo es independiente de lo casi ordenado +$e est$-iera
anteriormente& Es decir no e,iste $n me%or . peor caso todos los casos se tratan
ig$ales&
El algoritmo co$nting no se ordena in sit$ sino +$e re+$iere de $na memoria
adicional&
LimitacionesJeditarK
El algoritmo posee $na serie de limitaciones +$e obliga a +$e sólo p$eda ser
$tili5ado en determinadas circ$nstancias&
8/16/2019 120283Tarea Sobre Ordenacion Algo3
http://slidepdf.com/reader/full/120283tarea-sobre-ordenacion-algo3 13/16
Sólo ordena nmeros enteros no -ale para ordenar cadenas . es desaconse%able
para ordenar nmeros decimales& Teóricamente se p$ede pero deber6a recrear en la
matri5 a$,iliar tantas posiciones como decimales +$epan entre 2 nmeros
consec$ti-os si se restringe a 1 o 2 decimales podr6a ser ase+$ible $n nmero
ma.or de decimales p$ede llegar a s$poner $na memoria a$,iliar impracticable&
Otra limitación (por ine0iciencia) incl$so con nmeros enteros es c$ando el rango
entre el ma.or . el menor es m$. grande& !maginemos $na lista de 1 elementos
donde el menor es el . el ma.or 12QU& Ordenar esta lista s$pondr6a crear
$na matri5 a$,iliar de 12QU elementos& 4na cantidad m$. ele-ada de memoria
para ordenar sólo 1 elementos& Tambin s$pondr6a $n desperdicio de tiempo p$es
la matri5 a$,iliar para tras-asar a la lista ordenada debe recorrerse entera
a$n+$e sólo se reasignar/n 1 -alores de los 12QU elementos&
#on leng$a%es de programación +$e no permitan de0inir -ectores c$.o primer 6ndice
sea $n -alor distinto de o 1 es necesario reali5ar $na trad$cción de los
-alores& ;or e%emplo si el inter-alo es (1) . el -ector a$,iliar comprende el
rango (1:) para cada elemento se deber/ incrementar el contador de la posición
en Q&
4n modo de 'acer este algoritmo m/s pr/ctico es g$ardar -arios elementos en $n
6ndice de la matri5 pero en este caso la matri5 .a no es de -alores enteros sino
+$e contiene algn tipo de estr$ct$ra de datos& As6 es posible por e%emploordenar nmeros con decimales& ;or e%emplo si en la matri5 a$,iliar en el 6ndice
U metemos todas las apariciones de la lista c$.o -alor est/ en el rango U& :
U&& L$ego con cada elemento en cada 6ndice se reali5a $n n$e-o ordenamiento&
c$ando se $san este tipo de tcnicas el algoritmo .a se considera otro
denominado8 b$cet sort&
;se$docódigo
Se 'an aadido los comentarios pertinentes para aclarar las partes +$e 0$eren m/s
d$dosas&
comentario8 lista=alores es $na matri5 de -alores enteros& Entrada B$nción co$nting<sort(lista=alores) Lista=ariables min=alor comentario8 el -alor del elemento menor en la lista ma,=alor comentario8 el -alor del elemento ma.or en la lista -A$, comentario8 $na matri5 de elementos a$,iliar de tantoelementos como
de0ine el rango min=alor a ma,=alori % n comentario8 contadores de b$cle
-alor comentario8 -alor del elemento act$al en el b$cle
8/16/2019 120283Tarea Sobre Ordenacion Algo3
http://slidepdf.com/reader/full/120283tarea-sobre-ordenacion-algo3 14/16
tamao comentario8 cantidad de elementos en lista=alores
;re-ioscomentario8 @$scar -alor m6nimo . m/,imo
LlamadaaB$ncion @$scarLimites(lista=alores min=alor ma,=alor)
comentario8 #rea el -ector a$,iliar con todos s$s elementos a -A$, I N$e-o=ector(min=alorma,=alor)
comentario8 Obtiene la cantidad de elementos +$e contiene la matri5 tamao I TotalElementosEn(lista=alores)
comentario8 #ontar elementos& En el 6ndice e,presado por el -alor se-an contando las -eces +$e aparece dic'o -alor en la matri5 de entrada
comentario8 Este b$cle reali5a $na matri5 de conteo cada -alor indicac$antas -eces aparece el -alor representado por el 6ndice en la lista de
-alores& !nicioi I 3acer "ientras (i ? tamao)
-alor I lista=alores(i) -A$,(-alorK I -A$,(-alor) C 1 i I i C 1 Repetir
comentario8 Tras-asar la matri5 de conteo a la lista +$e +$eda as6 .aordenada
i I min=alor
% I 3acer "ientras (i ? ma,=alor) comentario8 Si para el 6ndice ViV se contó 1 o m/s elementostrans0erir a la lista
Si -A$,(i) 9 Entonces;ara n Repetir Desde 1 3asta -A$,(i)
lista=alores(%) I i% I % C 1
Sig$iente n Bin si Repetir
Bin Salida B$nción
comentario8 Esta 0$nción a$,iliar b$sca . de-$el-e el ma.or . menor elementosde $na matri5 Entrada B$nción @$scarLimites(lista=alores min=alor ma,=alor) =ariables i comentario8 contador del b$cle
!nicio min=alor I lista=alores() ma,=alor I min=alor
;ara i Repetir Desde 1 3asta TotalElementosEn(Lista=alores) Si lista=alores(i) ? min=alor entonces
min=alor I lista=alores(i)
8/16/2019 120283Tarea Sobre Ordenacion Algo3
http://slidepdf.com/reader/full/120283tarea-sobre-ordenacion-algo3 15/16
W Si lista=alores(i) 9 ma,=alor entonces ma,=alor I lista=alores(i) Bin Si Sig$iente i Bin
Salida B$nción
ORDENAMIENTO RADI (RADI SORT)
En in0orm/tica el ordenamiento Radi, (radi, sort en ingls) es $n algoritmo deordenamiento +$e ordena enteros procesando s$s d6gitos de 0orma indi-id$al& #omolos enteros p$eden representar cadenas de caracteres (por e%emplo nombres o0ec'as) . especialmente nmeros en p$nto 0lotante especialmente0ormateados radi, sort no est/ limitado sólo a los enteros&
La ma.or parte de los ordenadores digitales representan internamente todos s$sdatos como representaciones electrónicas de nmeros binarios por lo +$e procesarlos d6gitos de las representaciones de enteros por representaciones de gr$pos ded6gitos binarios es lo m/s con-eniente& E,isten dos clasi0icaciones de radi,sort8 el de d6gito menos signi0icati-o (LSD) . el de d6gito m/s signi0icati-o("SD)& Radi, sort LSD procesa las representaciones de enteros empe5ando por eld6gito menos signi0icati-o . mo-indose 'acia el d6gito m/s signi0icati-o& Radi,sort "SD traba%a en sentido contrario&
Las representaciones de enteros +$e son procesadas por los algoritmos deordenamiento se les llama a men$do Fcla-esF +$e p$eden e,istir por s6 mismas oasociadas a otros datos& Radi, sort LSD $sa t6picamente el sig$iente orden8cla-es cortas aparecen antes +$e las cla-es largas . cla-es de la misma longit$dson ordenadas de 0orma l,ica& Esto coincide con el orden normal de lasrepresentaciones de enteros como la sec$encia F1 2 Q U 1F& Radi, sorts "SD $sa orden l,ico +$e es ideal para la ordenación de cadenasde caracteres como las palabras o representaciones de enteros de longit$d 0i%a&4na sec$encia como Fb c d e 0 g ' i % baF ser/ ordenada l,icamente comoFb ba c d e 0 g ' i %F& Si se $sa orden l,ico para ordenarrepresentaciones de enteros de longit$d -ariable entonces la ordenación de lasrepresentaciones de los nmeros del 1 al 1 ser/ F1 1 2 Q U Fcomo si las cla-es m/s cortas est$-ieran %$sti0icadas a la i5+$ierda . rellenadasa la derec'a con espacios en blanco para 'acerlas tan largas como la cla-e m/slarga para el propósito de este ordenamiento& cabe destacar +$e este mtodo no0$nciona para la estr$ct$ra de datos debido a +$e los ciclos 0or +$e seimplementaran marcaran error debido a las matrices bidimensionales&
8/16/2019 120283Tarea Sobre Ordenacion Algo3
http://slidepdf.com/reader/full/120283tarea-sobre-ordenacion-algo3 16/16
EXE";LO
=ector original8
2U U Q 12 2 QQ
Asignamos los elementos en colas basadas en el d6gito menos signi0icati-o de cada$no de ellos&
8
18
2812 2
Q8QQ
8
U82U
8
8U Q8
8
Desp$s de la primera pasada la ordenación +$eda8
12 2 QQ 2U U Q
#olas basadas en el d6gito m/s signi0icati-o&
81812
282U
Q8QQ Q
8
U8U
8
8
8
82
Lista ordenada8
12 2U QQ Q U 2