InsertSort
¶zoznam = [81, 23, 66, 46, 77, 44, 59, 36, 30, 16, 10, 55, 91, 31, 13, 92, 63, 69, 39, 30, 49, 60, 51, 48, 27, 12, 55, 58, 49, 31]
vysledok = []
while len(zoznam) > 0:
vysledok = list(sorted(vysledok+[zoznam.pop(0)]))
print(vysledok)
[81] [23, 81] [23, 66, 81] [23, 46, 66, 81] [23, 46, 66, 77, 81] [23, 44, 46, 66, 77, 81] [23, 44, 46, 59, 66, 77, 81] [23, 36, 44, 46, 59, 66, 77, 81] [23, 30, 36, 44, 46, 59, 66, 77, 81] [16, 23, 30, 36, 44, 46, 59, 66, 77, 81] [10, 16, 23, 30, 36, 44, 46, 59, 66, 77, 81] [10, 16, 23, 30, 36, 44, 46, 55, 59, 66, 77, 81] [10, 16, 23, 30, 36, 44, 46, 55, 59, 66, 77, 81, 91] [10, 16, 23, 30, 31, 36, 44, 46, 55, 59, 66, 77, 81, 91] [10, 13, 16, 23, 30, 31, 36, 44, 46, 55, 59, 66, 77, 81, 91] [10, 13, 16, 23, 30, 31, 36, 44, 46, 55, 59, 66, 77, 81, 91, 92] [10, 13, 16, 23, 30, 31, 36, 44, 46, 55, 59, 63, 66, 77, 81, 91, 92] [10, 13, 16, 23, 30, 31, 36, 44, 46, 55, 59, 63, 66, 69, 77, 81, 91, 92] [10, 13, 16, 23, 30, 31, 36, 39, 44, 46, 55, 59, 63, 66, 69, 77, 81, 91, 92] [10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 55, 59, 63, 66, 69, 77, 81, 91, 92] [10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 55, 59, 63, 66, 69, 77, 81, 91, 92] [10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 55, 59, 60, 63, 66, 69, 77, 81, 91, 92] [10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 51, 55, 59, 60, 63, 66, 69, 77, 81, 91, 92] [10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 81, 91, 92] [10, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 81, 91, 92] [10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 81, 91, 92] [10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 55, 59, 60, 63, 66, 69, 77, 81, 91, 92] [10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 55, 58, 59, 60, 63, 66, 69, 77, 81, 91, 92] [10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 49, 51, 55, 55, 58, 59, 60, 63, 66, 69, 77, 81, 91, 92] [10, 12, 13, 16, 23, 27, 30, 30, 31, 31, 36, 39, 44, 46, 48, 49, 49, 51, 55, 55, 58, 59, 60, 63, 66, 69, 77, 81, 91, 92]
zoznam = [81, 23, 66, 46, 77, 44, 59, 36, 30, 16, 10, 55, 91, 31, 13, 92, 63, 69, 39, 30, 49, 60, 51, 48, 27, 12, 55, 58, 49, 31]
vysledok = []
for prvok in zoznam:
vysledok = list(sorted(vysledok+[prvok]))
print(vysledok)
[81] [23, 81] [23, 66, 81] [23, 46, 66, 81] [23, 46, 66, 77, 81] [23, 44, 46, 66, 77, 81] [23, 44, 46, 59, 66, 77, 81] [23, 36, 44, 46, 59, 66, 77, 81] [23, 30, 36, 44, 46, 59, 66, 77, 81] [16, 23, 30, 36, 44, 46, 59, 66, 77, 81] [10, 16, 23, 30, 36, 44, 46, 59, 66, 77, 81] [10, 16, 23, 30, 36, 44, 46, 55, 59, 66, 77, 81] [10, 16, 23, 30, 36, 44, 46, 55, 59, 66, 77, 81, 91] [10, 16, 23, 30, 31, 36, 44, 46, 55, 59, 66, 77, 81, 91] [10, 13, 16, 23, 30, 31, 36, 44, 46, 55, 59, 66, 77, 81, 91] [10, 13, 16, 23, 30, 31, 36, 44, 46, 55, 59, 66, 77, 81, 91, 92] [10, 13, 16, 23, 30, 31, 36, 44, 46, 55, 59, 63, 66, 77, 81, 91, 92] [10, 13, 16, 23, 30, 31, 36, 44, 46, 55, 59, 63, 66, 69, 77, 81, 91, 92] [10, 13, 16, 23, 30, 31, 36, 39, 44, 46, 55, 59, 63, 66, 69, 77, 81, 91, 92] [10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 55, 59, 63, 66, 69, 77, 81, 91, 92] [10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 55, 59, 63, 66, 69, 77, 81, 91, 92] [10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 55, 59, 60, 63, 66, 69, 77, 81, 91, 92] [10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 51, 55, 59, 60, 63, 66, 69, 77, 81, 91, 92] [10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 81, 91, 92] [10, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 81, 91, 92] [10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 81, 91, 92] [10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 55, 59, 60, 63, 66, 69, 77, 81, 91, 92] [10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 55, 58, 59, 60, 63, 66, 69, 77, 81, 91, 92] [10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 49, 51, 55, 55, 58, 59, 60, 63, 66, 69, 77, 81, 91, 92] [10, 12, 13, 16, 23, 27, 30, 30, 31, 31, 36, 39, 44, 46, 48, 49, 49, 51, 55, 55, 58, 59, 60, 63, 66, 69, 77, 81, 91, 92]
zoznam = [81, 23, 66, 46, 77, 44, 59, 36, 30, 16, 10, 55, 91, 31, 13, 92, 63, 69, 39, 30, 49, 60, 51, 48, 27, 12, 55, 58, 49, 31]
for index in range(2, len(zoznam)):
#zaradime kartu na danom indexe na spravnu poziciu vlavo, prebuble do uz usporiadanej casti
i = index-1
while zoznam[i] > zoznam[i+1]:
zoznam[i], zoznam[i+1] = zoznam[i+1], zoznam[i]
i -= 1
print(zoznam[:index]) #uz usporiadana cast
[81, 23] [81, 23, 46] [81, 23, 46, 66] [81, 23, 44, 46, 66] [81, 23, 44, 46, 59, 66] [81, 23, 36, 44, 46, 59, 66] [81, 23, 30, 36, 44, 46, 59, 66] [31, 81, 23, 30, 36, 44, 46, 59, 66]
--------------------------------------------------------------------------- IndexError Traceback (most recent call last) ~\AppData\Local\Temp\ipykernel_7796\2188616902.py in <cell line: 2>() 3 #zaradime kartu na danom indexe na spravnu poziciu vlavo, prebuble do uz usporiadanej casti 4 i = index-1 ----> 5 while zoznam[i] > zoznam[i+1]: 6 zoznam[i], zoznam[i+1] = zoznam[i+1], zoznam[i] 7 i -= 1 IndexError: list index out of range
zoznam = [2, 81, 23, 5, 7]
for index in range(1, len(zoznam)):
#zaradime kartu na danom indexe na spravnu poziciu vlavo, prebuble do uz usporiadanej casti
i = index-1
while zoznam[i] > zoznam[i+1]: #prebublanie dolava
zoznam[i], zoznam[i+1] = zoznam[i+1], zoznam[i]
i -= 1
print(zoznam[:index+1]) #uz usporiadana cast
[2, 81] [2, 23, 81] [2, 5, 23, 81] [2, 5, 7, 23, 81]
zoznam = [81, 23, 66, 46, 77, 44, 59, 36, 30, 16, 10, 55, 91, 31, 13, 92, 63, 69, 39, 30, 49, 60, 51, 48, 27, 12, 55, 58, 49, 31]
for index in range(1, len(zoznam)):
#zaradime kartu na danom indexe na spravnu poziciu vlavo, prebuble do uz usporiadanej casti
i = index-1
while zoznam[i] > zoznam[i+1]: #prebublanie dolava
zoznam[i], zoznam[i+1] = zoznam[i+1], zoznam[i]
i -= 1
print(zoznam[:index+1]) #uz usporiadana cast
print()
[31, 81] [31, 66, 81] [31, 46, 66, 81] [31, 46, 66, 77, 81] [31, 44, 46, 66, 77, 81] [31, 44, 46, 59, 66, 77, 81] [31, 36, 44, 46, 59, 66, 77, 81] [49, 31, 36, 44, 46, 59, 66, 77, 81] [58, 49, 31, 36, 44, 46, 59, 66, 77, 81]
--------------------------------------------------------------------------- IndexError Traceback (most recent call last) ~\AppData\Local\Temp\ipykernel_7796\4010770525.py in <cell line: 2>() 3 #zaradime kartu na danom indexe na spravnu poziciu vlavo, prebuble do uz usporiadanej casti 4 i = index-1 ----> 5 while zoznam[i] > zoznam[i+1]: #prebublanie dolava 6 zoznam[i], zoznam[i+1] = zoznam[i+1], zoznam[i] 7 i -= 1 IndexError: list index out of range
#zoznam po kazdej vymene
zoznam = [81, 23, 66, 46, 77, 44, 59, 36, 30, 16, 10, 55, 91, 31, 13, 92, 63, 69, 39, 30, 49, 60, 51, 48, 27, 12, 55, 58, 49, 31]
for index in range(1, len(zoznam)):
#zaradime kartu na danom indexe na spravnu poziciu vlavo, prebuble do uz usporiadanej casti
i = index-1
while zoznam[i] > zoznam[i+1]: #prebublanie dolava
zoznam[i], zoznam[i+1] = zoznam[i+1], zoznam[i]
i -= 1
print(zoznam[:index+1]) #uz usporiadana cast
print()
[23, 81] [31, 81] [31, 81] [31, 81] [31, 81] [31, 66, 81] [31, 66, 46, 81] [31, 46, 66, 81] [31, 46, 66, 77, 81] [31, 46, 66, 77, 44, 81] [31, 46, 66, 44, 77, 81] [31, 46, 44, 66, 77, 81] [31, 44, 46, 66, 77, 81] [31, 44, 46, 66, 77, 59, 81] [31, 44, 46, 66, 59, 77, 81] [31, 44, 46, 59, 66, 77, 81] [31, 44, 46, 59, 66, 77, 36, 81] [31, 44, 46, 59, 66, 36, 77, 81] [31, 44, 46, 59, 36, 66, 77, 81] [31, 44, 46, 36, 59, 66, 77, 81] [31, 44, 36, 46, 59, 66, 77, 81] [31, 36, 44, 46, 59, 66, 77, 81] [31, 36, 44, 46, 59, 66, 77, 30, 81] [31, 36, 44, 46, 59, 66, 30, 77, 81] [31, 36, 44, 46, 59, 30, 66, 77, 81] [31, 36, 44, 46, 30, 59, 66, 77, 81] [31, 36, 44, 30, 46, 59, 66, 77, 81] [31, 36, 30, 44, 46, 59, 66, 77, 81] [31, 30, 36, 44, 46, 59, 66, 77, 81] [30, 31, 36, 44, 46, 59, 66, 77, 81] [49, 31, 36, 44, 46, 59, 66, 77, 81] [49, 31, 36, 44, 46, 59, 66, 77, 81] [49, 31, 36, 44, 46, 59, 66, 77, 81] [49, 31, 36, 44, 46, 59, 66, 77, 16, 81] [49, 31, 36, 44, 46, 59, 66, 16, 77, 81] [49, 31, 36, 44, 46, 59, 16, 66, 77, 81] [49, 31, 36, 44, 46, 16, 59, 66, 77, 81] [49, 31, 36, 44, 16, 46, 59, 66, 77, 81] [49, 31, 36, 16, 44, 46, 59, 66, 77, 81] [49, 31, 16, 36, 44, 46, 59, 66, 77, 81] [49, 16, 31, 36, 44, 46, 59, 66, 77, 81] [16, 49, 31, 36, 44, 46, 59, 66, 77, 81] [58, 49, 31, 36, 44, 46, 59, 66, 77, 81] [58, 49, 31, 36, 44, 46, 59, 66, 77, 81] [58, 49, 31, 36, 44, 46, 59, 66, 77, 81] [58, 49, 31, 36, 44, 46, 59, 66, 77, 81] [58, 49, 31, 36, 44, 46, 59, 66, 77, 10, 81] [58, 49, 31, 36, 44, 46, 59, 66, 10, 77, 81] [58, 49, 31, 36, 44, 46, 59, 10, 66, 77, 81] [58, 49, 31, 36, 44, 46, 10, 59, 66, 77, 81] [58, 49, 31, 36, 44, 10, 46, 59, 66, 77, 81] [58, 49, 31, 36, 10, 44, 46, 59, 66, 77, 81] [58, 49, 31, 10, 36, 44, 46, 59, 66, 77, 81] [58, 49, 10, 31, 36, 44, 46, 59, 66, 77, 81] [58, 10, 49, 31, 36, 44, 46, 59, 66, 77, 81] [10, 58, 49, 31, 36, 44, 46, 59, 66, 77, 81] [55, 58, 49, 31, 36, 44, 46, 59, 66, 77, 81] [55, 58, 49, 31, 36, 44, 46, 59, 66, 77, 81] [55, 58, 49, 31, 36, 44, 46, 59, 66, 77, 81] [55, 58, 49, 31, 36, 44, 46, 59, 66, 77, 81] [55, 58, 49, 31, 36, 44, 46, 59, 66, 77, 81] [55, 58, 49, 31, 36, 44, 46, 59, 66, 77, 81] [55, 58, 49, 31, 36, 44, 46, 59, 66, 77, 81] [55, 58, 49, 31, 36, 44, 46, 59, 66, 77, 81] [55, 58, 49, 31, 36, 44, 46, 59, 66, 77, 81] [55, 58, 49, 31, 36, 44, 46, 59, 66, 77, 81] [55, 58, 49, 31, 36, 44, 46, 59, 66, 77, 81] [55, 58, 49, 31, 36, 44, 46, 59, 66, 77, 81] [55, 58, 49, 31, 36, 44, 46, 59, 66, 77, 81] [55, 58, 49, 31, 36, 44, 46, 59, 66, 77, 81] [55, 58, 49, 31, 36, 44, 46, 59, 66, 77, 81] [55, 58, 49, 31, 36, 44, 46, 59, 66, 77, 81] [55, 58, 49, 31, 36, 44, 46, 59, 66, 77, 81] [55, 58, 49, 31, 36, 44, 46, 59, 66, 77, 81] [55, 58, 49, 31, 36, 44, 46, 59, 66, 77, 81] [55, 58, 49, 31, 36, 44, 46, 59, 66, 77, 10] [55, 58, 49, 31, 36, 44, 46, 59, 66, 10, 77] [55, 58, 49, 31, 36, 44, 46, 59, 10, 66, 77] [55, 58, 49, 31, 36, 44, 46, 10, 59, 66, 77] [55, 58, 49, 31, 36, 44, 10, 46, 59, 66, 77] [55, 58, 49, 31, 36, 10, 44, 46, 59, 66, 77] [55, 58, 49, 31, 10, 36, 44, 46, 59, 66, 77] [55, 58, 49, 10, 31, 36, 44, 46, 59, 66, 77] [55, 58, 10, 49, 31, 36, 44, 46, 59, 66, 77] [55, 10, 58, 49, 31, 36, 44, 46, 59, 66, 77] [10, 55, 58, 49, 31, 36, 44, 46, 59, 66, 77]
--------------------------------------------------------------------------- IndexError Traceback (most recent call last) ~\AppData\Local\Temp\ipykernel_7796\459815308.py in <cell line: 3>() 4 #zaradime kartu na danom indexe na spravnu poziciu vlavo, prebuble do uz usporiadanej casti 5 i = index-1 ----> 6 while zoznam[i] > zoznam[i+1]: #prebublanie dolava 7 zoznam[i], zoznam[i+1] = zoznam[i+1], zoznam[i] 8 i -= 1 IndexError: list index out of range
Problém je pri prebublaní hodnoty 30
[30, 31, 36, 44, 46, 59, 66, 77, 81]
[49, 31, 36, 44, 46, 59, 66, 77, 81]
prebublať môže iba po začiatok, nie pokračovať ďalej
#zoznam po kazdej vymene
zoznam = [81, 23, 66, 46, 77, 44, 59, 36, 30, 16, 10, 55, 91, 31, 13, 92, 63, 69, 39, 30, 49, 60, 51, 48, 27, 12, 55, 58, 49, 31]
for index in range(1, len(zoznam)):
#zaradime kartu na danom indexe na spravnu poziciu vlavo, prebuble do uz usporiadanej casti
i = index-1
while i >= 1 and zoznam[i] > zoznam[i+1]: #prebublanie dolava
zoznam[i], zoznam[i+1] = zoznam[i+1], zoznam[i]
i -= 1
print(zoznam[:index+1]) #uz usporiadana cast
print()
[81, 23, 46, 66] [81, 23, 46, 66, 44, 77] [81, 23, 46, 44, 66, 77] [81, 23, 44, 46, 66, 77] [81, 23, 44, 46, 66, 59, 77] [81, 23, 44, 46, 59, 66, 77] [81, 23, 44, 46, 59, 66, 36, 77] [81, 23, 44, 46, 59, 36, 66, 77] [81, 23, 44, 46, 36, 59, 66, 77] [81, 23, 44, 36, 46, 59, 66, 77] [81, 23, 36, 44, 46, 59, 66, 77] [81, 23, 36, 44, 46, 59, 66, 30, 77] [81, 23, 36, 44, 46, 59, 30, 66, 77] [81, 23, 36, 44, 46, 30, 59, 66, 77] [81, 23, 36, 44, 30, 46, 59, 66, 77] [81, 23, 36, 30, 44, 46, 59, 66, 77] [81, 23, 30, 36, 44, 46, 59, 66, 77] [81, 23, 30, 36, 44, 46, 59, 66, 16, 77] [81, 23, 30, 36, 44, 46, 59, 16, 66, 77] [81, 23, 30, 36, 44, 46, 16, 59, 66, 77] [81, 23, 30, 36, 44, 16, 46, 59, 66, 77] [81, 23, 30, 36, 16, 44, 46, 59, 66, 77] [81, 23, 30, 16, 36, 44, 46, 59, 66, 77] [81, 23, 16, 30, 36, 44, 46, 59, 66, 77] [81, 16, 23, 30, 36, 44, 46, 59, 66, 77] [81, 16, 23, 30, 36, 44, 46, 59, 66, 10, 77] [81, 16, 23, 30, 36, 44, 46, 59, 10, 66, 77] [81, 16, 23, 30, 36, 44, 46, 10, 59, 66, 77] [81, 16, 23, 30, 36, 44, 10, 46, 59, 66, 77] [81, 16, 23, 30, 36, 10, 44, 46, 59, 66, 77] [81, 16, 23, 30, 10, 36, 44, 46, 59, 66, 77] [81, 16, 23, 10, 30, 36, 44, 46, 59, 66, 77] [81, 16, 10, 23, 30, 36, 44, 46, 59, 66, 77] [81, 10, 16, 23, 30, 36, 44, 46, 59, 66, 77] [81, 10, 16, 23, 30, 36, 44, 46, 59, 66, 55, 77] [81, 10, 16, 23, 30, 36, 44, 46, 59, 55, 66, 77] [81, 10, 16, 23, 30, 36, 44, 46, 55, 59, 66, 77] [81, 10, 16, 23, 30, 36, 44, 46, 55, 59, 66, 77, 31, 91] [81, 10, 16, 23, 30, 36, 44, 46, 55, 59, 66, 31, 77, 91] [81, 10, 16, 23, 30, 36, 44, 46, 55, 59, 31, 66, 77, 91] [81, 10, 16, 23, 30, 36, 44, 46, 55, 31, 59, 66, 77, 91] [81, 10, 16, 23, 30, 36, 44, 46, 31, 55, 59, 66, 77, 91] [81, 10, 16, 23, 30, 36, 44, 31, 46, 55, 59, 66, 77, 91] [81, 10, 16, 23, 30, 36, 31, 44, 46, 55, 59, 66, 77, 91] [81, 10, 16, 23, 30, 31, 36, 44, 46, 55, 59, 66, 77, 91] [81, 10, 16, 23, 30, 31, 36, 44, 46, 55, 59, 66, 77, 13, 91] [81, 10, 16, 23, 30, 31, 36, 44, 46, 55, 59, 66, 13, 77, 91] [81, 10, 16, 23, 30, 31, 36, 44, 46, 55, 59, 13, 66, 77, 91] [81, 10, 16, 23, 30, 31, 36, 44, 46, 55, 13, 59, 66, 77, 91] [81, 10, 16, 23, 30, 31, 36, 44, 46, 13, 55, 59, 66, 77, 91] [81, 10, 16, 23, 30, 31, 36, 44, 13, 46, 55, 59, 66, 77, 91] [81, 10, 16, 23, 30, 31, 36, 13, 44, 46, 55, 59, 66, 77, 91] [81, 10, 16, 23, 30, 31, 13, 36, 44, 46, 55, 59, 66, 77, 91] [81, 10, 16, 23, 30, 13, 31, 36, 44, 46, 55, 59, 66, 77, 91] [81, 10, 16, 23, 13, 30, 31, 36, 44, 46, 55, 59, 66, 77, 91] [81, 10, 16, 13, 23, 30, 31, 36, 44, 46, 55, 59, 66, 77, 91] [81, 10, 13, 16, 23, 30, 31, 36, 44, 46, 55, 59, 66, 77, 91] [81, 10, 13, 16, 23, 30, 31, 36, 44, 46, 55, 59, 66, 77, 91, 63, 92] [81, 10, 13, 16, 23, 30, 31, 36, 44, 46, 55, 59, 66, 77, 63, 91, 92] [81, 10, 13, 16, 23, 30, 31, 36, 44, 46, 55, 59, 66, 63, 77, 91, 92] [81, 10, 13, 16, 23, 30, 31, 36, 44, 46, 55, 59, 63, 66, 77, 91, 92] [81, 10, 13, 16, 23, 30, 31, 36, 44, 46, 55, 59, 63, 66, 77, 91, 69, 92] [81, 10, 13, 16, 23, 30, 31, 36, 44, 46, 55, 59, 63, 66, 77, 69, 91, 92] [81, 10, 13, 16, 23, 30, 31, 36, 44, 46, 55, 59, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 31, 36, 44, 46, 55, 59, 63, 66, 69, 77, 91, 39, 92] [81, 10, 13, 16, 23, 30, 31, 36, 44, 46, 55, 59, 63, 66, 69, 77, 39, 91, 92] [81, 10, 13, 16, 23, 30, 31, 36, 44, 46, 55, 59, 63, 66, 69, 39, 77, 91, 92] [81, 10, 13, 16, 23, 30, 31, 36, 44, 46, 55, 59, 63, 66, 39, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 31, 36, 44, 46, 55, 59, 63, 39, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 31, 36, 44, 46, 55, 59, 39, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 31, 36, 44, 46, 55, 39, 59, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 31, 36, 44, 46, 39, 55, 59, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 31, 36, 44, 39, 46, 55, 59, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 31, 36, 39, 44, 46, 55, 59, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 31, 36, 39, 44, 46, 55, 59, 63, 66, 69, 77, 91, 30, 92] [81, 10, 13, 16, 23, 30, 31, 36, 39, 44, 46, 55, 59, 63, 66, 69, 77, 30, 91, 92] [81, 10, 13, 16, 23, 30, 31, 36, 39, 44, 46, 55, 59, 63, 66, 69, 30, 77, 91, 92] [81, 10, 13, 16, 23, 30, 31, 36, 39, 44, 46, 55, 59, 63, 66, 30, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 31, 36, 39, 44, 46, 55, 59, 63, 30, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 31, 36, 39, 44, 46, 55, 59, 30, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 31, 36, 39, 44, 46, 55, 30, 59, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 31, 36, 39, 44, 46, 30, 55, 59, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 31, 36, 39, 44, 30, 46, 55, 59, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 31, 36, 39, 30, 44, 46, 55, 59, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 31, 36, 30, 39, 44, 46, 55, 59, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 31, 30, 36, 39, 44, 46, 55, 59, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 55, 59, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 55, 59, 63, 66, 69, 77, 91, 49, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 55, 59, 63, 66, 69, 77, 49, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 55, 59, 63, 66, 69, 49, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 55, 59, 63, 66, 49, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 55, 59, 63, 49, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 55, 59, 49, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 55, 49, 59, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 55, 59, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 55, 59, 63, 66, 69, 77, 91, 60, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 55, 59, 63, 66, 69, 77, 60, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 55, 59, 63, 66, 69, 60, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 55, 59, 63, 66, 60, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 55, 59, 63, 60, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 55, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 55, 59, 60, 63, 66, 69, 77, 91, 51, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 55, 59, 60, 63, 66, 69, 77, 51, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 55, 59, 60, 63, 66, 69, 51, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 55, 59, 60, 63, 66, 51, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 55, 59, 60, 63, 51, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 55, 59, 60, 51, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 55, 59, 51, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 55, 51, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 51, 55, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 51, 55, 59, 60, 63, 66, 69, 77, 91, 48, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 51, 55, 59, 60, 63, 66, 69, 77, 48, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 51, 55, 59, 60, 63, 66, 69, 48, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 51, 55, 59, 60, 63, 66, 48, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 51, 55, 59, 60, 63, 48, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 51, 55, 59, 60, 48, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 51, 55, 59, 48, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 51, 55, 48, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 51, 48, 55, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 48, 51, 55, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 91, 27, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 27, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 27, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 27, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 27, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 27, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 27, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 27, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 27, 55, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 48, 49, 27, 51, 55, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 48, 27, 49, 51, 55, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 27, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 27, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 39, 27, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 36, 27, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 31, 27, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 30, 27, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 30, 27, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 91, 12, 92] [81, 10, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 12, 91, 92] [81, 10, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 12, 77, 91, 92] [81, 10, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 12, 69, 77, 91, 92] [81, 10, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 12, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 12, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 12, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 12, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 12, 55, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 12, 51, 55, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 12, 49, 51, 55, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 12, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 12, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 27, 30, 30, 31, 36, 39, 12, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 27, 30, 30, 31, 36, 12, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 27, 30, 30, 31, 12, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 27, 30, 30, 12, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 27, 30, 12, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 27, 12, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 23, 12, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 16, 12, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 13, 12, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 91, 55, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 55, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 55, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 55, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 55, 66, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 55, 63, 66, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 55, 60, 63, 66, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 55, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 55, 59, 60, 63, 66, 69, 77, 91, 58, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 55, 59, 60, 63, 66, 69, 77, 58, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 55, 59, 60, 63, 66, 69, 58, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 55, 59, 60, 63, 66, 58, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 55, 59, 60, 63, 58, 66, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 55, 59, 60, 58, 63, 66, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 55, 59, 58, 60, 63, 66, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 55, 58, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 55, 58, 59, 60, 63, 66, 69, 77, 91, 49, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 55, 58, 59, 60, 63, 66, 69, 77, 49, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 55, 58, 59, 60, 63, 66, 69, 49, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 55, 58, 59, 60, 63, 66, 49, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 55, 58, 59, 60, 63, 49, 66, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 55, 58, 59, 60, 49, 63, 66, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 55, 58, 59, 49, 60, 63, 66, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 55, 58, 49, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 55, 49, 58, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 49, 55, 58, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 49, 55, 55, 58, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 49, 51, 55, 55, 58, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 49, 51, 55, 55, 58, 59, 60, 63, 66, 69, 77, 91, 31, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 49, 51, 55, 55, 58, 59, 60, 63, 66, 69, 77, 31, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 49, 51, 55, 55, 58, 59, 60, 63, 66, 69, 31, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 49, 51, 55, 55, 58, 59, 60, 63, 66, 31, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 49, 51, 55, 55, 58, 59, 60, 63, 31, 66, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 49, 51, 55, 55, 58, 59, 60, 31, 63, 66, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 49, 51, 55, 55, 58, 59, 31, 60, 63, 66, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 49, 51, 55, 55, 58, 31, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 49, 51, 55, 55, 31, 58, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 49, 51, 55, 31, 55, 58, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 49, 51, 31, 55, 55, 58, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 49, 31, 51, 55, 55, 58, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 31, 49, 51, 55, 55, 58, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 31, 49, 49, 51, 55, 55, 58, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 31, 48, 49, 49, 51, 55, 55, 58, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 31, 46, 48, 49, 49, 51, 55, 55, 58, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 31, 44, 46, 48, 49, 49, 51, 55, 55, 58, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 31, 39, 44, 46, 48, 49, 49, 51, 55, 55, 58, 59, 60, 63, 66, 69, 77, 91, 92] [81, 10, 12, 13, 16, 23, 27, 30, 30, 31, 31, 36, 39, 44, 46, 48, 49, 49, 51, 55, 55, 58, 59, 60, 63, 66, 69, 77, 91, 92]
#zoznam po kazdej vymene
zoznam = [81, 23, 66, 46, 77, 44, 59, 36, 30, 16, 10, 55, 91, 31, 13, 92, 63, 69, 39, 30, 49, 60, 51, 48, 27, 12, 55, 58, 49, 31]
for index in range(1, len(zoznam)):
#zaradime kartu na danom indexe na spravnu poziciu vlavo, prebuble do uz usporiadanej casti
i = index-1
while i >= 0 and zoznam[i] > zoznam[i+1]: #prebublanie dolava
zoznam[i], zoznam[i+1] = zoznam[i+1], zoznam[i]
i -= 1
print(zoznam[:index+1]) #uz usporiadana cast
[23, 81] [23, 66, 81] [23, 46, 66, 81] [23, 46, 66, 77, 81] [23, 44, 46, 66, 77, 81] [23, 44, 46, 59, 66, 77, 81] [23, 36, 44, 46, 59, 66, 77, 81] [23, 30, 36, 44, 46, 59, 66, 77, 81] [16, 23, 30, 36, 44, 46, 59, 66, 77, 81] [10, 16, 23, 30, 36, 44, 46, 59, 66, 77, 81] [10, 16, 23, 30, 36, 44, 46, 55, 59, 66, 77, 81] [10, 16, 23, 30, 36, 44, 46, 55, 59, 66, 77, 81, 91] [10, 16, 23, 30, 31, 36, 44, 46, 55, 59, 66, 77, 81, 91] [10, 13, 16, 23, 30, 31, 36, 44, 46, 55, 59, 66, 77, 81, 91] [10, 13, 16, 23, 30, 31, 36, 44, 46, 55, 59, 66, 77, 81, 91, 92] [10, 13, 16, 23, 30, 31, 36, 44, 46, 55, 59, 63, 66, 77, 81, 91, 92] [10, 13, 16, 23, 30, 31, 36, 44, 46, 55, 59, 63, 66, 69, 77, 81, 91, 92] [10, 13, 16, 23, 30, 31, 36, 39, 44, 46, 55, 59, 63, 66, 69, 77, 81, 91, 92] [10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 55, 59, 63, 66, 69, 77, 81, 91, 92] [10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 55, 59, 63, 66, 69, 77, 81, 91, 92] [10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 55, 59, 60, 63, 66, 69, 77, 81, 91, 92] [10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 49, 51, 55, 59, 60, 63, 66, 69, 77, 81, 91, 92] [10, 13, 16, 23, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 81, 91, 92] [10, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 81, 91, 92] [10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 59, 60, 63, 66, 69, 77, 81, 91, 92] [10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 55, 59, 60, 63, 66, 69, 77, 81, 91, 92] [10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 55, 58, 59, 60, 63, 66, 69, 77, 81, 91, 92] [10, 12, 13, 16, 23, 27, 30, 30, 31, 36, 39, 44, 46, 48, 49, 49, 51, 55, 55, 58, 59, 60, 63, 66, 69, 77, 81, 91, 92] [10, 12, 13, 16, 23, 27, 30, 30, 31, 31, 36, 39, 44, 46, 48, 49, 49, 51, 55, 55, 58, 59, 60, 63, 66, 69, 77, 81, 91, 92]
Najmenej porovnaní aj výmen, ak je už usporiadaná postupnosť ...
najviac ak je usporiadaná opačne
# Usporiadanie spájaním `MergeSort`
def usporiadanie_spajanim(pole):
#rozdelime na 2 casti
stred = len(pole)//2
pole_lava = pole[:stred]
pole_prava = pole[stred:]
#panujeme = rekurzivne vypocitame mensie casti
usp_lava = usporiadanie_spajanim(pole_lava)
usp_prava = usporiadanie_spajanim(pole_prava)
#zlucenie
vysledok = []
while len(usp_lava) > 0 and len(usp_prava) > 0:
if usp_lava[0] < usp_prava[0]:
vysledok.append(usp_lava.pop(0)) #vyberiem prvy prvok z zavej casti
else:
vysledok.append(usp_prava.pop(0)) #vyberiem prvy prvok z zavej casti
#zostali iba v jednej casti
vysledok.extend(usp_lava+usp_prava)
return vysledok
zoznam = [81, 23, 66, 46, 77, 44, 59, 36, 30, 16, 10, 55, 91, 31, 13, 92, 63, 69, 39, 30, 49, 60, 51, 48, 27, 12, 55, 58, 49, 31]
usporiadanie_spajanim(zoznam)
def usporiadanie_spajanim(pole):
if len(pole) < 2:
return pole
#rozdelime na 2 casti
stred = len(pole)//2
pole_lava = pole[:stred]
pole_prava = pole[stred:]
#panujeme = rekurzivne vypocitame mensie casti
usp_lava = usporiadanie_spajanim(pole_lava)
usp_prava = usporiadanie_spajanim(pole_prava)
#zlucenie
vysledok = []
while len(usp_lava) > 0 and len(usp_prava) > 0:
if usp_lava[0] < usp_prava[0]:
vysledok.append(usp_lava.pop(0)) #vyberiem prvy prvok z zavej casti
else:
vysledok.append(usp_prava.pop(0)) #vyberiem prvy prvok z zavej casti
#zostali iba v jednej casti
vysledok.extend(usp_lava+usp_prava)
return vysledok
zoznam = [81, 23, 66, 46, 77, 44, 59, 36, 30, 16, 10, 55, 91, 31, 13, 92, 63, 69, 39, 30, 49, 60, 51, 48, 27, 12, 55, 58, 49, 31]
print(*usporiadanie_spajanim(zoznam))
10 12 13 16 23 27 30 30 31 31 36 39 44 46 48 49 49 51 55 55 58 59 60 63 66 69 77 81 91 92
def usporiadanie_spajanim(pole):
if len(pole) < 2:
return pole
#rozdelime na 2 casti
stred = len(pole)//2
pole_lava = pole[:stred]
pole_prava = pole[stred:]
print('Rozdelenie', pole_lava, ' | ', pole_prava)
#panujeme = rekurzivne vypocitame mensie casti
usp_lava = usporiadanie_spajanim(pole_lava)
usp_prava = usporiadanie_spajanim(pole_prava)
#zlucenie
vysledok = []
while len(usp_lava) > 0 and len(usp_prava) > 0:
if usp_lava[0] < usp_prava[0]:
vysledok.append(usp_lava.pop(0)) #vyberiem prvy prvok z zavej casti
else:
vysledok.append(usp_prava.pop(0)) #vyberiem prvy prvok z zavej casti
#zostali iba v jednej casti
vysledok.extend(usp_lava+usp_prava)
print('Spojenie', vysledok)
return vysledok
zoznam = [81, 23, 66, 46, 77, 44, 59, 36, 30, 16, 10, 55, 91, 31, 13, 92, 63, 69, 39, 30, 49, 60, 51, 48, 27, 12, 55, 58, 49, 31]
print(*usporiadanie_spajanim(zoznam))
Rozdelenie [81, 23, 66, 46, 77, 44, 59, 36, 30, 16, 10, 55, 91, 31, 13] | [92, 63, 69, 39, 30, 49, 60, 51, 48, 27, 12, 55, 58, 49, 31] Rozdelenie [81, 23, 66, 46, 77, 44, 59] | [36, 30, 16, 10, 55, 91, 31, 13] Rozdelenie [81, 23, 66] | [46, 77, 44, 59] Rozdelenie [81] | [23, 66] Rozdelenie [23] | [66] Spojenie [23, 66] Spojenie [23, 66, 81] Rozdelenie [46, 77] | [44, 59] Rozdelenie [46] | [77] Spojenie [46, 77] Rozdelenie [44] | [59] Spojenie [44, 59] Spojenie [44, 46, 59, 77] Spojenie [23, 44, 46, 59, 66, 77, 81] Rozdelenie [36, 30, 16, 10] | [55, 91, 31, 13] Rozdelenie [36, 30] | [16, 10] Rozdelenie [36] | [30] Spojenie [30, 36] Rozdelenie [16] | [10] Spojenie [10, 16] Spojenie [10, 16, 30, 36] Rozdelenie [55, 91] | [31, 13] Rozdelenie [55] | [91] Spojenie [55, 91] Rozdelenie [31] | [13] Spojenie [13, 31] Spojenie [13, 31, 55, 91] Spojenie [10, 13, 16, 30, 31, 36, 55, 91] Spojenie [10, 13, 16, 23, 30, 31, 36, 44, 46, 55, 59, 66, 77, 81, 91] Rozdelenie [92, 63, 69, 39, 30, 49, 60] | [51, 48, 27, 12, 55, 58, 49, 31] Rozdelenie [92, 63, 69] | [39, 30, 49, 60] Rozdelenie [92] | [63, 69] Rozdelenie [63] | [69] Spojenie [63, 69] Spojenie [63, 69, 92] Rozdelenie [39, 30] | [49, 60] Rozdelenie [39] | [30] Spojenie [30, 39] Rozdelenie [49] | [60] Spojenie [49, 60] Spojenie [30, 39, 49, 60] Spojenie [30, 39, 49, 60, 63, 69, 92] Rozdelenie [51, 48, 27, 12] | [55, 58, 49, 31] Rozdelenie [51, 48] | [27, 12] Rozdelenie [51] | [48] Spojenie [48, 51] Rozdelenie [27] | [12] Spojenie [12, 27] Spojenie [12, 27, 48, 51] Rozdelenie [55, 58] | [49, 31] Rozdelenie [55] | [58] Spojenie [55, 58] Rozdelenie [49] | [31] Spojenie [31, 49] Spojenie [31, 49, 55, 58] Spojenie [12, 27, 31, 48, 49, 51, 55, 58] Spojenie [12, 27, 30, 31, 39, 48, 49, 49, 51, 55, 58, 60, 63, 69, 92] Spojenie [10, 12, 13, 16, 23, 27, 30, 30, 31, 31, 36, 39, 44, 46, 48, 49, 49, 51, 55, 55, 58, 59, 60, 63, 66, 69, 77, 81, 91, 92] 10 12 13 16 23 27 30 30 31 31 36 39 44 46 48 49 49 51 55 55 58 59 60 63 66 69 77 81 91 92
$O(n \cdot \log n)$ - časová zložitosť, teda počet porovnaní v najhoršom prípade
n | 1.000 | 1.000.000 |
---|---|---|
$O(n^2)$ | 1.000.000 | 1.000.000.000.000 |
$O(n \cdot \log n)$ | 10.000 | 20.000.000 |
Potrebujeme ale dvakrát toľko pamäte (pomocné pole), nejde o usporiadanie na mieste in place/situ
(keď potrebujeme najviac $O(\log n)$ pamäte.
def usporiadanie_rychle(pole):
print(pole)
if len(pole) < 2:
return pole
pivot = pole[0] #zoberme prvy prvok ako pivota
return usporiadanie_rychle([prvok for prvok in pole if prvok < pivot]) \
+[pivot] \
+ usporiadanie_rychle([prvok for prvok in pole if prvok > pivot])
usporiadanie_rychle([1,5,7,8,9,3,0,])
[1, 5, 7, 8, 9, 3, 0] [0] [5, 7, 8, 9, 3] [3] [7, 8, 9] [] [8, 9] [] [9]
[0, 1, 3, 5, 7, 8, 9]
zoznam = [81, 23, 66, 46, 77, 44, 59, 36, 30, 16, 10, 55, 91, 31, 13, 92, 63, 69, 39, 30, 49, 60, 51, 48, 27, 12, 55, 58, 49, 31]
usporiadanie_rychle(zoznam)
[81, 23, 66, 46, 77, 44, 59, 36, 30, 16, 10, 55, 91, 31, 13, 92, 63, 69, 39, 30, 49, 60, 51, 48, 27, 12, 55, 58, 49, 31] [23, 66, 46, 77, 44, 59, 36, 30, 16, 10, 55, 31, 13, 63, 69, 39, 30, 49, 60, 51, 48, 27, 12, 55, 58, 49, 31] [16, 10, 13, 12] [10, 13, 12] [] [13, 12] [12] [] [] [66, 46, 77, 44, 59, 36, 30, 55, 31, 63, 69, 39, 30, 49, 60, 51, 48, 27, 55, 58, 49, 31] [46, 44, 59, 36, 30, 55, 31, 63, 39, 30, 49, 60, 51, 48, 27, 55, 58, 49, 31] [44, 36, 30, 31, 39, 30, 27, 31] [36, 30, 31, 39, 30, 27, 31] [30, 31, 30, 27, 31] [27] [31, 31] [] [] [39] [] [59, 55, 63, 49, 60, 51, 48, 55, 58, 49] [55, 49, 51, 48, 55, 58, 49] [49, 51, 48, 49] [48] [51] [58] [63, 60] [60] [] [77, 69] [69] [] [91, 92] [] [92]
[10, 12, 13, 16, 23, 27, 30, 31, 36, 39, 44, 46, 48, 49, 51, 55, 58, 59, 60, 63, 66, 69, 77, 81, 91, 92]
len(usporiadanie_rychle(zoznam))
[81, 23, 66, 46, 77, 44, 59, 36, 30, 16, 10, 55, 91, 31, 13, 92, 63, 69, 39, 30, 49, 60, 51, 48, 27, 12, 55, 58, 49, 31] [23, 66, 46, 77, 44, 59, 36, 30, 16, 10, 55, 31, 13, 63, 69, 39, 30, 49, 60, 51, 48, 27, 12, 55, 58, 49, 31] [16, 10, 13, 12] [10, 13, 12] [] [13, 12] [12] [] [] [66, 46, 77, 44, 59, 36, 30, 55, 31, 63, 69, 39, 30, 49, 60, 51, 48, 27, 55, 58, 49, 31] [46, 44, 59, 36, 30, 55, 31, 63, 39, 30, 49, 60, 51, 48, 27, 55, 58, 49, 31] [44, 36, 30, 31, 39, 30, 27, 31] [36, 30, 31, 39, 30, 27, 31] [30, 31, 30, 27, 31] [27] [31, 31] [] [] [39] [] [59, 55, 63, 49, 60, 51, 48, 55, 58, 49] [55, 49, 51, 48, 55, 58, 49] [49, 51, 48, 49] [48] [51] [58] [63, 60] [60] [] [77, 69] [69] [] [91, 92] [] [92]
26
! zmizli opakujúce sa prvky
#3-cestne usporiadanie
def usporiadanie_rychle(pole):
# print(pole)
if len(pole) < 2:
return pole
pivot = pole[0] #zoberme prvy prvok ako pivota
return usporiadanie_rychle([prvok for prvok in pole if prvok < pivot]) \
+[prvok for prvok in pole if prvok ==pivot] \
+ usporiadanie_rychle([prvok for prvok in pole if prvok > pivot])
len(usporiadanie_rychle(zoznam))
30
https://www.youtube.com/watch?v=GIvjJwzrHBU (Listening to Sorting Algorithms!)
https://www.toptal.com/developers/sorting-algorithms (Sorting Algorithms Animations)
https://imgur.com/gallery/voutF (Sorting Algorithms Visualized)
https://sortvisualizer.com/ (Sort Visualizer)