19/05/2015

1

COMPANYLOGOAlgoritmos de Ordenación

₪Contenido

J. C. Carbajal L.

Merge sort1

Análisis Merge sort2

Quick sort3

Análisis QuickSort4

D.A.I. A l g o r i t m i c a I I I

Tarea QuickSort5

COMPANYLOGOEjemplo: Merge sort

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

43 15 9 1 22 26 19 55 37 43 99 2

18 26 32 6 43 15 9 1 22 26 19 55 37 43 99 2

18 26 32 6 43 15 9 1 22 26 19 55 37 43 99 2

18 26 32 6 43 15 9 1 22 26 19 55 37 43 99 2

18 26 32 6 43 15 9 1 22 26 19 55 37 43 99 2

18 26 32 6

COMPANYLOGOEjemplo: Merge sort

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

18 26 32 6 43 15 9 1

18 26 32 6 43 15 9 1

18 26 32 6 43 15 9 1

2618 6 32 1543 1 9

18 26 32 6 43 15 9 1

18 26 32 6 43 15 9 1

18 26 326 15 43 1 9

6 18 26 32 1 9 15 43

1 6 9 15 18 26 32 43

18 26

18 26

18 26

32

32

6

6

32 6

18 26 32 6

43

43

15

15

43 15

9

9

1

1

9 1

43 15 9 1

18 26 32 6 43 15 9 1

18 26 6 32

6 26 3218

1543 1 9

1 9 15 43

1 6 9 1518 26 32 43

Secuencia original Secuencia ordenada

COMPANYLOGOMerge sort

MergeSort( list, first, last )

list la lista de elementos que se pondrán en orden

first el índice del primer elemento de la parte de la lista a ordenar

last el índice del último elemento de la parte de la lista a ordenar

if first < last then

middle = ( first + last ) / 2

MergeSort( list, first, middle )

MergeSort( list, middle + 1, last )

MergeLists( list, first, middle, middle + 1, last )

end if

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

COMPANYLOGOMergeLists

MergeLists( list, start1, end1, start2, end2 )

list los elementos que se pondrán en orden

start1 inicio de la lista A

end1 final de la lista A

start2 inicio de la lista B

end2 final de la lista B

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

COMPANYLOGOMergeLists

// asume que los elementos de A y B son contiguos en la lista

finalStart = start1finalEnd = end2indexC = 1while (start1 ≤ end1) and (start2 ≤ end2) do

if list[start1] < list[start2] thenresult[indexC] = list[start1]start1 = start1 + 1

elseresult[indexC] = list[start2]start2 = start2 + 1

end ifindexC = indexC + 1

end while

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

19/05/2015

2

COMPANYLOGOMergeLists

// mover la parte de la lista que queda

if (start1 ≤ end1) then

for i = start1 to end1 do

result[indexC] = list[i]

indexC = indexC + 1

end for

else

for i = start2 to end2 do

result[indexC] = list[i]

indexC = indexC + 1

end for

end ifJ. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

COMPANYLOGOMergeLists

MergeSort( list, first, last )

list la lista de elementos a ordenar

first el índice del primer elemento de la parte de la lista a ordenar

last el índice del último elemento de la parte de la lista a ordenar

if first < last then

middle = ( first + last ) / 2

MergeSort( list, first, middle )

MergeSort( list, middle + 1, last )

MergeLists( list, first, middle, middle + 1, last )

end if

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

COMPANYLOGOAnálisis de MergeLists

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

14 23 45 98 6 33 42 67

ú ú

COMPANYLOGOAnálisis de MergeLists

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

MergeLists

23 45 98 33 42 6714 6

COMPANYLOGOAnálisis de MergeLists

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

MergeLists

23 45 98 6 42 67

6

14 33

COMPANYLOGOAnálisis de MergeLists

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

MergeLists

14 45 98 6 42 67

6 14

23 33

19/05/2015

3

COMPANYLOGOAnálisis de MergeLists

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

MergeLists

14 23 98 6 42 67

6 14 23

45 33

COMPANYLOGOAnálisis de MergeLists

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

