D R . J E S Ú S A . G O N Z Á L E Z B E R N A L C I E N C I A S C O M P U T A C I O N A L E S

I N A O E

Análisis y Diseño de Algoritmos

Ordenamiento en Tiempo Lineal

2

Ordenamiento por Comparación (Comparison Sorts)

�  Tiempo de ejecución ¡  HeapSort y MergeSort, O(nlgn), peor caso ¡  QuickSort, O(nlgn), caso promedio

�  Para alguna entrada ¡  Ω(nlgn)

�  Los algoritmos anteriores comparten una característica ¡  El orden que determinan se basa en comparaciones entre los

elementos de entrada ¡  Los conocemos como “ordenamiento basado en

comparaciones” ó “comparison sorts”

2

3

Ordenamiento Lineal (Linear Sorting)

�  No se basan en comparaciones ¡  Counting Sort ¡  Radix Sort ¡  Bucket Sort

3

4

Cotas Inferiores para Ordenamiento

�  En “comparison sort”, comparamos elementos ¡  Dados 2 elementos ai y aj probamos:

÷ ai < aj, ai ≤ aj, ai = aj, ai ≥ aj ó ai > aj para determinar orden relativo

÷ No verificamos los valores de otra forma

�  Para algoritmos lineales ¡  Si asumimos entradas únicas, no serían necesarias las

comparaciones “=“ ÷ Quedan sólo comparaciones de la forma ai ≤ aj

4

5

Modelo de Árboles de Decisión

�  Ordenamientos de comparación se ven en términos de árboles de decisión ¡  Árbol binario completo que representa comparaciones hechas

por un alg. de ordenamiento particular sobre una entrada de determinado tamaño

¡  Se ignora el control, movimientos de datos y otros aspectos del algoritmo

5

Árbol de Decisión para Insertion Sort con 3 Valores

�  Nodo interno anotado como i:j, i y j en el rango [1..n] �  Hojas anotadas por una permutación <π(1), π(2), …, π(n)>

�  La ejecución del alg. de ord à ruta de la raíz a hoja

6

n = 3 Entrada: <a1=6, a2=8, a3=5> Posibles salidas: 3!

Counting Sort

�  Asume entrada de n elementos enteros en rango de 0 a k

�  Cuando k = O(n), ordenamiento corre en Θ(n) �  Determina para cada elemento de entrada x, el # de

elementos menores de x ¡  Así posiciona a x en su lugar en el arreglo de salida ¡  Si hay 17 elementos menores a x à x va en el lugar 18 ¡  Manejo de números repetidos

7

Algoritmo Counting Sort 8

�  A[j] à Elemento del arreglo original �  C[A[j]] à # de repeticiones del número en A[j] �  B[C[A[j]]] à Arreglo final, pone el número en la posición final

Ejemplo de Counting Sort 9

Análisis de Counting Sort 10

�  Ciclo for líneas 1-2 toma Θ(k) �  Ciclo for líneas 3-4 toma Θ(n) �  Ciclo for líneas 9-11 toma Θ(n) �  Tiempo total es Θ(k+n)

¡  En general usamos counting sort cuando tenemos k = O(n) ÷ Tiempo de ejecución Θ(n)

�  Mejora la cota inferior Ω(nlgn) porque no es un algoritmo de ordenamiento por comparación ¡  No hace comparaciones entre elementos ¡  Usa los valores de los elementos para indexarlos en el arreglo

Análisis Counting Sort 11

�  Algoritmo estable ¡  Números con el mismo valor aparecen en la salida en el mismo

orden en que estaban en el arreglo de entrada ¡  Propiedad importante cuando hay datos asociados con el

elemento que se ordena ¡  Counting Sort se utiliza como subrutina de Radix Sort ¡  La estabilidad de Counting Sort es importante para que Radix

Sort sea un algoritmo correcto

Radix Sort 12

�  Originalmente utilizado para ordenar juegos de cartas perforadas (IBM) ¡  Los ordenadores de tarjetas trabajaban una columna a la

vez

�  Actualmente se utiliza para ordenamientos multi-llave (p.e. año/mes/día)

�  Considera cada dígito del número como una llave independiente

Radix Sort 13

�  ¿Cómo ordenamos? ¡  Primero ordena el dígito más significativo n, luego el dígito

n-2, etc. ÷ Problema: podemos ordenar en 10 conjuntos (uno por dígito) pero

para ordenamientos recursivos subsecuentes requerimos los 10 conjuntos y se debería mantener los otros 9 montones.

¡  Podemos ordenar del dígito menos significativo al más significativo

Ejemplo de Radix Sort 14

Algoritmo de Radix Sort 15

�  d es el número de dígitos ¡  el dígito 1, es el de orden más bajo ¡  el dígito d es el de mayor orden

