Brute Force - Selection Sort and Bubble Sort

Kategori: Algorithm Design and Analysis , 11 Haziran 2020 , JanFranco


Algoritma analizlerini görmüştük. Artık algoritma türlerine giriş yapabiliriz. İlk bahseceğimiz algoritma türü Brute Force olacaktır. Brute force algoritmalarda bir kaba kuvvet söz konusudur. Çok kolay tasarlanıp implement edilebilir fakat diğer algoritmalara göre daha yavaş çalışabilirler. Bir kaç algoritmaya göz atalım, selection sort ve bubble sort.

Sorting algoritmalarında amaç, verilen n kadar nesneyi büyükten küçüğe veya küçükten büyüğe bir düzene sokmaktır. Şuana kadar yazılmış onlarca sıralama algoritması bulunabilir fakat brute force tasarım tekniğini incelediğimiz için selection sort ve bubble sort algoritmalarını inceyeceğiz.

Selection sort algoritmasında dizi baştan sona minimum elemanı bulmak için taranır. Bulunan minimum eleman sıralanmamış dizinin en başına yazılır. Sahte kodu görelim:


Algorithm SelectionSort(A[0..n-1)

for i <- 0 to n - 2 do
    min <- i
	for j <- i + 1 to n - 1 do
	    if A[j] < A[min]
		min <- j
	swap A[i] and A[min]
Zaman etkinliğini bulalım:

C(n) = sum(i=0 to n-2) sum(j=i+1 to n-1) 1 = sum(i=0 to n-2) (n-1-i) = n(n-1)/2 (n^2 - n)

Örnek bir dizi üzerinden inceleyelim:



i = 0 adımında dizinin minimum elemanını 17 olarak bulduk. 0. indexteki eleman ile 17'yi yer değiştirdik. i = 1 adımında minimum eleman olarak 29'u bulduk. 1. indexteki 45 sayısı ile 29 yer değiştirdi. Bu şekilde n-1'e kadar devam edecek ve son adımda dizi sıralanmış olacak. Algoritmanın adındaki gibi her adımda seçerek sıralıyoruz. Bir diğer brute force sorting algoritması olan bubble sort'u inceleyelim:


Algorithm BubbleSort(A[0..n-1])

for i <- 0 to n - 2 do
    for j <- 0 to n - 2 - i do
	if A[j+1] < A[j]
	    swap A[j] and A[j+1]
Bu sahte kodu bir örnek ile canlandıralım:



Dizideki elemanlar sırasıyla kendisinden bir sonraki eleman ile karşılaştırılır. Eğer bir düzensizlik var ise elemanlar kendi aralarında yer değiştirir. j = 0 adımında 89 ile 45'i kontrol ettik ve burada bir düzensizlik tespit ederek iki sayıyı yer değiştirdik. j = 1 adımında 89 ve 68 sayılarını kontrol ettik ve yer değiştirdik. j = 3 adımında 89 ve 90 sayılarını kontrol ettik, burada bir düzensizlik olmadığından j = 4 adımına geçtik. Bu adımda da 90 ve 29 sayılarını kontrol ettik ve yer değiştirdik. Bu şekilde j = n-2 olana kadar devam ettik. Daha sonra i = 1 adımında aynı işlemleri tekrar ettik. Zaman etkinliğine de bakalım:

C(n) = sum(i=0 to n-2) sum(j=0 to n-2-i) 1 = sum(i=0 to n-2) [(n-2-i)-0+1] = sum(i=0 to n-2) (n-1-i) = n(n-1)/2 n(n-1)/2 € O(n^2)


Sonraki Yazı: Sequential Search and Brute Force String Matching
Yorumlar

Henüz bir yorum bulunmuyor.