MergeLists

14 23 98 6 33 67

6 14 23 33

45 42

COMPANYLOGOAnálisis de MergeLists

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

MergeLists

14 23 98 6 33 42

6 14 23 33 42

45 67

COMPANYLOGOAnálisis de MergeLists

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

MergeLists

14 23 45 6 33 42

6 14 23 33 42 45

98 67

COMPANYLOGOAnálisis de MergeLists

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

MergeLists

14 23 45 98 6 33 42 67

6 14 23 33 42 45 67

COMPANYLOGOAnálisis de MergeLists

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

MergeLists

14 23 45 98 6 33 42 67

6 14 23 33 42 45 67 98

Debido a que las comparaciones resultaron en movimiento todos menos el último elemento de A, habremos hecho + − comparaciones en este caso más desfavorable.

19/05/2015

4

COMPANYLOGOAnálisis de Merge sort

Basándose en el análisis de MergeLists, estosignifica que en la etapa de combinar se llevará a�/ comparaciones en el mejor de los casos, y�/ + �/ − , o � − comparaciones en el peorcaso. Poniendo todo esto junto da las dosrelaciones de recurrencia para el mejor de loscasos (B) y el peor de los casos (W).� � = � � + � −� = � =� = � + �= =

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

COMPANYLOGOAnálisis de Merge sort

Resolver las ecuaciones de recurrencia. Primeroresolveremos para el peor caso� � = � � + � −� � = � � 8 + � −� � 8 = � � 6 + � 8 −� � 6 = � � + � 6 −Ahora sustituimos:� � = � � + � −� � = � � + � − + � −� � = � + � − + � −� � = � � 8 + � − + � − + � −� � = 8 � 8 + � − + � − + � −

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

COMPANYLOGOAnálisis de Merge sort� � = 8 � 8 + � − +� − +� −� �= 8 � � 6 + � 8− + � − 8+ � − +� − +� −� � = 6� � 6 + � − 8 + � − +� − +� −� �= 6 � � + � 6 − + � − 8 +� − +� − +�−� �= � � +� − 6+ � − 8 +� − +� − +� −� � = � � 5� � log � = � � �

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

COMPANYLOGOAnálisis de Merge sort� � = � � 5� � log � = � � �

� � = � ∗� +� log� − �=log �− �� � = � log� − log � −� � = � log� − � +Esto significa que� � = � log�Cuando nos fijamos en � � y � , vemos la diferenciaentre los dos es que � se convierte en �/ . Cuando nosfijamos en el papel que � jugó durante nuestrassustituciones, el lector debe ver que � ≈ � log� / ,por lo que también es el caso de que � = � � log� .

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

COMPANYLOGOQuicksort

Dado un vector de n elementos (por ejemplo,números enteros):

Si el array sólo contiene un elemento, regresar

Sino

Elegir un elemento a utilizar como pivote.

Elementos separados en dos sub-arreglos:

Elementos menores que o iguales al pivote

Elementos mayores que el pivote

QuickSort dos sub-arreglos

Retorno de resultados

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

COMPANYLOGOEjemplo

Se nos da conjunto de n números enteros paraordenar:

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

40 20 10 80 60 50 7 30 100

19/05/2015

5

COMPANYLOGOEscoger el pivote

Hay un número de maneras de escoger el elementopivote. En este ejemplo, vamos a utilizar el primerelemento de la matriz:

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

40 20 10 80 60 50 7 30 100

COMPANYLOGOParticionar el arreglo

Dado un pivote, particionar los elementos delarreglo de tal manera que el arreglo resultanteconsta de:

Un sub-arreglo que contiene elementos > = pivote

Otro sub-arreglo que contiene los elementos < pivote

Los sub-arrays se almacenan en la matriz de datosoriginal.

Particiones recorre, intercambiando elementos queestán por debajo / encima del pivote.

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

COMPANYLOGOejemplo

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

40 20 10 80 60 50 7 30 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

COMPANYLOGOejemplo

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

40 20 10 80 60 50 7 30 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

1.While data[too_big_index] <= data[pivot]++too_big_index

