-- Algoritma

Bubble Sort

Bir dizi içerisindeki elemanları 2’şer 2’şer ele alarak karşılaştırarak sıralayan temel algoritmalardan biridir.

Yukardaki resimde görüldüğü üzere elemanlar 2’şer olarak alınmış, eğer 2. eleman 1. elemandan küçükse swap işlemi yapılmış(küçükten büyüğe sıralamak için) ve dizinin sonuna kadar devam edilmiş. Bu işlemler hiç swap olmayana kadar devam edilince dizi sıralanmış olur.

Aşağıda bubble sort algoritmasının Java dilinde kodunu verdim.

public class BubbleSort {

  public static void main(String[] args) {
    
    int number[] = {70, 60,40, 90, 10, 20, 80, 30, 50};
    bubble_sort(number);
  }
  public static void bubble_sort(int[] input) {	
    
    for(int i=0; i<input.length-1;i++) {
    
      boolean sirali = true;
      
      
        for(int j=0; j< input.length-1-i; j++) { // input.length-1-i >> her geçişte büyük eleman en sona atıldığı için o kısma bakmamıza gerek yok.
        
            if(input[j+1] < input[j] ) {
                 sirali = false; // buraya gelindiyse swap yapılacak demektir ve dizi sıralı değildir.
                 int temp = input[j];
                 input[j] = input[j+1];
                 input[j+1] = temp;
             }
         }
        
     printNumber(input);
     
     if(sirali) break; // eğer sıralıysa döngüden çık.
    }
    
  }
  
  public static void printNumber(int[] input) {
    
    for(int i : input) {
      System.out.print(i + " ");
    }
    System.out.println();
  }

Output :

60 40 70 10 20 80 30 50 90 
40 60 10 20 70 30 50 80 90 
40 10 20 60 30 50 70 80 90 
10 20 40 30 50 60 70 80 90 
10 20 30 40 50 60 70 80 90 
10 20 30 40 50 60 70 80 90

Geçişler ve ara iterasyonlarda dizinin ne durumda olduğuna aşağıdan bakabiliriz

       ------1. Geçiş------

Orjinal dizi >> 70, 60, 40, 90, 10, 20, 80, 30, 50

it0 >> 70-60-40-90-10-20-80-30-50 [60 < 70 -> swap]
it1 >> 60,70,40,90,10,20,80,30,50 [40 < 70 -> swap]
it2 >> 60,40,70,90,10,20,80,30,50 [70 <! 90 -> swap yok]  
it3 >> 60,40,70,90,10,20,80,30,50 [10 < 90 -> swap]  
it4 >> 60,40,70,10,90,20,80,30,50 [20 < 90 -> swap]  
it5 >> 60,40,70,10,20,90,80,30,50 [80 < 90 -> swap]
it6 >> 60,40,70,10,20,80,90,30,50 [30 < 90 -> swap]
it7 >> 60,40,70,10,20,80,30,90,50 [50 < 90 -> swap]

1. geçişin sonu >> 60,40,70,10,20,80,30,50,90


        ------2. Geçiş------

1. geçişten gelen dizi >> 60,40,70,10,20,80,30,50,90

it0 >> 60,40,70,10,20,80,30,50,90 [40 < 60 -> swap]
it1 >> 40,60,70,10,20,80,30,50,90 [70 <! 60 -> swap yok]
it2 >> 40,60,70,10,20,80,30,50,90 [10 < 70 -> swap]
it3 >> 40,60,10,70,20,80,30,50,90 [20 < 70 -> swap]
it4 >> 40,60,10,20,70,80,30,50,90 [80 <! 70 -> swap yok]
it5 >> 40,60,10,20,70,80,30,50,90 [30 < 80 -> swap]
it6 >> 40,60,10,20,70,30,80,50,90 [50 < 80 -> swap]
2. geçişin sonu >> 40,60,10,20,70,30,50,80,90

 
        ------3. Geçiş------

2. geçişten gelen dizi >> 40,60,10,20,70,30,50,80,90

it0 >> 40,60,10,20,70,30,50,80,90 [60 <! 40 -> swap yok]
it1 >> 40,60,10,20,70,30,50,80,90 [10 < 60 -> swap]
it2 >> 40,10,60,20,70,30,50,80,90 [20 < 60 -> swap]
it3 >> 40,10,20,60,70,30,50,80,90 [70 <! 60 -> swap yok]
it4 >> 40,10,20,60,70,30,50,80,90 [30 < 70 -> swap]
it5 >> 40,10,20,60,30,70,50,80,90 [50 < 70 -> swap]

3.geçişin sonu >> 40,10,20,60,30,50,70,80,90


        ------4. Geçiş------

3. geçişten gelen dizi >> 40,10,20,60,30,50,70,80,90

it0 >> 40,10,20,60,30,50,70,80,90 [10 < 40 -> swap]
it1 >> 10,40,20,60,30,50,70,80,90 [20 < 40 -> swap]
it2 >> 10,20,40,60,30,50,70,80,90 [60 <! 40 -> swap yok]
it3 >> 10,20,40,60,30,50,70,80,90 [30 < 60 -> swap]
it4 >> 10,20,40,30,60,50,70,80,90 [50 < 60 -> swap]

4. geçişin sonu >> 10,20,40,30,50,60,70,80,90


        ------5. Geçiş------

4. geçişten gelen dizi >> 10,20,40,30,50,60,70,80,90

it0 >> 10,20,40,30,50,60,70,80,90 [20 <! 10 -> swap yok]
it1 >> 10,20,40,30,50,60,70,80,90 [40 <! 20 -> swap yok]
it2 >> 10,20,40,30,50,60,70,80,90 [30 < 40 -> swap]
it3 >> 10,20,30,40,50,60,70,80,90 [50 <! 40 -> swap yok]

5. geçişin sonu >> 10,20,30,40,50,60,70,80,90

        ------6. Geçiş------

5. geçişten gelen dizi >> 10,20,30,40,50,60,70,80,90

it0 >> 10,20,30,40,50,60,70,80,90 [20 <! 10 -> swap yok]
it1 >> 10,20,30,40,50,60,70,80,90 [30 <! 20 -> swap yok]
it2 >> 10,20,30,40,50,60,70,80,90 [30 <! 40 -> swap yok]

** Hiç swap işlemi yapılmadığına göre array sıralanmıştır.

 

Yorum bırak

Yorum