Algoritmos de ordenación

Ordenación o clasificación es el proceso de reordenar un conjunto de objetos en un orden específico. El propósito de la ordenación es facilitar la búsqueda de elementos en el conjunto ordenado.
Existen muchos algoritmos de ordenación, siendo la diferencia entre ellos las ventajas de unos sobre otros en la eficiencia en tiempo de ejecución.

1. 1
Ordenación, Clasificación
•Introducción
•Algoritmos
•Complejidad

2. 2
Introducción
•Ordenaciónoclasificacióneselprocesode
reordenarunconjuntodeobjetosenunorden
específico.Elpropósitodelaordenaciónes
facilitarlabúsquedadeelementosenelconjunto
ordenado.
•Existenmuchosalgoritmosdeordenación,siendo
ladiferenciaentreelloslasventajasdeunossobre
otrosenlaeficienciaentiempodeejecución.

3. 3
Introducción
•Los métodos de ordenación se pueden clasificar en
dos categorías:
–ordenación de ficheros y
–ordenación de arrays.
También suele llamarse ordenamiento externo e
interno, debido a que los ficheros se guardan en
la memoria externa (lenta) mientras que los
arrays se almacenan en la memoria rápida del
ordenador (interna). En esta sección sólo se
aborda el ordenamiento interno.