COMPANYLOGOejemplo

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

40 20 10 80 60 50 7 30 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

1.While data[too_big_index] <= data[pivot]++too_big_index

COMPANYLOGOejemplo

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

40 20 10 80 60 50 7 30 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

1.While data[too_big_index] <= data[pivot]++too_big_index

19/05/2015

6

COMPANYLOGOejemplo

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

40 20 10 80 60 50 7 30 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

1.While data[too_big_index] <= data[pivot]

++too_big_index

2.While data[too_small_index] > data[pivot]

--too_small_index

COMPANYLOGOejemplo

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

40 20 10 80 60 50 7 30 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

1.While data[too_big_index] <= data[pivot]

++too_big_index

2.While data[too_small_index] > data[pivot]

--too_small_index

COMPANYLOGOejemplo

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

40 20 10 30 60 50 7 80 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

1.While data[too_big_index] <= data[pivot]

++too_big_index

2.While data[too_small_index] > data[pivot]

--too_small_index

3.If too_big_index < too_small_index

swap data[too_big_index] and data[too_small_index]

COMPANYLOGOejemplo

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

40 20 10 80 60 50 7 30 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

1.While data[too_big_index] <= data[pivot]

++too_big_index

2.While data[too_small_index] > data[pivot]

--too_small_index

3.If too_big_index < too_small_index

swap data[too_big_index] and data[too_small_index]

COMPANYLOGOejemplo

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

40 20 10 30 60 50 7 80 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

1.While data[too_big_index] <= data[pivot]

++too_big_index

2.While data[too_small_index] > data[pivot]

--too_small_index

3.If too_big_index < too_small_index

swap data[too_big_index] and data[too_small_index]

COMPANYLOGOejemplo

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

40 20 10 30 60 50 7 80 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

1.While data[too_big_index] <= data[pivot]

++too_big_index

2.While data[too_small_index] > data[pivot]

--too_small_index

3.If too_big_index < too_small_index

swap data[too_big_index] and data[too_small_index]

4.While too_small_index > too_big_index, go to 1.

19/05/2015

7

COMPANYLOGOejemplo

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

40 20 10 30 60 50 7 80 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

1.While data[too_big_index] <= data[pivot]

++too_big_index

2.While data[too_small_index] > data[pivot]

--too_small_index

3.If too_big_index < too_small_index

swap data[too_big_index] and data[too_small_index]

4.While too_small_index > too_big_index, go to 1.

COMPANYLOGOejemplo

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

40 20 10 30 60 50 7 80 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

1.While data[too_big_index] <= data[pivot]

++too_big_index

2.While data[too_small_index] > data[pivot]

--too_small_index

3.If too_big_index < too_small_index

swap data[too_big_index] and data[too_small_index]

4.While too_small_index > too_big_index, go to 1.

COMPANYLOGOejemplo

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

40 20 10 30 60 50 7 80 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

1.While data[too_big_index] <= data[pivot]

++too_big_index

2.While data[too_small_index] > data[pivot]

--too_small_index

3.If too_big_index < too_small_index

swap data[too_big_index] and data[too_small_index]

4.While too_small_index > too_big_index, go to 1.

COMPANYLOGOejemplo

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

40 20 10 30 60 50 7 80 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

1.While data[too_big_index] <= data[pivot]

++too_big_index

2.While data[too_small_index] > data[pivot]

--too_small_index

3.If too_big_index < too_small_index

swap data[too_big_index] and data[too_small_index]

4.While too_small_index > too_big_index, go to 1.

COMPANYLOGOejemplo

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

40 20 10 30 60 50 7 80 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

1.While data[too_big_index] <= data[pivot]

++too_big_index

2.While data[too_small_index] > data[pivot]

--too_small_index

3.If too_big_index < too_small_index

swap data[too_big_index] and data[too_small_index]

4.While too_small_index > too_big_index, go to 1.

COMPANYLOGOejemplo

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

40 20 10 30 60 50 7 80 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

1.While data[too_big_index] <= data[pivot]

++too_big_index

