Python & Java Karşılaştırma (Sıralama Algoritmaları)

Her bilgisayar mühendisinin, algoritma dersinde öğrendiği temel konulardan biridir Sıralama Algoritmaları (Sorting Algorithms). Bu konunun temel amacı veri kümemizi en hızlı ve en az karmaşıklıkla sıraya koymaktır. Verinin boyutuna, düzenine göre uygun olan algoritmayı kullanmak ya da makul bir çözüm bulmayı öğrenmişizdir ya da en azından buna benzer şeyler görmüşüzdür :)

Nitekim bir çok matematik, analiz ve/veya istatistik probleminde verileri belirli bir düzene koyma işi karşımıza çıkmaktadır. Yazılımcıların her zaman karşına çıkan bu problemi tekrar gözden geçirmek, sıralama algoritmalarını hatırlamak için böyle bir yazı yazmaya karar verdim.

Aslında herşey python mu yoksa diğer object-oriented ya da script dilleri mi daha hızlı sorusuyla başladı :d. Bunu da en güzel denemenin yolu verilerle işlemler yapmaktır zaten. Denediğim diller arasında Python, C(makine diline en çabuk çevrilen en alt seviye dil olması sebebiyle) ve Java'dan sonra en hızlı programlama dili çıktı. Java için Eclipse, Python için IDLE kullanılmıştır. Burada yazılan kodların sadece Python olanları bana aittir. Diğer dillerin implementasyonları (Türkçe karşılığını bulamadım malesef) internetten bulunmuştur. Gelelim üzerinde test yaptığımız sıralama algoritmalarına. Aşağıda yaptığım açıklamalar çok yüzeyseldir. Daha detaylı bilgileri wikipedia da ingilizce isimlerini aratarak bulabilirsiniz, ya da kodu inceleyerek kendi analizinizi yapabilirsiniz.

Insertion Sort (Eklemeli Sıralama)
Düzensiz her elemanın yanındakiyle karşılaştırılarak duruma göre yer değiştirmesi sonucu düzenli dizin oluşturulan algoritmadır. Burada dizinin ikinci elemanından başlayarak son elemana kadar, her elemanla tek tek karşılaştırılmasıyla düzene konduğu algoritmadır.
Örnek Dizi: 5-3-1-8-6
1> 5-3-1-8-6
2> 3-5-1-8-6
3> 3-1-5-8-6
4> 1-3-5-8-6
5> 1-3-5-6-8

Buble Sort (Kabarcık Sıralama)
Dizinin ilk elemanından başlanarak ikili kıyaslama yapılmasıyla sıraya koyulan algoritmadır. n elemanlı dizide birinci geçişte n-1 kıyaslama yapılır. Bu n-1 karşılaştırmadan n-2 defa yapıldığı için karmaşıklık n[kare] dir.
Örnek Dizi: 5-3-1-8
1a) 5-3-1-8 > 3-5-1-8
1b) 3-5-1-8 > 3-1-5-8
1c) 3-5-1-8 > 3-1-5-8

2a) 3-1-5-8 > 1-3-5-8
2b) 1-3-5-8 > 1-3-5-8
2c) 1-3-5-8 > 1-3-5-8

Selection Sort (Seçmeli Sıralama)
Sıradaki elemanın, dizinin geri kalanın en küçüğü (ya da en büyüğü) ile kıyaslanıp, yer değiştirme olması durumunda diğer dizi elemanlarının bir sıra ileri kaydırılıp sıralamanın yapıldığı algoritmadır. İlk kıyaslamada, geri kalan sayıların en küçüğü bulunurken n-1 karşılaştırma yapılır. Sonrakinde n-2. En sonunda 1. n-1 + n-2 + ... + 1 = n (n-1) / 2. Yani karmaşıklık n[kare] dir.
Örnek Dizi: 5-3-1-8-6
1) 5 - (3 - 1 - 8 - 6) - min:1 > 1-5-3-8-6
2) 1 - 5 - (3 - 8 - 6) - min:3 > 1-3-5-8-6
3) 1 - 3 - 5 - (8 - 6) - min:6 > 1-3-5-6-8

Heap Sort (Yığın/Öbek Sıralaması)
Verilen düzensiz dizi öncelikle öbek(heap) yapısı haline getirilir. Öbek, her düğümün çocuğundan büyük olduğu özel bir ikili ağaçtır. Bu ağaç üzerinde karşılaştırmalara yapılarak veriler sıralı düzene getirilir. Öbek yapısının ilk düğümü her zaman en büyük olacaktır. İlk düğüm seçilip yeni bir dizinin ilk ya da son (büyüyen/küçülen diziye göre) elemanına atanır. Öbek yapısı tekrar oluşturulur, haliyle bir önceki yapıda çekilen düğümün çocuklarından büyük olan yeni yapının ilk düğümü olur. O da çekilip yeni dizinin sıradaki elemanına atanır. Bu işlem öbek bitene kadar tekrarlanır. Sonunda elimizde sıralanmış dizi olur.
Örnek Dizi: 5-3-1-8-6
1) Öbek Yap (8-5-6-1-3)
2) Öbek Yap (6-5-1-3) > 8
3) Öbek Yap (5-1-3) > 8-6
4) Öbek Yap (3-1) > 8-6-5
5) 8-6-5-3-1