4. 4
Introducción
•Elproblemadelordenamientopuedeestablecerse
mediantelasiguienteación:
Dadosloselementos:
Ordenarconsisteenpermutaresoselementosen
unorden:
talquedadaunafuncióndeordenamientof:nkkk
aaa ,,,
21
 )()()(
21 nkkk
afafaf   naaa ,,,
21

5. 5
Introducción
•Normalmente, la función de ordenamiento no es
evaluada de acuerdo a una regla de computación
determinada, pero se guarda como un componente
explícito (campo) de cada item (elemento). El valor de
ese campo se llama la llavedel item.
•Unmétododeordenamientoesestablesielorden
relativodeelementosconigualllavepermanece
inalteradoporelprocesodeordenamiento.
•Seentiendequelosmétodosdeordenamientobuscan
unusoeficientedelamemoriaporloquelas
permutacionesdeelementosseharáinsitu,esdecir,
usandoelmismocontenedororiginal.

6. 6
Introducción
•Enloquesigueseconsideraquelaestructura
lineal(array,lista,vectorosecuencia)aordenarse
representaporunarraydeobjetos(números
enteros):
int a[ ] = new int[MAX];
•siendo MAX el número máximo de elementos del
array. El orden de los elementos después de la
ordenación se considera ascendente.

7. 7
Algoritmo burbuja
•Esunmétodocaracterizadoporlacomparacióne
intercambiodeparesdeelementoshastaquetodos
loselementosesténordenados.
•Encadaiteraciónsecolocaelelementomás
pequeño(ordenascendente)ensulugarcorrecto,
cambiándoseademáslaposicióndelosdemás
elementosdelarray.

8. 8
Algoritmo burbujaDatos
originales1ª iter.2ª 3ª 4ª
36 6 6 6 6
24 36 10 10 10
10 24 36 12 12
6 10 24 36 24
12 12 12 24 36

9. 9
Algoritmo burbujaDatos
originales1ª iter.2ª 3ª 4ª
36 6 6 6 6
24 36 10 10 10
10 24 36 12 12
6 10 24 36 24
12 12 12 24 36

10. 10
Algoritmo burbujaDatos
originales1ª iter.2ª 3ª 4ª
36 6 6 6 6
24 36 10 10 10
10 24 36 12 12
6 10 24 36 24
12 12 12 24 36

11. 11
Algoritmo burbujaDatos
originales1ª iter.2ª 3ª 4ª
36 6 6 6 6
24 36 10 10 10
10 24 36 12 12
6 10 24 36 24
12 12 12 24 36

12. 12
Algoritmo burbujaDatos
originales1ª iter.2ª 3ª 4ª
36 6 6 6 6
24 36 10 10 10
10 24 36 12 12
6 10 24 36 24
12 12 12 24 36

13. 13
Algoritmo burbuja
for(i=n;i>0;i--)
for(j=0;j<i-1;j++)
if (a[j] > a[j+1])
{
t=a[j];
a[j] = a[j+1];
a[j+1]=t;
ninterc++;
}

14. 14
Algoritmo sacudida (shakesort)
•Esunamejoradelalgoritmodeburbujaenelque
seregistralaocurrenciadeunintercambioyel
índicedelúltimointercambioysealternala
direccióndelaspasadasconsecutivas.Conello
unaburbujalivianaenellado“pesado”yuna
pesadaenellado“liviano”quedaránenordenen
unapasadasimple.

15. 15
Algoritmo sacudida (shakesort)
l=1; r=n-1; k=n-1;
do
{
for(j=r; j>=l; j--)
if (a[j-1]>a[j])
{
t=a[j-1];
a[j-1] = a[j];
a[j]=t;
k=j;
ninterc++;
}
l=k+1;
for(j=l; j<=r; j++)
if (a[j-1]>a[j])
{
t=a[j-1];
a[j-1] = a[j];
a[j]=t;
k=j;
ninterc++;
}
r=k-1;
}
while (l<r);

16. 16
Algoritmo inserción
•Estemétodoesusadoporlosjugadoresdecartas.
Loselementosestándivididosconceptualmenteen
unasecuenciadestinoyunasecuenciafuente.En
cadapaso,comenzandoconi=2eincrementandoi
enuno,elelementoi-ésimodelasecuenciafuente
setomaysetransfierealasecuenciadestino
insertándoloenellugaradecuado.
•En otras palabras, en el i-ésimo paso insertamos el
i-ésimo elemento a[i] en su lugar correcto entre
a[1], a[2],…., a[i-1], que fueron colocados en
orden previamente.

17. 17
Algoritmo inserciónArray
original:4455124294180667
i=2 4455124294180667
i=3 1244554294180667
i=4 1242445594180667
i=5 1242445594180667
i=6 1218424455940667
i=7 0612184244559467
i=8 0612184244556794

18. 18
Algoritmo inserciónArray
original:4455124294180667
i=2 4455124294180667
i=3 1244554294180667
i=4 1242445594180667
i=5 1242445594180667
i=6 1218424455940667
i=7 0612184244559467
i=8 0612184244556794

19. 19
Algoritmo inserciónArray
original:4455124294180667
i=2 4455124294180667
i=3 1244554294180667
i=4 1242445594180667
i=5 1242445594180667
i=6 1218424455940667
i=7 0612184244559467
i=8 0612184244556794

20. 20
Algoritmo inserciónArray
original:4455124294180667
i=2 4455124294180667
i=3 1244554294180667
i=4 1242445594180667
i=5 1242445594180667
i=6 1218424455940667
i=7 0612184244559467
i=8 0612184244556794

21. 21
Algoritmo inserciónArray
original:4455124294180667
i=2 4455124294180667
i=3 1244554294180667
i=4 1242445594180667
i=5 1242445594180667
i=6 1218424455940667
i=7 0612184244559467
i=8 0612184244556794

22. 22
Algoritmo inserciónArray
original:4455124294180667
i=2 4455124294180667
i=3 1244554294180667
i=4 1242445594180667
i=5 1242445594180667
i=6 1218424455940667
i=7 0612184244559467
i=8 0612184244556794

23. 23
Algoritmo inserciónArray
original:4455124294180667
i=2 4455124294180667
i=3 1244554294180667
i=4 1242445594180667
i=5 1242445594180667
i=6 1218424455940667
i=7 0612184244559467
i=8 0612184244556794

24. 24
Algoritmo inserciónArray
original:4455124294180667
i=2 4455124294180667
i=3 1244554294180667
i=4 1242445594180667
i=5 1242445594180667
i=6 1218424455940667
i=7 0612184244559467
i=8 0612184244556794

25. 25
Algoritmo inserción
for(i=1;i<n;i++)
{
j=i-1;
t=a[i];
while (j>=0 && t<a[j])
{
a[j+1] = a[j];
j=j-1;
}
a[j+1]=t;
}

26. 26
Algoritmo selección
•Enéstemétodo,eneli-ésimopasoseleccionamos
elelementoconlallavedemenorvalor,entre
a[i],…,a[n]ylointercambiamoscona[i].Como
resultado,despuésdeipasadas,eli-ésimo
elementomenorocuparáa[1],…,a[i]enellugar
ordenado.

27. 27
Algoritmo selecciónArray
original:4455124294180667
i=2 0655124294184467
i=3 0612554294184467
i=4 0612184294554467
i=5 0612184294554467
i=6 0612184244559467
i=7 0612184244559467
i=8 0612184244556794

28. 28
Algoritmo selecciónArray
original:4455124294180667
i=2 0655124294184467
i=3 0612554294184467
i=4 0612184294554467
i=5 0612184294554467
i=6 0612184244559467
i=7 0612184244559467
i=8 0612184244556794

29. 29
Algoritmo selecciónArray
original:4455124294180667
i=2 0655124294184467
i=3 0612554294184467
i=4 0612184294554467
i=5 0612184294554467
i=6 0612184244559467
i=7 0612184244559467
i=8 0612184244556794

30. 30
Algoritmo selecciónArray
original:4455124294180667
i=2 0655124294184467
i=3 0612554294184467
i=4 0612184294554467
i=5 0612184294554467
i=6 0612184244559467
i=7 0612184244559467
i=8 0612184244556794

31. 31
Algoritmo selecciónArray
original:4455124294180667
i=2 0655124294184467
i=3 0612554294184467
i=4 0612184294554467
i=5 0612184294554467
i=6 0612184244559467
i=7 0612184244559467
i=8 0612184244556794

32. 32
Algoritmo selecciónArray
original:4455124294180667
i=2 0655124294184467
i=3 0612554294184467
i=4 0612184294554467
i=5 0612184294554467
i=6 0612184244559467
i=7 0612184244559467
i=8 0612184244556794

33. 33
Algoritmo selecciónArray
original:4455124294180667
i=2 0655124294184467
i=3 0612554294184467
i=4 0612184294554467
i=5 0612184294554467
i=6 0612184244559467
i=7 0612184244559467
i=8 0612184244556794

34. 34
Algoritmo selecciónArray
original:4455124294180667
i=2 0655124294184467
i=3 0612554294184467
i=4 0612184294554467
i=5 0612184294554467
i=6 0612184244559467
i=7 0612184244559467
i=8 0612184244556794

35. 35
Algoritmo selección
for(i=0;i<n-1;i++)
{
k=i;
t=a[i];
for (j=i+1; j<n; j++)
{
if (a[j] < t)
{
t= a[j];
k=j;
}
a[k]= a[i];
a[i]= t;
}
}

36. 36
Algoritmo rápido (Quicksort)
•Laordenaciónrápidasebasaenelhechoquelos
intercambiosdebenserrealizadospreferentemente
sobredistanciasgrandes.
•Elalgoritmoaseguireselmismoqueseaplica
cuandosequiereordenarungranmontónde
exámenes:
–Seleccionarunvalordedivisión(Lporejemplo)y
dividirelmontónendospilas,A-LyM-Z.Despuésse
tomalaprimerapilaysesubdivideendos,A-FyG-L
porejemplo.AsuvezlapilaA-Fpuedesubdividirse
enA-CyD-F.Esteprocesocontinúahastaquelas
pilasseansuficientementepequeñasparaordenarlas
fácilmente.Elmismoprocesoseaplicaalaotrapila.

37. 37
Algoritmo rápido (Quicksort)
•En este caso se toma un elemento x del array (el
del medio por ejemplo), se busca en el array desde
la izquierda hasta que >x, lo mismo se hace desde
la derecha hasta encontrar <x.
•Después se intercambia esos elementos y se
continúa ese proceso hasta que los índices se
encuentren en la mitad del array. Se aplica el
mismo proceso para la porción izquierda del array
entre el extremo izquierdo y el índice derecho y
para la porción derecha entre el extremo derecho y
el último índice izquierdo.

38. 38
Algoritmo rápido (Quicksort)
•Descripción del algoritmo:
1) Dividir: Si la secuencia S tiene 2 o más elementos,
seleccionar un elemento x de S como pivote. Cualquier
elemento arbitrario, como el último, puede servir. Elimiar los
elementos de S dividiéndolos en 3 secuencias:
L, contiene los elementos de S menores que x
E, contiene los elementos de S iguales a x
G, contiene los elementos de S mayores que x
2) Recursión: De forma recursiva ordenar L y G
3) Vencer: Finalmente, colocar nuevamente los elementos en S
en orden, primero insertar los elementos de L, después E, y
los elementos de G.