2.While data[too_small_index] > data[pivot]

--too_small_index

3.If too_big_index < too_small_index

swap data[too_big_index] and data[too_small_index]

4.While too_small_index > too_big_index, go to 1.

19/05/2015

8

COMPANYLOGOejemplo

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

40 20 10 30 7 50 60 80 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

1.While data[too_big_index] <= data[pivot]

++too_big_index

2.While data[too_small_index] > data[pivot]

--too_small_index

3.If too_big_index < too_small_index

swap data[too_big_index] and data[too_small_index]

4.While too_small_index > too_big_index, go to 1.

COMPANYLOGOejemplo

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

40 20 10 30 7 50 60 80 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

1.While data[too_big_index] <= data[pivot]

++too_big_index

2.While data[too_small_index] > data[pivot]

--too_small_index

3.If too_big_index < too_small_index

swap data[too_big_index] and data[too_small_index]

4.While too_small_index > too_big_index, go to 1.

COMPANYLOGOejemplo

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

40 20 10 30 7 50 60 80 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

1.While data[too_big_index] <= data[pivot]

++too_big_index

2.While data[too_small_index] > data[pivot]

--too_small_index

3.If too_big_index < too_small_index

swap data[too_big_index] and data[too_small_index]

4.While too_small_index > too_big_index, go to 1.

COMPANYLOGOejemplo

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

40 20 10 30 7 50 60 80 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

1.While data[too_big_index] <= data[pivot]

++too_big_index

2.While data[too_small_index] > data[pivot]

--too_small_index

3.If too_big_index < too_small_index

swap data[too_big_index] and data[too_small_index]

4.While too_small_index > too_big_index, go to 1.

COMPANYLOGOejemplo

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

40 20 10 30 7 50 60 80 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

1.While data[too_big_index] <= data[pivot]

++too_big_index

2.While data[too_small_index] > data[pivot]

--too_small_index

3.If too_big_index < too_small_index

swap data[too_big_index] and data[too_small_index]

4.While too_small_index > too_big_index, go to 1.

COMPANYLOGOejemplo

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

40 20 10 30 7 50 60 80 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

1.While data[too_big_index] <= data[pivot]

++too_big_index

2.While data[too_small_index] > data[pivot]

--too_small_index

3.If too_big_index < too_small_index

swap data[too_big_index] and data[too_small_index]

4.While too_small_index > too_big_index, go to 1.

19/05/2015

9

COMPANYLOGOejemplo

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

40 20 10 30 7 50 60 80 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

1.While data[too_big_index] <= data[pivot]

++too_big_index

2.While data[too_small_index] > data[pivot]

--too_small_index

3.If too_big_index < too_small_index

swap data[too_big_index] and data[too_small_index]

4.While too_small_index > too_big_index, go to 1.

COMPANYLOGOejemplo

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

40 20 10 30 7 50 60 80 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

1.While data[too_big_index] <= data[pivot]

++too_big_index

2.While data[too_small_index] > data[pivot]

--too_small_index

3.If too_big_index < too_small_index

swap data[too_big_index] and data[too_small_index]

4.While too_small_index > too_big_index, go to 1.

COMPANYLOGOejemplo

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

40 20 10 30 7 50 60 80 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

1.While data[too_big_index] <= data[pivot]

++too_big_index

2.While data[too_small_index] > data[pivot]

--too_small_index

3.If too_big_index < too_small_index

swap data[too_big_index] and data[too_small_index]

4.While too_small_index > too_big_index, go to 1.

COMPANYLOGOejemplo

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

40 20 10 30 7 50 60 80 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

1.While data[too_big_index] <= data[pivot]

++too_big_index

2.While data[too_small_index] > data[pivot]

--too_small_index

3.If too_big_index < too_small_index

swap data[too_big_index] and data[too_small_index]

4.While too_small_index > too_big_index, go to 1.

5.Swap data[too_small_index] and data[pivot_index]

COMPANYLOGOejemplo

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

7 20 10 30 40 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

1.While data[too_big_index] <= data[pivot]

++too_big_index

2.While data[too_small_index] > data[pivot]

