# pmp005
# dekorator_siralama_algo.py
"""
tarih: 20191215
orijinal kodlar: https://www.daniweb.com/programming/software-development/code/216689/sorting-algorithms-in-python
düzenleme: ahmet aksoy (ax)
python: python-3.7.4
os: ubuntu 18.04 lts
"""
import random
import time
NSAY = 1000 # Sıralanacak eleman sayısı
tlist = [] # tam sayılardan oluşan eleman listesi
PRINT = False
gentoplam=0
# tlist listesini rasgele tam sayılarla doldur
for i in range(0, NSAY):
tlist.append(random.randint(0, NSAY*10))
# dekoratör fonksiyonun tanımlanması
def print_toplam_gecen_sure(func):
def ic_fonksiyon(*arg):
global gentoplam
t0 = time.perf_counter() # fonksiyonun başlangıç zamanı
orijinal_fonksiyon = func(*arg) # Orijinal fonksiyon
t = time.perf_counter() # fonksiyonun bitiş zamanı
fad = func.__name__ # fonksiyonun adı
print(f"{fad:20s} {(t - t0)*1000.0:0.3f} ms")
gentoplam+=(t-t0)*1000
return orijinal_fonksiyon
return ic_fonksiyon
# bubblesort
@print_toplam_gecen_sure # dekoratör fonksiyon
def bubblesort(liste):
for i in range(len(liste)):
for k in range(len(liste) - 1, i, -1):
if (liste[k] < liste[k - 1]):
liste[k],liste[k-1] = liste[k-1],liste[k]
# insertion_sort
@print_toplam_gecen_sure
def insertion_sort(liste):
for i in range(1, len(liste)):
j = i
while j > 0 and liste[j] < liste[j - 1]:
liste[j], liste[j-1] = liste[j - 1], liste[j]
j -= 1
# selection_sort
@print_toplam_gecen_sure
def selection_sort(liste):
for i in range(0, len(liste)):
min = i
for j in range(i + 1, len(liste)):
if liste[j] < liste[min]:
min = j
liste[i], liste[min] = liste[min], liste[i]
# merge_sort
@print_toplam_gecen_sure
def merge_sort(liste):
msort_rec(liste, 0, len(liste) - 1)
def merge(lst, left, mid, right):
newlist = []
i, j = left, mid + 1
n = left
while n < right + 1:
if i > mid:
newlist.append(lst[j])
j += 1
elif j > right:
newlist.append(lst[i])
i += 1
elif lst[j] < lst[i]:
newlist.append(lst[j])
j += 1
else:
newlist.append(lst[i])
i += 1
n += 1
n = 0
for k in (range(left, right + 1)):
lst[k] = newlist[n]
n += 1
def msort_rec(liste, left, right):
if len(liste) is 0:
return
if right <= left:
return
else:
mid = (left + right) // 2
msort_rec(liste, left, mid)
msort_rec(liste, mid + 1, right)
merge(liste, left, mid, right)
# heap_sort - yığın sıralama
@print_toplam_gecen_sure
def heap_sort(liste):
heapsort(liste)
def heapsort(liste):
# convert list into heap
boy = len(liste) - 1
leastParent = boy // 2
for i in range(leastParent, -1, -1):
go_down(liste, i, boy)
# convert heap into sorted list
for i in range(boy, 0, -1):
if liste[0] > liste[i]:
liste[0], liste[i] = liste[i], liste[0]
go_down(liste, 0, i - 1)
def go_down(liste, ilk, son):
maximum = 2 * ilk + 1
while maximum <= son:
if (maximum < son) and (liste[maximum] < liste[maximum + 1]):
maximum += 1
if liste[maximum] > liste[ilk]:
liste[maximum], liste[ilk] = liste[ilk], liste[maximum]
ilk = maximum
maximum = 2 * ilk + 1
else:
return
# quick_sort
@print_toplam_gecen_sure
def quick_sort(liste):
qsort(liste, 0, len(liste) - 1)
def qsort(liste, ilk, son):
if ilk >= son:
return liste
eleman = random.randrange(ilk, son + 1)
yeni_eleman = parca(liste, ilk, son, eleman)
qsort(liste, ilk, yeni_eleman - 1)
qsort(liste, yeni_eleman + 1, son)
def parca(liste, ilk, son, eleman):
liste[eleman], liste[son] = liste[son], liste[eleman]
gecici = ilk
for i in range(ilk, son):
if liste[i] < liste[son]:
liste[i], liste[gecici] = liste[gecici], liste[i]
gecici += 1
liste[gecici], liste[son] = liste[son], liste[gecici]
return gecici
# shell_sort - kabuk sıralama
@print_toplam_gecen_sure
def shell_sort(liste):
n = len(liste)
aralik = n//2
while aralik>0:
for i in range(aralik,n):
gecici=liste[i]
j=i
while j>= aralik and liste[j-aralik]>gecici:
liste[j]=liste[j-aralik]
j-=aralik
liste[j]=gecici
aralik //= 2
# sort: ön tanımlı python sıralaması (timsort)
@print_toplam_gecen_sure
def python_sort(liste):
liste.sort()
def check(liste1,liste2):
if len(liste1) != len(liste2):
print("Liste uzunlukları farklı!")
else:
toplam=0
for j in range(len(liste1)):
toplam+=(liste1[j]-liste2[j])*(liste1[j]-liste2[j])
if toplam>0:
print("Liste toplamları uyuşmuyor!")
if PRINT:
print(liste2)
if __name__ == "__main__":
liste = tlist.copy()
bubblesort(liste)
if PRINT:
print(liste)
zliste = liste.copy()
liste=tlist.copy()
insertion_sort(liste)
check(zliste,liste)
liste = tlist.copy()
selection_sort(liste)
check(zliste,liste)
liste=tlist.copy()
merge_sort(liste)
check(zliste,liste)
liste=tlist.copy()
heap_sort(liste)
check(zliste,liste)
liste = tlist.copy()
quick_sort(liste)
check(zliste,liste)
liste=tlist.copy()
shell_sort(liste)
check(zliste,liste)
liste=tlist.copy()
python_sort(liste)
check(zliste,liste)
print(f"Toplam süre = {gentoplam:.2f} ms")
"""
Kaynaklar:
https://www.daniweb.com/programming/software-development/code/216689/sorting-algorithms-in-python
https://medium.com/@george.seif94/a-tour-of-the-top-5-sorting-algorithms-with-python-code-43ea9aa02889
https://www.tutorialspoint.com/python_data_structure/python_sorting_algorithms.htm
https://makeartwithpython.com/blog/visualizing-sort-algorithms-in-python/
https://fw-geekycoder.blogspot.com/2012/04/sorting-algorithms-in-python.html
for visualization
https://github.com/nrsyed/sorts/blob/master/python/sorts.py
"""