Scribd
Cargar
7 vistas13 páginas

Análisis de rendimiento de Quick y Heap Sort

El documento describe la implementación y prueba de los algoritmos Quick sort y Heap sort para ordenar arreglos de números aleatorios. Se crean funciones para Quick sort y Heap sort, y se prueban en tres casos: aleatorio, ascendente y descendente. Se mide el tiempo de ejecución de cada algoritmo para diferentes tamaños de arreglo de 1000 a 4900 elementos, y se grafican los resultados para analizar el comportamiento en los diferentes casos.

Cargado por

Adriana Valadez
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
7 vistas13 páginas

Análisis de rendimiento de Quick y Heap Sort

El documento describe la implementación y prueba de los algoritmos Quick sort y Heap sort para ordenar arreglos de números aleatorios. Se crean funciones para Quick sort y Heap sort, y se prueban en tres casos: aleatorio, ascendente y descendente. Se mide el tiempo de ejecución de cada algoritmo para diferentes tamaños de arreglo de 1000 a 4900 elementos, y se grafican los resultados para analizar el comportamiento en los diferentes casos.

Cargado por

Adriana Valadez
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

practica2

January 23, 2021

1 Practica 2
Adriana Valadez Squivias Se crea una funcion de devuelve un arreglo de numeros aleatorios

[1]: from random import randint


import time
import [Link] as plt

def getRandomNumbers(size):
return [randint(0,200)for _ in range(size)]

Ejemplo de los 3 casos a probar: 1. desordenado (intermedio) 2. Ascendente (mejor) 3. descendente


(peor)

[2]: randomNumbers=getRandomNumbers(5)
ascendentNumbers = sorted(randomNumbers)
descendentNumbers = sorted(randomNumbers, reverse = True)

print("El arreglo aleatorio es: ")


print(randomNumbers)
print("El arreglo ordenado ascendente es: ")
print(ascendentNumbers)
print("El arreglo ordenado descendente es: ")
print(descendentNumbers)

El arreglo aleatorio es:


[108, 153, 3, 12, 45]
El arreglo ordenado ascendente es:
[3, 12, 45, 108, 153]
El arreglo ordenado descendente es:
[153, 108, 45, 12, 3]
Una vez creados los arreglos se define el algoritmo Quick sort

[3]: def quick_sort(lista):


izquierda = []
centro = []
derecha = []
if len(lista) > 1:

1
pivote = lista[0]
for i in lista:
if i < pivote:
[Link](i)
elif i == pivote:
[Link](i)
elif i > pivote:
[Link](i)

return quick_sort(izquierda)+centro+quick_sort(derecha)

print("Quick sort:")

print(len(lista))
else:

return lista

Prueba de Quick sort

[4]: prueba = getRandomNumbers(5)


print("Quick sort:")
print(len(prueba))
print(prueba)
print(quick_sort(prueba))

Quick sort:
5
[54, 55, 49, 118, 82]
[49, 54, 55, 82, 118]
Definicion de inicio, fin e intervalos

[5]: startCount = 1000


endCount = 5000
stepCount = 300

1.1 Quick sort caso intermedio (aleatorio)


[6]: performance = []
for x in range(startCount,endCount,stepCount):
print("Quick sort:")
print(x)
start = [Link]() #O(1)
quick_sort(getRandomNumbers(x)) #O(n2)

2
end = [Link]() #O(1)
[Link](end - start) #O(1)

print(performance)

Quick sort:
1000
Quick sort:
1300
Quick sort:
1600
Quick sort:
1900
Quick sort:
2200
Quick sort:
2500
Quick sort:
2800
Quick sort:
3100
Quick sort:
3400
Quick sort:
3700
Quick sort:
4000
Quick sort:
4300
Quick sort:
4600
Quick sort:
4900
[0.005959749221801758, 0.0069522857666015625, 0.0059587955474853516,
0.00794363021850586, 0.009933948516845703, 0.009933233261108398,
0.011920452117919922, 0.012913703918457031, 0.015893936157226562,
0.01589226722717285, 0.011090517044067383, 0.015622377395629883,
0.015619993209838867, 0.015621662139892578]

[7]: [Link](performance)
[Link]("Caso aleatorio Quick sort")

[7]: Text(0.5, 1.0, 'Caso aleatorio Quick sort')

3
1.2 Quick sort mejor caso
[8]: performance = []
for x in range(startCount,endCount,stepCount):
ascendentNumbers = sorted(getRandomNumbers(x))
print("Quick sort:")
print(x)
start = [Link]()
quick_sort(ascendentNumbers)
end = [Link]()
[Link](end - start)

print(performance)

Quick sort:
1000
Quick sort:
1300
Quick sort:
1600
Quick sort:
1900
Quick sort:
2200
Quick sort:

4
2500
Quick sort:
2800
Quick sort:
3100
Quick sort:
3400
Quick sort:
3700
Quick sort:
4000
Quick sort:
4300
Quick sort:
4600
Quick sort:
4900
[0.052645206451416016, 0.02957439422607422, 0.06248068809509277,
0.06359410285949707, 0.12118864059448242, 0.08147335052490234,
0.09436607360839844, 0.09635353088378906, 0.11026120185852051,
0.12017369270324707, 0.12615370750427246, 0.13115525245666504,
0.1499943733215332, 0.15498089790344238]

[9]: [Link](performance)
[Link]("Mejor caso Quick sort")

[9]: Text(0.5, 1.0, 'Mejor caso Quick sort')

5
1.3 Quick sort Peor caso (Descendente)
[10]: performance = []
for x in range(startCount,endCount,stepCount):
descendantNumbers = sorted(getRandomNumbers(x), reverse = True)
print("Quick sort:")
print(x)
start = [Link]()
quick_sort(descendantNumbers)
end = [Link]()
[Link](end - start)