--too_small_index

3.If too_big_index < too_small_index

swap data[too_big_index] and data[too_small_index]

4.While too_small_index > too_big_index, go to 1.

5.Swap data[too_small_index] and data[pivot_index]

pivot_index = 4

COMPANYLOGOResultado de la partición

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

7 20 10 30 40 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

<= data[pivot] > data[pivot]

19/05/2015

10

COMPANYLOGOQuicksort: sub-arreglos

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

7 20 10 30 40 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

<= data[pivot] > data[pivot]

COMPANYLOGOAnálisis de Quicksort

Suponga que las claves son aleatorias,distribuidas uniformemente.

¿Cuál es el mejor tiempo para sufuncionamiento?

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

COMPANYLOGOQuicksort : mejor caso

Suponga que las claves son aleatorias,distribuidas uniformemente.

¿Cuál es el mejor tiempo para sufuncionamiento?

La recursividad:

1. Partición divide arreglo en dos sub-arreglos de tamaño/2. Quicksort a cada sub-arreglo

¿Profundidad del árbol de recursión?� log ¿Número de accesos en la partición?�

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

COMPANYLOGOQuicksort : mejor caso

Suponga que las claves son aleatorias, distribuidasuniformemente.

Mejor de los casos el tiempo de funcionamiento:� log

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

COMPANYLOGOQuicksort: mejor caso

Suponga que las claves son aleatorias, distribuidasuniformemente.

Tiempo de funcionamiento en el mejor de los casos:� log¿Tiempo de funcionamiento en el peor de loscasos?

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

COMPANYLOGOQuicksort: Peor caso

Supongamos que el primer elemento se elige comopivote.

Supongamos que obtenemos un arreglo que ya estáen orden:

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

2 4 10 12 13 50 57 63 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

19/05/2015

11

COMPANYLOGOQuicksort: Peor caso

1.While data[too_big_index] <= data[pivot]

++too_big_index

2.While data[too_small_index] > data[pivot]

--too_small_index

3.If too_big_index < too_small_index

swap data[too_big_index] and data[too_small_index]

4.While too_small_index > too_big_index, go to 1.

5.Swap data[too_small_index] and data[pivot_index]

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

2 4 10 12 13 50 57 63 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

COMPANYLOGOQuicksort: Peor caso

1.While data[too_big_index] <= data[pivot]

++too_big_index

2.While data[too_small_index] > data[pivot]

--too_small_index

3.If too_big_index < too_small_index

swap data[too_big_index] and data[too_small_index]

4.While too_small_index > too_big_index, go to 1.

5.Swap data[too_small_index] and data[pivot_index]

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

2 4 10 12 13 50 57 63 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

COMPANYLOGOQuicksort: Peor caso

1.While data[too_big_index] <= data[pivot]

++too_big_index

2.While data[too_small_index] > data[pivot]

--too_small_index

3.If too_big_index < too_small_index

swap data[too_big_index] and data[too_small_index]

4.While too_small_index > too_big_index, go to 1.

5.Swap data[too_small_index] and data[pivot_index]

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

2 4 10 12 13 50 57 63 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

COMPANYLOGOQuicksort: Peor caso

1.While data[too_big_index] <= data[pivot]

++too_big_index

2.While data[too_small_index] > data[pivot]

--too_small_index

3.If too_big_index < too_small_index

swap data[too_big_index] and data[too_small_index]

4.While too_small_index > too_big_index, go to 1.

5.Swap data[too_small_index] and data[pivot_index]

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

2 4 10 12 13 50 57 63 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

COMPANYLOGOQuicksort: Peor caso

1.While data[too_big_index] <= data[pivot]

++too_big_index

2.While data[too_small_index] > data[pivot]

--too_small_index

3.If too_big_index < too_small_index

swap data[too_big_index] and data[too_small_index]

4.While too_small_index > too_big_index, go to 1.

5.Swap data[too_small_index] and data[pivot_index]

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

2 4 10 12 13 50 57 63 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

COMPANYLOGOQuicksort: Peor caso