39. 39
Idea de Quick Sort
1) Selección: tomar un elemento
2) Dividir: reordenar los elementos
tal que x va a suposición final E
3) Recursión y Vencer: ordenar
recursivamente

40. 40
Arbol Quicksort

41. 41
Arbol Quicksort

42. 42
Arbol Quicksort

43. 43
Arbol Quicksort

44. 44
Arbol Quicksort

45. 45
Arbol Quicksort

46. 46
Arbol Quicksort

47. 47
Arbol Quicksort

48. 48
Arbol Quicksort

49. 49
Arbol Quicksort

50. 50
Arbol Quicksort

51. 51
Arbol Quicksort

52. 52
... Arbol Quicksort (final)

53. 53
Quicksort In-Place
Paso Dividir: l recorre la secuencia desde la izquierda, y r desde la
derecha
Se realiza un intercambio cuando l está en un elemento mayor que el
pivote y r está en uno menor al pivote.

54. 54
In Place Quick Sort (contd.)
Un intercambio con el pivote completa el paso dividir cuando r < l

55. 55
Algoritmo rápido (Quicksort)
void qsort(int izq, int der,
int a[])
{
int i, ult, m, tmp;
if (izq >= der)
return;
tmp= a[izq];
m= (izq+der)/2;
a[izq]= a[m];
a[m]=tmp;
ult=izq;
for (i=izq+1;i<=der;i++)
if (a[i] < a[izq])
{
tmp= a[++ult];
a[ult]= a[i];
a[i]=tmp;
}
tmp= a[izq];
a[izq]= a[ult];
a[ult]=tmp;
qsort(izq,ult-1,a);
qsort(ult+1,der,a);
}