print(performance)

Quick sort:
1000
Quick sort:
1300
Quick sort:
1600
Quick sort:
1900
Quick sort:
2200
Quick sort:
2500
Quick sort:
2800
Quick sort:
3100
Quick sort:
3400
Quick sort:
3700
Quick sort:
4000
Quick sort:
4300
Quick sort:
4600
Quick sort:
4900
[0.03575706481933594, 0.02782154083251953, 0.030792951583862305,
0.03476762771606445, 0.040726661682128906, 0.04768085479736328,
0.05660057067871094, 0.04504084587097168, 0.06247878074645996,

6
0.07810163497924805, 0.0868384838104248, 0.07813668251037598,
0.07809710502624512, 0.08398151397705078]

[11]: [Link](performance)
[Link]("Peor caso Quick sort")

[11]: Text(0.5, 1.0, 'Peor caso Quick sort')

2 Heap sort
definición de la función:

[12]: def heapify(lista, n, i):


iteraciones=0
iteraciones += 1
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and lista[i] < lista[left]:
largest = left
if right < n and lista[largest] < lista[right]:
largest = right
if largest != i:
lista[i], lista[largest] = lista[largest], lista[i]

7
heapify(lista, n, largest)
return lista

def heapSort(lista):
iteraciones=0
n = len(lista)
for i in range(n // 2 - 1, -1, -1):
iteraciones += 1
heapify(lista, n, i)
for i in range(n-1, 0, -1):
iteraciones += 1
lista[i], lista[0] = lista[0], lista[i]
sortedData = heapify(lista, i, 0)
return sortedData

Prueba de Heap sort

[13]: prueba = getRandomNumbers(5)


print("Heap Sort:")
print(len(prueba))
print(prueba)
print( heapSort(prueba))

Heap Sort:
5
[36, 6, 50, 75, 196]
[6, 36, 50, 75, 196]

2.1 Heap sort caso intermedio (aleatorio)


[14]: performance = []
for x in range(startCount,endCount,stepCount):
print("Heap sort:")
print(x)
start = [Link]() #O(1)
quick_sort(getRandomNumbers(x)) #O(n2)
end = [Link]() #O(1)
[Link](end - start) #O(1)

print(performance)

Heap sort:
1000
Heap sort:
1300
Heap sort:
1600
Heap sort:
1900

8
Heap sort:
2200
Heap sort:
2500
Heap sort:
2800
Heap sort:
3100
Heap sort:
3400
Heap sort:
3700
Heap sort:
4000
Heap sort:
4300
Heap sort:
4600
Heap sort:
4900
[0.004945993423461914, 0.006933927536010742, 0.0069735050201416016,
0.008960962295532227, 0.008939266204833984, 0.01092672348022461,
0.010022163391113281, 0.0, 0.015639543533325195, 0.015633821487426758,
0.01562190055847168, 0.015621423721313477, 0.02990889549255371,
0.019846677780151367]

[15]: [Link](performance)
[Link]("Caso aleatorio Heap sort")

[15]: Text(0.5, 1.0, 'Caso aleatorio Heap sort')

9
2.2 Heap sort mejor caso
[16]: performance = []
for x in range(startCount,endCount,stepCount):
ascendentNumbers = sorted(getRandomNumbers(x))
print("Heap sort:")
print(x)
start = [Link]()
quick_sort(ascendentNumbers)
end = [Link]()
[Link](end - start)

print(performance)

Heap sort:
1000
Heap sort:
1300
Heap sort:
1600
Heap sort:
1900
Heap sort:
2200
Heap sort:

10
2500
Heap sort:
2800
Heap sort:
3100
Heap sort:
3400
Heap sort:
3700
Heap sort:
4000
Heap sort:
4300
Heap sort:
4600
Heap sort:
4900
[0.037743568420410156, 0.03972983360290527, 0.0506596565246582,
0.05759096145629883, 0.06856203079223633, 0.07549285888671875,
0.08639883995056152, 0.09736919403076172, 0.11028242111206055,
0.1400463581085205, 0.12317347526550293, 0.1371009349822998, 0.1420426368713379,
0.15197968482971191]

[17]: [Link](performance)
[Link]("Mejor caso Heap sort")

[17]: Text(0.5, 1.0, 'Mejor caso Heap sort')

11
2.3 Heap sort peor caso
[18]: performance = []
for x in range(startCount,endCount,stepCount):
descendantNumbers = sorted(getRandomNumbers(x), reverse = True)
print("Heap sort:")
print(x)
start = [Link]()
quick_sort(descendantNumbers)
end = [Link]()
[Link](end - start)

print(performance)

Heap sort:
1000
Heap sort:
1300
Heap sort:
1600
Heap sort:
1900
Heap sort:
2200
Heap sort:
2500
Heap sort:
2800
Heap sort:
3100
Heap sort:
3400
Heap sort:
3700
Heap sort:
4000
Heap sort:
4300
Heap sort:
4600
Heap sort:
4900
[0.0348505973815918, 0.03630542755126953, 0.03872036933898926,
0.04869222640991211, 0.04787087440490723, 0.0627126693725586,
0.05866384506225586, 0.06250286102294922, 0.07712030410766602,

12
0.06782364845275879, 0.07809805870056152, 0.10381174087524414,
0.11323976516723633, 0.11920332908630371]

[19]: [Link](performance)
[Link]("Peor caso Heap sort")

[19]: Text(0.5, 1.0, 'Peor caso Heap sort')

13

También podría gustarte