1.While data[too_big_index] <= data[pivot]

++too_big_index

2.While data[too_small_index] > data[pivot]

--too_small_index

3.If too_big_index < too_small_index

swap data[too_big_index] and data[too_small_index]

4.While too_small_index > too_big_index, go to 1.

5.Swap data[too_small_index] and data[pivot_index]

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

2 4 10 12 13 50 57 63 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

19/05/2015

12

COMPANYLOGOQuicksort: Peor caso

1.While data[too_big_index] <= data[pivot]

++too_big_index

2.While data[too_small_index] > data[pivot]

--too_small_index

3.If too_big_index < too_small_index

swap data[too_big_index] and data[too_small_index]

4.While too_small_index > too_big_index, go to 1.

5.Swap data[too_small_index] and data[pivot_index]

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

2 4 10 12 13 50 57 63 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index

COMPANYLOGOQuicksort: Peor caso

1.While data[too_big_index] <= data[pivot]

++too_big_index

2.While data[too_small_index] > data[pivot]

--too_small_index

3.If too_big_index < too_small_index

swap data[too_big_index] and data[too_small_index]

4.While too_small_index > too_big_index, go to 1.

5.Swap data[too_small_index] and data[pivot_index]

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

2 4 10 12 13 50 57 63 100pivot_index = 0

[0] [1] [2] [3] [4] [5] [6] [7] [8]

> data[pivot]<= data[pivot]

COMPANYLOGOQuicksort : peor caso

Suponga que las claves son aleatorias, distribuidasuniformemente.

Tiempo de funcionamiento mejor caso: � log ¿Tiempo funcionamiento para el peor caso?

La recursividad:1. La partición divide el arreglo en dos sub-arreglos:

un sub-arreglo de tamaño 0

otro sub-arreglo de tamaño n-1

2. Quicksort a cada sub-arreglo

¿Profundidad del árbol de recursión?� ¿Número de accesos en la partición?�

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

COMPANYLOGOQuicksort : peor caso

Suponga que las claves son aleatorias,distribuidas uniformemente.

Tiempo de funcionamiento mejor caso:� log Tiempo funcionamiento para el peor caso�

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

COMPANYLOGOQuicksort : peor caso

Suponga que las claves son aleatorias,distribuidas uniformemente.

Tiempo de funcionamiento mejor caso:� log Tiempo funcionamiento para el peor caso�¿Qué podemos hacer para evitar el peorde los casos?

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

COMPANYLOGOMejorar la elección pivote

Escoger el valor medio de tres elementos delarreglo de datos:

datos [0], datos [n / 2], y los datos [n-1].

Utilice este valor medio como pivote.

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

19/05/2015

13

COMPANYLOGO

Mejorar el rendimiento de Quicksort

Mejor la elección del pivote.

Para sub-arrays de tamaño 3 o menos, aplicar labúsqueda de fuerza bruta:

Sub-arreglo de tamaño 1: trivial

Sub-arreglo de tamaño 2:

if(data[first] > data[second]) intercambiarlos

Sub-arreglo de tamaño 3: se deja comotarea.

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

COMPANYLOGOTarea: Quicksort

Quicksort( list, first, last )

list elementos que se pondrán en orden

first índice del primer elemento en la parte de la lista a ordenar

last índice del último elemento en la parte de la lista a ordenar

if first < last then

pivot = PivotList( list, first, last )

Quicksort( list, first, pivot-1 )

Quicksort( list, pivot+1, last )

end if

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

COMPANYLOGOTarea: Quicksort

PivotList( list, first, last )list los elementos para trabajarfirst el índice del primer elementolast el índice del último elementoPivotValue = list[ first ]PivotPoint = firstfor index = first + 1 to last do

if list[ index ] < PivotValue thenPivotPoint = PivotPoint + 1Swap( list[ PivotPoint ], list[ index ] )

end ifend for// mover el valor del pivote a su lugar correctoSwap( list[ first ], list[ PivotPoint ] )return PivotPoint

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

COMPANYLOGOQuicksort

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

Tarea: realizar el análisis del caso promedio para el quicksort