Análisis de Radix Sort 16

�  Si cada dígito esta en el rango de 1 a k, usamos CountingSort

�  Cada paso por un dígito toma Θ(n + k) �  Para d dígitos Θ(dn + dk) �  Si d es una constante y k = O(n), T(n) = O(n) �  Radix-n significa que cada dígito puede diferenciar

entre n símbolos diferentes, en ejemplos anteriores utilizamos radix-10 (dígitos del 0 al 9).

Precisión 17

�  ¿Porqué pasadas posteriores no desacomodan los ordenamientos previos?

�  Probar que después de la pasada p, ordenando para el dígito p+1 hacia el último dígito ¡  Por inducción sobre p

÷ Verdadero para p=1, aplicamos sort estable al dígito 1, ordenado después de la primera pasada

÷ Asumimos verdadero para p=1 y probamos para p=i+1 ÷ Después de la pasada i, comparamos dos números x y y ÷  Si x esta antes que y, pasó una de estas dos condiciones

¢  x < y para el dígito i, à x va antes que y en orden ¢  x = y para el dígito i, à x < y para el resto del número, ubicado en

ese orden en una pasada anterior, no fue intercambiado por el uso de un ordenamiento estable

Ejemplo 18

�  Pruebe que n enteros en el rango de 1 a n2 se pueden ordenar en tiempo O(n)

�  El número de dígitos utilizado para representar n2 números diferentes en un sistema de números k-ario es: logk(n2) ¡  Entonces, considerando los n2 números como números en radix-n,

tenemos: ¡  d=logn(n2)=2logn(n)=2 ¡  Entonces necesitamos 2 dígitos, d = 2 ¡  Cada dígito requiere n símbolos (radix-n) , por lo que k=n ¡  T(n)= Θ(d(n + k)) = Θ(2(n + n)) = Θ(n).

Bucket Sort 19

�  Corre en tiempo lineal cuando la entrada se toma de una distribución uniforme

�  Rápido porque asume algo sobre la entrada (como counting sort, asume números en un rango pequeño) ¡  Bucket Sort asume números generados aleatoriamente y

distribuidos uniformemente en un rango de [o,1)

�  Divide el intervalo de [0,1) en n sub-intervalos de igual tamaño ¡  Se ordenan los números en cada partición ¡  Se recorren las particiones en orden listando los elementos

Algoritmo Bucket Sort 20

Ejemplo de Bucket Sort 21

Análisis Bucket Sort 22

1.  BucketSort(A) COST*TIMES 2.  n = length(A) 1 3.  for i = 1 to n n+1 4.  insert(A[i], B[floor(nA[i])] n 5.  for i = 0 to n-1 n +1 6.  InsertionSort(B[i]) n*T(InsertionSort) 7.  return (B[0],B[1], …, B[n-1]) n

Análisis Bucket Sort 23

�  TBS = 4n + TISn + 3 �  Sea ni = número de elementos en partición B[i] �  El tiempo esperado para ordenar los elementos en B[i] = E(O(ni

2)) = O(E(ni

2)). �  Note que el valor esperado de una variable aleatoria X como se describe

en el capítulo 6 es:

¡  La variable x representa el valor de X, y Pr(X=x) la probabilidad de que el valor de X sea x

�  La varianza de una variable aleatoria X con media E[X] se denota como Var[X]

∑ ==x

xXxXE )Pr()(

intentos para binomial óndistribucila esesta ,)(

][][][ 22

nqpkn

kXP

XEXVarXE

knk −⎟⎟⎠

⎞⎜⎜⎝

⎛==

+=

Análisis Bucket Sort 24

�  Para todas las particiones, �  Dados

¡  n elementos, uniformemente distribuidos sobre todos los posibles valores

¡  n particiones

�  ¿Cuál es la probabilidad de que un elemento sea insertado en la partición i? ¡  P=1/n.

�  Dados n intentos que consisten en poner elementos en las particiones, ¿cuántos elementos se insertarán en la partición i?

∑ ∑−

=

−

=

=1

0

1

0

22 )).(())((n

i

n

iii nEOnEO

Análisis Bucket Sort 25

)1(/12

1/11)(

/11)1()( y varianza1)( mediacon

),(

22

Θ=

−=

+−=

−=−=

==

=

nnnE

npnpnVarnpnEpnBinomialn

i

i

i

i

�  Por tanto, TIS = Θ(1) �  y TBS = 4n + Θ(1)n + 3 = O(n) para el caso promedio.

En el peor caso, el tiempo de ejecución es n2.

Aplicaciones de Bucket Sort

�  GPU bucket sort algorithm with applications to nearest-neighbour search, by T. Rozen, K. Boryczko, W. Alda ¡  http://wscg.zcu.cz/WSCG2008/Papers_2008/journal/G07-

full.pdf

26