Merge Sort (Birleştirme Sıralaması)
Sıralanacak dizi, iki ya da daha az eleman kalacak şekilde ikiye parçalandıktan sonra parçaların sıraya dizilip birleştirilmesiyle düzenlenir. Bu yönteme böl fethet (divide and conquer) denir. Karmaşklığı düşüktür (n logn) fakat bellek harcaması fazladır.
Örnek Dizi: 5-3-1-8-6-4-7-2
1) Böl: 5-3-1-8 / 6-4-7-2
2) Böl: 5-3 / 1-8 / 6-4 / 7-2
Fethet:
3) Sırala: 3-5 / 1-8 / 4-6 / 2-7
4) Birleştir: 1-3-5-8 / 2-4-6-7 (birleştirirken karşılaştırmalar yapılmaktadır, yer kaplayan kısım burasıdır)
5) Birleştir: 1-2-3-4-5-6-7-8

Sıralama algoritmaları hakkında yeterli açıklama için wikipedia'yı [1] okuyabilirsiniz. Kıyaslama tablosuna göz atmak da fayda var. Görsel canladırmaları için de aşağıdaki site [2] gayet başarılı. Karışık, az sıralı diziler için animasyonlara bakabilirsiniz. Kod içerisinde python'un kendi heap ve sort methodları bulunmaktadır. Sıralama sonuçlarına bakıldığında en iyi değerler bunlarda çıkmaktadır. Bunun sebebi bu yordamlarda pythonun kendine özel veri tiplerini (tupple) kullanarak eşleme yaptığı verilere üzerinde sıralama yapmasıdır. [3]


Gelelim python kod implementasyonu, sonuçları ve diğer dillerle karşılaştırılmasına...
Üzerinde koşulan donanım: İşlemci - Intel(R) Core(TM) Duo CPU T2350 @ 1.86GHz / Bellek - 1giga
işletim sistemi: Ubuntu 10.4 - lucid

Kod -----
#!/usr/bin/env python
# -*- coding: ISO-8859-9 -*-

import sys
import random
import time
import heapq
import locale

class SortingAlgorithms:
"""This class involves sorting algorithms functions. Complexity, memory usage, and
complexity statistics will be showed. As an example data pythons random library used
and lists with n(got by user) elements are sorted. """

def __init__(self, unsortedList):
self.tmpList = unsortedList
self.length = len(unsortedList)

