Merhaba arkadaşlar,
Mobilhanem.com üzerinden anlattığımız/yayınladığımız Algoritma Eğitimleri serimize devam ediyoruz. Bu dersimizde ise Bubble Sort algoritmasını anlatmaya çalışacağız.
Sıralama Nedir?
Verileri bilgisayarda tutarken veya işlerken bazı durumlarda sıralı olmasını isteriz. Bu nedenle mevcut olan sıralama algoritmalarından bize uygun olanını seçip kullanmalıyız.
Çoğul eki kullandım çünkü halihazırda kullanılan bolca sıralama algoritması mevcut.
Sıralama Algoritmaları Arasındaki Farklar
En temel fark algoritmanın zaman ve hafıza karmaşıklığı arasındaki farklardır. Verimli algoritmalar O(N log N) zamanda çalışırken verimsiz algoritmalar O(N^2) zamanında çalışır.
Bubble Sort Hakkında
Bugünkü dersimizde verimsiz olarak adlandırdığımız algoritmalardan Bubble Sort algoritmasını öğreneceğiz. Peki neden verimsiz algoritma öğreniyoruz diye soranlara hemen belirtmeliyim ki bu tarz algoritmalar anlaşılması daha kolay ve mantığı basittir. Algoritmalar konusunda temel oluşturmak için bunları öğrenmemiz bizim çok yararımıza olacaktır. Bu temeli oluşturduktan sonra ileride öğreneceğiniz zor algoritmaları daha rahat kavrayacaksınız.
Fazla uzatmadan hemen algoritmamıza geçelim:
for(i=1;i<=n;i++) for(j=n;j>i;j–)
if(dizi[j] < dizi[j-1]){ tmp = dizi[j-1]; dizi[j-1] = dizi[j]; dizi[j] = tmp; }
|
for(i=1;i<=n;i++)
for(j=n;j>i;j—) if(dizi[j] < dizi[j–1]){ tmp = dizi[j–1]; dizi[j–1] = dizi[j]; dizi[j] = tmp;
} |
Temel mantığımız her diziyi baştan sona gezdiğimizde bir elemanı doğru bir şekilde sıralamış olacağız. Yani her elemanı doğru sıralamak için diziyi uzunluğu kadar gezmemiz gerekmekte.
Yukarıdaki for döngümüz diziyi N defa yani uzunluğu kadar gezmemizi sağlıyor. İçindeki for döngüsü ise sondan başa gelerek küçük elemanı başa doğru getiriyor. if kontrolü sağdaki elemanın soldaki elemandan küçük olup olmadığını kontrol ediyor. Biz istiyoruz ki sağdaki eleman her zaman soldakinden büyük olması lazım. Çünkü bu örneğimizde algoritma diziyi küçükten büyüğe doğru sıralıyor.
Not: Büyükten küçüğe doğru sıralamak isteseydik if kontrolünün içindeki küçüktür işaretini büyüktür yapmamız yeterli olacaktır.
Örnek bir sayı dizisi üzerinde denersek sırayla alacağımız sonuç şöyle olacaktır:
Başlangıç
56 3 96 -2 1
1. döngü
-2 56 3 96 1
2. döngü
-2 1 56 3 96
3. döngü
-2 1 3 56 96
4. döngü
-2 1 3 56 96
5. döngü
-2 1 3 56 96
Her döngümüzün sonunda sağ tarafta kalan küçük bir eleman sol taraftaki yerine yerleştiriliyor. Ancak dikkat ettiyseniz 3. döngüden itibaren dizimiz sıralı olmasına rağmen bilgisayar hala daha sıralamaya çalışıyor.
Çünkü bu ve diğer bütün algoritmalar en kötü seneryoda dahi çalışması için tasarlanmıştır. Verdiğimiz sayı dizisi en kötü seneryo olmadığı için 5 kere döngü yapmasına gerek kalmadan 3 döngüde sıralama işlemini gerçekleştirmiştir.
Algoritmamızı iyileştirmek için dilersek her seferinde dizimizin sıralı olup olmadığını kontrol eden bir ifade yazabiliriz. Böylelikle sıralı olduğu anda işlemi durdurup çıkmamız algoritmayı daha verimli hale getirecektir.
Örnek:
for(i=1;i<=n;i++){ int sirali=1; for(j=n;j>i;j–)
if(dizi[j] < dizi[j-1]){ tmp = dizi[j-1]; dizi[j-1] = dizi[j]; dizi[j] = tmp; sirali = 0; } if(sirali == 1) break; }
|
for(i=1;i<=n;i++){ int sirali=1; for(j=n;j>i;j—) if(dizi[j] < dizi[j–1]){ tmp = dizi[j–1]; dizi[j–1] = dizi[j]; dizi[j] = tmp;
sirali = 0; } if(sirali == 1) break; } |
Bubble Sort Analizi
Üstteki for döngümüz en kötü seneryoda N defa dönüyor. İçindeki for döngüsü ise en kötü seneryoda ilk başta N daha sonra N-1 en sonda da 1 kere döndüğü için bu algoritmanın karmaşıklığı N*(N-1) olacaktır. Bu ifadenin Büyük O notasyonunda gösterimi ise O(N^2)‘dir.
Farklı Dillerde Bubble Sort Kodları:
C/C++
void bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n-1; i++)
for (j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1]){
int tmp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = tmp;
}
}
|
void bubbleSort(int arr[], int n) { int i, j; for (i = 0; i < n–1; i++)
for (j = 0; j < n–i–1; j++) if (arr[j] > arr[j+1]){ int tmp = arr[j+1]; arr[j+1] = arr[j]; arr[j] = tmp; }
} |
Java
void bubbleSort(int arr[])
{
int n = arr.length;
for (int i = 0; i < n-1; i++)
for (int j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1])
{
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
|
void bubbleSort(int arr[]) { int n = arr.length; for (int i = 0; i < n–1; i++) for (int j = 0; j < n–i–1; j++) if (arr[j] > arr[j+1]) { int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } |
Python
def bubbleSort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]
|
def bubbleSort(arr): n = len(arr)
for i in range(n):
for j in range(0, n–i–1):
if arr[j] > arr[j+1] : arr[j], arr[j+1] = arr[j+1], arr[j] |
Okuduğunuz için teşekkürler umarım faydalı olmuşumdur. Takıldığınız noktaları ve her türlü sorularınızı aşağıdan veya Soru Cevap kısmından sormayı lütfen eksik etmeyin. Bir sonraki Algoritma Eğitiminde görüşmek üzere. Sağlıcakla kalın.
Tüm Algoritma Derslerimiz İçin tıklayınız.
72