56. 56
Ordenación directa por base (radix sort)
•A diferencia de otros métodos, radix sort considera la
estructura de las llaves.
•Se asume que las llaves están representadas en un
sistema de numeración M (M=radix), e.g., si M=2, las
llaves están representadas en binario.
•Toma ventaja de la posición de cada dígito individual
en la clave. Hay dos versiones de la ordenación radix:
MSD (most significant digit), LSD (least significant
digit).
•La ordenación se realiza comparando los bits en cada
posición.

57. 57
Ejemplo Radix sort
Conjunto a ordenar: { 33, 60, 5, 15, 25, 12, 45, 70, 35, 7}
frente cola
cola_digitos[0] 60 70
cola_digitos[1]
cola_digitos[2] 12
cola_digitos[3] 33
cola_digitos[4]
cola_digitos[5] 5152545 35
cola_digitos[6]
cola_digitos[7] 7
cola_digitos[8]
cola_digitos[9]

58. 58
Ejemplo Radix sort
Conjunto a ordenar: { 33, 60, 5, 15, 25, 12, 45, 70, 35, 7}
frente cola
cola_digitos[0] 05 07
cola_digitos[1]12
cola_digitos[2] 25
cola_digitos[3] 33 35
cola_digitos[4]
cola_digitos[5] 45
cola_digitos[6] 60
cola_digitos[7] 70
cola_digitos[8]
cola_digitos[9]

59. 59
Radix sort directo
Se examinan los bits de derecha a izquierda
for k=0 to b-1
ordenar el array de forma estable
tomando solo el bit k

60. 60
Radix sort en enteros
La ordenación resultante es estable:

61. 61
Análisis de Tiempo de Ejecución
•Los algoritmos de burbuja, inserción, selección corren
en O(n
2
).
•El algoritmo quicksort, montones corren en O(nlogn)
•El algoritmo radix sort es O(n)