def InsertionSort(self):
for x in range(1,self.length):
y = x
while(y>0):
if(self.tmpList[y]
self.tmpList[y-1], self.tmpList[y] = self.tmpList[y], self.tmpList[y-1]
y = y - 1

def BubbleSort(self):
for x in range(self.length):
y = x + 1
while(y <>
if (self.tmpList[y] <>
self.tmpList[y-1], self.tmpList[y] = self.tmpList[y], self.tmpList[y-1]
y = y + 1

def SelectionSort(self):
for x in range(self.length - 1):
minimum = x
y = x + 1
while(y
if(self.tmpList[y] <>
mimimum = y
y = y + 1

if( minimum != x):
self.tmpList[x], self.tmpList[minimum] = self.tmpList[minimum],self.tmpList[x]

def NormalHeapSort(self):
def shiftDown(start, count):
root = start

while root * 2 + 1 <>
child = root * 2 + 1
if child <>
child += 1
if self.tmpList[root] <>
self.tmpList[root], self.tmpList[child] = self.tmpList[child], self.tmpList[root]
root = child
else:
return

start = self.length / 2 - 1
end = self.length - 1

while start >= 0:
shiftDown(start, self.length)
start -= 1

while end > 0:
self.tmpList[end], self.tmpList[0] = self.tmpList[0], self.tmpList[end]
shiftDown(0, end)
end -= 1

def MergeSort(self, unsortedList):
def merge(left, right):
result = []
i ,j = 0, 0
while(i <>
if (left[i] <= right[j]):
result.append(left[i])
i = i + 1
else:
result.append(right[j])
j = j + 1
result += left[i:]
result += right[j:]
return result

if len(unsortedList) <>
return unsortedList
else:
middle = len(unsortedList) / 2
left = self.MergeSort(unsortedList[:middle])
right = self.MergeSort(unsortedList[middle:])
return merge(left, right)

def PythonHeapSort(self):
self.tmpList = heapq.nlargest(self.length, self.tmpList)


if __name__ == "__main__":
print "Kaç elemanlı diziyi sıralamak istersiniz?"
n = input()
intList = random.sample(xrange(n*2), n)
print intList
print "\nGeçen Süre"

Sorter = SortingAlgorithms(intList)
beginTime = time.clock()
Sorter.InsertionSort()
endTime = time.clock()
print "\nInsertion Sort >", (endTime - beginTime)
Sorter = SortingAlgorithms(intList)
beginTime = time.clock()
Sorter.BubbleSort()
endTime = time.clock()
print "\nBubble Sort >", (endTime - beginTime)

Sorter = SortingAlgorithms(intList)
beginTime = time.clock()
Sorter.SelectionSort()
endTime = time.clock()
print "\nSelection Sort >", (endTime - beginTime)

Sorter = SortingAlgorithms(intList)
beginTime = time.clock()
Sorter.NormalHeapSort()
endTime = time.clock()
print "\nNormal Heap Sort >", (endTime - beginTime)

Sorter = SortingAlgorithms(intList)
beginTime = time.clock()
Sorter.PythonHeapSort()
endTime = time.clock()
print "\nPython Heap Sort >", (endTime - beginTime)

Sorter = SortingAlgorithms(intList)
beginTime = time.clock()
Sorter.MergeSort(intList)
endTime = time.clock()
print "\nMerge Sort >", (endTime - beginTime)

Sorter = SortingAlgorithms(intList)
beginTime = time.clock()
intList.sort()
endTime = time.clock()
print "\nPython Sort >", (endTime - beginTime)


SONUÇ

Kaç elemanlı diziyi sıralamak istersiniz?
100
[150, 145, 155, 57, 18, 198, 178, 70, 103, 64, 66, 117, 153, 30, 127, 15, 109, 121, 46, 43, 88, 170, 84, 96, 97, 35, 124, 47, 129, 185, 191, 169, 63, 40, 176, 69, 116, 76, 144, 156, 162, 133, 123, 4, 177, 24, 199, 80, 23, 182, 157, 175, 174, 38, 141, 194, 111, 187, 68, 78, 193, 75, 171, 165, 196, 137, 106, 21, 147, 114, 138, 71, 29, 67, 59, 192, 181, 119, 136, 151, 110, 50, 31, 79, 28, 104, 184, 168, 26, 122, 7, 92, 12, 60, 152, 8, 98, 188, 83, 100]

Geçen Süre
Insertion Sort > 0.004315352928933706
Bubble Sort > 0.002731911458020502
Selection Sort > 0.002764597176456784
Normal Heap Sort > 0.0015809271848796422
Python Heap Sort > 3.5200004469843754e-05
Merge Sort > 0.001170260466064825
Python Sort > 1.117460459360009e-05

Aynı dizi için sadece java merge sort denenmiştir.
Sonuç: 244444 nanosaniye. Yani 0.244-e03

--------------------------------------------------------------------------------------

Kaç elemanlı diziyi sıralamak istersiniz?
1000
Geçen Süre
Insertion Sort > 0.19723847583980644
Bubble Sort > 0.12029573591056963
Selection Sort > 0.11590551313085884
Normal Heap Sort > 0.010408026718479513
Python Heap Sort > 5.587302296805596e-05
Merge Sort > 0.006195480151807042
Python Sort > 3.100952774726107e-05


Aynı dizi için sadece java merge sort denenmiştir.
Sonuç: 785016 nanosaniye. Yani 0.785-e03
--------------------------------------------------------------------------------------

Kaç elemanlı diziyi sıralamak istersiniz?
10000
Geçen Süre
Insertion Sort > 20.581436467483996
Bubble Sort > 11.75080771438828
Selection Sort > 12.1826413692243
Normal Heap Sort > 0.14290671021037582
Python Heap Sort > 0.00046179053483541566
Merge Sort > 0.076276454130344
Python Sort > 0.0003033905147162841

1000 ve 10000 elemanlı diziler ekte verilmiştir.

Referanslar
[1] - http://en.wikipedia.org/wiki/Sorting_algorithm
[2] - http://www.sorting-algorithms.com
[3] - http://wiki.python.org/moin/PythonSpeed/PerformanceTips#Sorting

Comments

Unknown said…
X++ veya C# Dilinde de bir örnek verirsen,kanımca daha bir mükemmel olur...
Unknown said…
çok güzel bir yazı olmuş elinize sağlık

Popular posts from this blog

JACKSON ile JSON işleme

Python - Türkçe Karakter Problemi