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"