Algoritmos de Ordenamiento ( Counting Sort, Bucket sort, radix sort, string sort
Jérémy Barbay 5 Oct 201005/10/10 a las 17:17 hrs.2010-10-05 17:17:05
Algoritmos de Ordenamiento ( Counting Sort, Bucket sort, radix sort, string sort)
=================================================================================
Author: Jérémy Barbay
Date: 2010-10-05 20:47:32 XXX
SCHEDULED: <2010-10-05 Tue 12:00-13:30>
Table of Contents
=================
1 Counting Sort O(\sigma + n)
2 Bucket Sort O(\sigma+n)
3 Radix Sort O(n \lg_n \sigma) = O(c n)
4 BONUS Prevechando de las repeticiones en el modelo de Comparaciones
5 BONUS String Sort
1 Counting Sort O(\sigma + n)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1. for j=1 to \sigma do C[j] <- 0
2. for i=1 to n do C[A[i]]++
3. p<-1
4. for j=1 to \sigma do
- for i=1 to C[j] do
- A[p++] <- j
Este algoritmo es bueno para ordenar multi conjuntos (donde
cada elementos puede ser presente muchas veces), pero pobre
para diccionarios, para cual es mejor usar la extensión
lógica, Bucket Sort.
2 Bucket Sort O(\sigma+n)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1. for j=1 to \sigma do C[j] <- 0
2. for i=1 to n do C[A[i]]++
3. P[1] <- 1
4. for j<- 2 to \sigma do
- P[j] <- P[j-1] + C[j-1]
5. for i<-1 to n
- B[P[A[i]]++] <- A[i]
Este algoritmo es particularmente practica para ordenar
llaves asociadas con objetos, donde dos llaves pueden ser
asociadas con algunas valores distintas. Nota que el
ordenamiento es *estable*.
3 Radix Sort O(n \lg_n \sigma) = O(c n)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
- Considera un arreglo A de tamaño n sobre alfabeto $\sigma$
- si $\sigma=n$, se recuerdan que bucket sort puede
ordenar A en O(n)
- si $\sigma=n^2$, bucket sort puede ordenar A en O(n):
- 1 ves con los $\lg n$ bits de la derecha
- 1 ves con los $\lg n$ bits de la izquierda
(utilizando la estabilidad de bucket sort)
- si $|A|=n^c$, bucket sort puede ordenar A
- en tiempo $O(cn)$
- con espacio 2n + \sigma \approx 3n
(\sigma \approx n a cada iteración de bucket sort)
El espacio se puede reducir a 2n+\sqrt{n} con \lg n/ 2
bits a cada iteración de Bucketsort, cambiando la
complejidad solamente por un factor de 2.
En final, si $A$ es de tamaño $n$ sobre un alfabeto de
tamaño $\sigma$, radix sort puede ordenar $A$ en tiempo
O( n \lceil \frac{\lg \sigma}{\lg n}\rceil )
4 BONUS Prevechando de las repeticiones en el modelo de Comparaciones
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
- Se puede o no?
- Ordenar en $n H_i$ comparaciones
5 BONUS String Sort
~~~~~~~~~~~~~~~~~~~~
+ Problema: Ordenar $k$ strings sobre alfabeto [\sigma], de
largo total n=\sum n_i.
+ Si \sigma \leq k, y cada string es de mismo tamaño.
- Si utilizamos bucket-sort de la derecha a la izquierda,
podemos ordenar en tiempo $O(n)$, porque O(n \lceil \lg
\sigma/\lg l \rceil ) y \sigma<n.
+ Si \sigma \in O(1)
- Radix Sort sobre $c$ simboles, donde $c$ es el tamaño
mínima de una string, y iterar recursivamente sobre el
restos de la strings mas grande con mismo prefijo.
- En el peor caso, la complejidad corresponde a la suma de
las superficias de los bloques, aka O(n).
[1] FOOTNOTE DEFINITION NOT FOUND: 1
=================================================================================
Author: Jérémy Barbay
Date: 2010-10-05 20:47:32 XXX
SCHEDULED: <2010-10-05 Tue 12:00-13:30>
Table of Contents
=================
1 Counting Sort O(\sigma + n)
2 Bucket Sort O(\sigma+n)
3 Radix Sort O(n \lg_n \sigma) = O(c n)
4 BONUS Prevechando de las repeticiones en el modelo de Comparaciones
5 BONUS String Sort
1 Counting Sort O(\sigma + n)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1. for j=1 to \sigma do C[j] <- 0
2. for i=1 to n do C[A[i]]++
3. p<-1
4. for j=1 to \sigma do
- for i=1 to C[j] do
- A[p++] <- j
Este algoritmo es bueno para ordenar multi conjuntos (donde
cada elementos puede ser presente muchas veces), pero pobre
para diccionarios, para cual es mejor usar la extensión
lógica, Bucket Sort.
2 Bucket Sort O(\sigma+n)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1. for j=1 to \sigma do C[j] <- 0
2. for i=1 to n do C[A[i]]++
3. P[1] <- 1
4. for j<- 2 to \sigma do
- P[j] <- P[j-1] + C[j-1]
5. for i<-1 to n
- B[P[A[i]]++] <- A[i]
Este algoritmo es particularmente practica para ordenar
llaves asociadas con objetos, donde dos llaves pueden ser
asociadas con algunas valores distintas. Nota que el
ordenamiento es *estable*.
3 Radix Sort O(n \lg_n \sigma) = O(c n)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
- Considera un arreglo A de tamaño n sobre alfabeto $\sigma$
- si $\sigma=n$, se recuerdan que bucket sort puede
ordenar A en O(n)
- si $\sigma=n^2$, bucket sort puede ordenar A en O(n):
- 1 ves con los $\lg n$ bits de la derecha
- 1 ves con los $\lg n$ bits de la izquierda
(utilizando la estabilidad de bucket sort)
- si $|A|=n^c$, bucket sort puede ordenar A
- en tiempo $O(cn)$
- con espacio 2n + \sigma \approx 3n
(\sigma \approx n a cada iteración de bucket sort)
El espacio se puede reducir a 2n+\sqrt{n} con \lg n/ 2
bits a cada iteración de Bucketsort, cambiando la
complejidad solamente por un factor de 2.
En final, si $A$ es de tamaño $n$ sobre un alfabeto de
tamaño $\sigma$, radix sort puede ordenar $A$ en tiempo
O( n \lceil \frac{\lg \sigma}{\lg n}\rceil )
4 BONUS Prevechando de las repeticiones en el modelo de Comparaciones
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
- Se puede o no?
- Ordenar en $n H_i$ comparaciones
5 BONUS String Sort
~~~~~~~~~~~~~~~~~~~~
+ Problema: Ordenar $k$ strings sobre alfabeto [\sigma], de
largo total n=\sum n_i.
+ Si \sigma \leq k, y cada string es de mismo tamaño.
- Si utilizamos bucket-sort de la derecha a la izquierda,
podemos ordenar en tiempo $O(n)$, porque O(n \lceil \lg
\sigma/\lg l \rceil ) y \sigma<n.
+ Si \sigma \in O(1)
- Radix Sort sobre $c$ simboles, donde $c$ es el tamaño
mínima de una string, y iterar recursivamente sobre el
restos de la strings mas grande con mismo prefijo.
- En el peor caso, la complejidad corresponde a la suma de
las superficias de los bloques, aka O(n).
[1] FOOTNOTE DEFINITION NOT FOUND: 1
| Última Modificación | 5 Oct 201005/10/10 a las 17:17 hrs.2010-10-05 17:17:05 |
|---|---|
| Vistas Únicas | 3 |
| Compartir |
