Bubble Sort Algoritmasının İyileştirilmiş Hali

bubble sort algoritması
Kabarcık Sıralama
Size daha önce de demiştim, bizim burada öğreneceğimiz algoritmalar, algoritmaların en yalın halidir. Bu algoritmalar iyileştirilerek çalışma zamanları azaltılabilir. Aman yanlış anlama olmasın n^2'lik çalışma zamanına sahip uygulamayı nlogn yapamayız :) Ama ufak tefek iyileştirmeler ortaya koymak mümkün.

Bubble sort algoritmasının yalın halinde dizi sıralı haldeyken bile döngüye giriyordu. Halbuki dizi sıralıysa döngüye girmesine hiç gerek yok. Buradan tasarruf etmemiz mümkün. Aşağıdaki koda dikkatlice bakın. Kırmızı ile yazdığım kısımları sonradan ekledim. Yani yine benim yazdığım bubble sort uygulaması c kodu geçerli.

void bubbleSort(int dizi[], int boyut)

{

    int i,j; //döngülerimiz için yazdım
    int siralimi = 0;
    for(i=0; i<boyut; i++)

    {

        for(j=0; j<boyut-1; j++) //boyut-1 ifadesini kaçırmayın, orası önemli

        {

            if(dizi[j+1]<dizi[j])

                {

                    int temp = dizi[j];

                    dizi[j]  = dizi[j+1];

                    dizi[j+1]= temp;
                    
                    siralimi = 1;
                }

        }
        if(!siralimi)
           break;

    }

}
çok basit bir işlemle algoritmanın daha az işlem yapmasını sağladık. Tabii her zaman değil, eğer dizi zaten sıralıysa döngüye hiç girmemesi için kontrol oluşturduk. Peki ne yaptık? İlk önce siralimi diye bir değişken oluşturduk. Ona 0 değerini atadık. if koşulunun içerisine siralimi değişkenini 1 diye belirttik. Böylece eğer swap işlemi gerçekleşiyorsa döngü normal şekilde çalışıyor. Yok eğer siralimi değişkeni hep 0 olarak kalırsa en alttaki if statements'ına girer ve break komutuyla for döngüsünden çıkar.

Uyarı!!! if koşulu üstteki for döngüsünün içinde, içteki for döngüsünün dışındadır. Bu noktaya dikkat edin. Yanlışlıkla içteki for döngüsünün içerisine yazmayın.

Etiketler: , , ,