Kabarcık Sıralama Algoritması

Kabarcık Sıralama Algoritması Açıklaması

Kabarcık Sıralama, bilgisayar bilimlerindeki en basit sıralama algoritmalarından biridir. İki komşu öğeyi tekrar tekrar karşılaştırarak ve yanlış sıradaysalar yerlerini değiştirerek çalışır. Dizinin her tam geçişinden sonra, en büyük sıralanmamış öğe, dizinin sonundaki doğru konumuna gelir.

Kabarcık Sıralama, büyük veri kümeleri için verimli olmasa da, karşılaştırma, yer değiştirme, yineleme, optimizasyon, en iyi durum davranışı, en kötü durum davranışı ve zaman karmaşıklığı gibi önemli algoritmik fikirleri açıkladığı için yeni başlayanlar için çok faydalıdır.

Giriş

Sıralama, programlamadaki en yaygın işlemlerden biridir. Geliştiriciler sayıları, isimleri, tarihleri, fiyatları, ürünleri, veritabanı sonuçlarını, puanları, logları ve diğer birçok veri türünü sıralarlar. Sıralama, gerçek yazılım projelerinde sıkça karşılaşıldığı için, sıralama algoritmalarını öğrenmek, geliştiricilerin verilerin nasıl verimli bir şekilde organize edilip işlenebileceğini anlamalarına yardımcı olur.

Kabarcık Sıralama, genellikle yeni başlayanlara öğretilen ilk sıralama algoritmalarından biridir. Bunun nedeni en hızlı algoritma olması değil, mantığının görselleştirmesinin kolay olmasıdır. Algoritma komşu değerleri karşılaştırır, gerektiğinde yerlerini değiştirir ve dizi sıralanıncaya kadar bu işlemi tekrarlar.

Kabarcık Sıralama'yı anlamak, geliştiricilerin algoritma verimliliğinin neden önemli olduğunu kavramalarına da yardımcı olur. Bir çözüm doğru olabilir, ancak giriş boyutu büyüdüğünde yine de yavaş kalabilir. Bu nedenle Kabarcık Sıralama, zaman karmaşıklığı ve Büyük O gösterimini öğrenmek için iyi bir başlangıç noktasıdır.

Kabarcık Sıralama Nedir?

Kabarcık Sıralama, karşılaştırma tabanlı bir sıralama algoritmasıdır. Bir dizideki komşu öğeleri karşılaştırır ve doğru sırada değillerse yerlerini değiştirir.

Artan sıralama için Kabarcık Sıralama, sol öğenin sağ öğeden büyük olup olmadığını kontrol eder. Eğer büyükse, iki öğenin yeri değiştirilir. Bu işlem, tüm öğeler en küçükten en büyüğe sıralanana kadar birçok kez tekrarlanır.

Kabarcık Sıralama adı, büyük değerlerin dizinin sonuna doğru yavaşça hareket etme veya kabarcık gibi yükselme şeklinden gelir. Bir tam geçişten sonra, en büyük değer nihai konumuna ulaşır. Bir sonraki geçişten sonra, ikinci en büyük değer nihai konumuna ulaşır ve bu böyle devam eder.

Kabarcık Sıralama'nın Temel Fikri

Kabarcık Sıralama'nın temel fikri basittir:

• İki komşu öğeyi karşılaştırın.

• Yanlış sıradaysalar, yerlerini değiştirin.

• Bir konum ileri gidin ve tekrarlayın.

• Bir tam geçişten sonra, en büyük sıralanmamış değer doğru şekilde yerleştirilir.

• Tüm dizi sıralanana kadar işlemi tekrarlayın.

Bu durum Kabarcık Sıralama'yı anlamayı kolaylaştırır, ancak birçok tekrarlayan karşılaştırma yaptığı için büyük diziler için pek verimli değildir.

Basit Kelimelerle Kabarcık Sıralama

Bir sayı sırası hayal edin. Kabarcık Sıralama sol taraftan başlar ve her bir komşu sayı çiftini karşılaştırır. Eğer ilk sayı ikinci sayıdan büyükse, yerlerini değiştirirler.

Algoritma sıranın sonuna ulaştığında, en büyük sayı son konuma taşınmış olur. Ardından algoritma baştan tekrar başlar, ancak bu kez son sayıyı kontrol etmesine gerek yoktur çünkü o zaten sıralanmıştır.

Bu işlem, daha fazla yer değiştirmeye gerek kalmayana kadar veya algoritma gerekli tüm geçişleri tamamlayana kadar devam eder.

Kabarcık Sıralama Algoritması Adımları

Bir diziyi artan sırada sıralamak için Kabarcık Sıralama şu adımları izler:

1. Dizinin ilk öğesinden başlayın.

2. Mevcut öğeyi sonraki öğeyle karşılaştırın.

3. Mevcut öğe sonraki öğeden büyükse, yerlerini değiştirin.

4. Sonraki öğe çiftine geçin.

5. Dizinin sıralanmamış kısmının sonuna kadar devam edin.

6. İşlemi birden fazla geçiş için tekrarlayın.

7. Dizi sıralandığında durun.

Eğer tam bir geçiş herhangi bir yer değiştirme olmadan tamamlanırsa, algoritma erken durdurularak iyileştirilebilir. Bu, dizinin zaten sıralanmış olduğu anlamına gelir.

Manuel Çalıştırma Örneği

Kabarcık Sıralama'yı net bir şekilde anlamak için, bu diziyi artan sırada manuel olarak sıralayalım:

[5, 1, 4, 2, 8]

Amaç, diziyi en küçükten en büyüğe yeniden sıralamaktır:

[1, 2, 4, 5, 8]

1. Geçiş

Başlangıç dizisi:

[5, 1, 4, 2, 8]

İlk geçişten sonra, en büyük değer olan 8, zaten doğru son konumundadır.

2. Geçiş

2. geçişten önceki dizi:

[1, 4, 2, 5, 8]

İkinci geçişten sonra, ikinci en büyük değer olan 5 de doğru son konumundadır.

3. Geçiş

3. geçişten önceki dizi:

[1, 2, 4, 5, 8]

Bu geçişte herhangi bir yer değiştirme olmadı. Bu, dizinin zaten sıralanmış olduğu anlamına gelir. Optimize edilmiş bir Kabarcık Sıralama, gereksiz geçişlere devam etmek yerine burada durabilir.

Nihai Sıralanmış Dizi

Nihai sıralanmış dizi:

[1, 2, 4, 5, 8]

Bu manuel çalıştırma, daha büyük öğelerin dizinin sonuna doğru adım adım nasıl hareket ettiğini gösterir. Ayrıca, bir geçiş sırasında hiçbir yer değiştirme olmadığında optimize edilmiş sürümün neden erken durabileceğini de gösterir.

Kabarcık Sıralama Sözde Kodu

Sözde kod, belirli bir programlama diline odaklanmadan algoritmayı açıklamaya yardımcı olur.

repeat for each pass:
    swapped = false

    compare each adjacent pair in the unsorted part:
        if left element is greater than right element:
            swap them
            swapped = true

    if swapped is false:
        stop because the array is already sorted

Önemli kısım swapped bayrağıdır. Dizinin tüm geçişler tamamlanmadan önce zaten sıralanmış olup olmadığını algoritmanın algılamasına yardımcı olur.

PHP'de Kabarcık Sıralama Örneği

Aşağıdaki örnek, PHP'de Kabarcık Sıralama'yı uygular. Bir sayı dizisini artan sırada sıralar.

<?php

declare(strict_types=1);

function bubbleSort(array $numbers): array
{
    $count = count($numbers);

    for ($i = 0; $i < $count - 1; $i++) {
        for ($j = 0; $j < $count - $i - 1; $j++) {
            if ($numbers[$j] > $numbers[$j + 1]) {
                $temporary = $numbers[$j];
                $numbers[$j] = $numbers[$j + 1];
                $numbers[$j + 1] = $temporary;
            }
        }
    }

    return $numbers;
}

$values = [5, 1, 4, 2, 8];
$sortedValues = bubbleSort($values);

print_r($sortedValues);

Çıktı:

Array
(
    [0] => 1
    [1] => 2
    [2] => 4
    [3] => 5
    [4] => 8
)

Bu sürüm doğrudur, ancak dizi tüm geçişler tamamlanmadan önce sıralanmış olsa bile çalışmaya devam eder.

PHP'de Optimize Edilmiş Kabarcık Sıralama

Optimize edilmiş sürüm, swapped adlı bir boolean değişken kullanır. Tam bir geçiş herhangi bir yer değiştirme olmadan biterse, algoritma erken durur.

<?php

declare(strict_types=1);

function optimizedBubbleSort(array $numbers): array
{
    $count = count($numbers);

    for ($i = 0; $i < $count - 1; $i++) {
        $swapped = false;

        for ($j = 0; $j < $count - $i - 1; $j++) {
            if ($numbers[$j] > $numbers[$j + 1]) {
                [$numbers[$j], $numbers[$j + 1]] = [$numbers[$j + 1], $numbers[$j]];
                $swapped = true;
            }
        }

        if ($swapped === false) {
            break;
        }
    }

    return $numbers;
}

$values = [5, 1, 4, 2, 8];
$sortedValues = optimizedBubbleSort($values);

print_r($sortedValues);

Bu sürüm, zaten sıralanmış veya neredeyse sıralanmış diziler için daha iyidir. En iyi durumda, sadece bir geçişten sonra tamamlanabilir.

JavaScript'te Kabarcık Sıralama Örneği

Aynı fikir JavaScript'te de uygulanabilir. Sözdizimi değişir, ancak algoritma aynı kalır.

function bubbleSort(numbers) {
    const result = [...numbers];
    const count = result.length;

    for (let i = 0; i < count - 1; i++) {
        let swapped = false;

        for (let j = 0; j < count - i - 1; j++) {
            if (result[j] > result[j + 1]) {
                const temporary = result[j];
                result[j] = result[j + 1];
                result[j + 1] = temporary;
                swapped = true;
            }
        }

        if (!swapped) {
            break;
        }
    }

    return result;
}

const values = [5, 1, 4, 2, 8];
console.log(bubbleSort(values));

Çıktı:

[1, 2, 4, 5, 8]

Bu JavaScript örneği, sıralamadan önce orijinal dizinin bir kopyasını oluşturur. Bu, orijinal girdiyi değiştirmeden tutar, bu da birçok uygulamada faydalı olabilir.

İç Döngü Neden Kısalır?

Kabarcık Sıralama'da, her geçişten sonra, bir büyük öğe dizinin sonundaki nihai konumuna ulaşır. Bu nedenle, algoritmanın bu son sıralanmış kısmı tekrar karşılaştırmasına gerek kalmaz.

İç döngünün bu koşulu kullanmasının nedeni budur:

$j < $count - $i - 1

$i arttığında, karşılaştırma sayısı azalır. Bu, zaten sıralanmış olduğu bilinen öğeleri kontrol etmeyi önler.

Kabarcık Sıralama'nın Zaman Karmaşıklığı

Zaman karmaşıklığı, bir algoritmanın çalışma süresinin giriş boyutu arttıkça nasıl büyüdüğünü açıklar. Bir dizide n öğe varsa, Kabarcık Sıralama'nın birçok öğe çiftini karşılaştırması gerekebilir.

Kabarcık Sıralama'nın zaman karmaşıklığı, giriş sırasına ve optimize edilmiş sürümün kullanılıp kullanılmadığına bağlıdır.

En iyi durum, optimize edilmiş sürüm kullanıldığında yalnızca O(n)'dir. swapped bayrağı olmadan, Kabarcık Sıralama, dizi zaten sıralı olsa bile genellikle O(n²) kalır çünkü yine de gereksiz geçişler yapar.

En İyi Durum Zaman Karmaşıklığı

En iyi durum, giriş dizisi zaten sıralı olduğunda meydana gelir.

[1, 2, 3, 4, 5]

Optimize edilmiş sürümde, Kabarcık Sıralama dizi üzerinde bir geçiş yapar ve hiçbir yer değiştirmeye gerek olmadığını bulur. Hiçbir yer değiştirme gerçekleşmediği için, algoritma hemen durur.

n öğeli bir dizi için, bir geçiş yaklaşık n - 1 karşılaştırma gerektirir. Bu nedenle, en iyi durum zaman karmaşıklığı:

O(n)

Bu durum, optimize edilmiş Kabarcık Sıralama'yı çok küçük veya neredeyse sıralanmış diziler için kabul edilebilir kılar, ancak gerçek uygulamalarda varsayılan sıralama çözümü olarak kullanılmamalıdır.

Ortalama Durum Zaman Karmaşıklığı

Ortalama durum, dizi öğeleri rastgele sırada olduğunda meydana gelir.

[4, 1, 5, 2, 3]

Bu durumda, Kabarcık Sıralama genellikle birden fazla geçiş yapar. Bazı öğelerin doğru yerlerine ulaşmadan önce birkaç konum hareket etmesi gerekir.

Karşılaştırma sayısı, giriş boyutunun karesiyle yaklaşık olarak artar. Bu nedenle, ortalama durum zaman karmaşıklığı:

O(n²)

Bu, giriş boyutu iki katına çıktığında, iş miktarının iki katından çok daha fazla artabileceği anlamına gelir. Büyük veri kümeleri için bu durum verimsiz hale gelir.

En Kötü Durum Zaman Karmaşıklığı

En kötü durum, dizinin ters sırada sıralandığında meydana gelir.

[5, 4, 3, 2, 1]

Bu durumda, her komşu çift yanlış sıradadır. Algoritma, her öğeyi doğru konumuna taşımak için birçok yer değiştirme yapmak zorundadır.

Standart Kabarcık Sıralama yaklaşımındaki toplam karşılaştırma sayısı:

(n - 1) + (n - 2) + (n - 3) + ... + 1

Bu toplam şuna eşittir:

n × (n - 1) / 2

Büyük O gösterimi kullanıldığında, sabitler ve daha küçük terimler çıkarılır. Böylece en kötü durum zaman karmaşıklığı şöyle olur:

O(n²)

Kabarcık Sıralama'nın büyük veri kümeleri için uygun olmamasının ana nedeni budur.

Kabarcık Sıralama'nın Alan Karmaşıklığı

Alan karmaşıklığı, bir algoritmanın ne kadar ek belleğe ihtiyaç duyduğunu açıklar. Kabarcık Sıralama diziyi yerinde sıralayabilir, yani sıralanmış sonucu depolamak için başka bir diziye ihtiyaç duymaz.

Sadece döngü sayaçları ve yer değiştirme için geçici bir değişken gibi birkaç ek değişkene ihtiyaç duyar. Bu nedenle, Kabarcık Sıralama'nın alan karmaşıklığı:

O(1)

Bu, Kabarcık Sıralama'nın giriş boyutundan bağımsız olarak sabit miktarda ek bellek kullandığı anlamına gelir.

Kabarcık Sıralama Kararlı mı?

Kabarcık Sıralama, doğru uygulandığında kararlı bir sıralama algoritmasıdır. Kararlılık, eşit öğelerin sıralamadan sonra orijinal göreceli sıralarını koruması anlamına gelir.

Örneğin, iki öğrencinin puanı aynıysa, kararlı bir sıralama algoritması onları sıralamadan önceki aynı göreceli sırada tutar.

Kabarcık Sıralama kararlı kalır çünkü öğeleri yalnızca sol öğe sağ öğeden büyük olduğunda yer değiştirir. Eşit öğeleri yer değiştirmez.

if ($numbers[$j] > $numbers[$j + 1]) {
    // swap only when left value is greater
}

Eğer koşul > yerine >= kullanılsaydı, eşit öğeler yer değiştirebilirdi ve algoritma kararlılığını kaybedebilirdi.

Kabarcık Sıralama Yerinde Sıralama mı?

Kabarcık Sıralama, orijinal diziyi doğrudan değiştirdiğinde yerinde (in-place) bir sıralama algoritmasıdır. Bu, giriş boyutuna orantılı ikinci bir dizi gerektirmediği anlamına gelir.

Yukarıdaki PHP örneği sıralanmış bir kopya döndürür çünkü PHP'deki diziler varsayılan olarak değerle geçirilir. Ancak, algoritmik fikir aynı diziyi değiştirerek yerinde uygulanabilir.

Yerinde sıralama, bellek kısıtlı olduğunda kullanışlıdır, ancak Kabarcık Sıralama, daha verimli sıralama algoritmalarına kıyasla hala yavaştır.

Azalan Sıralama için Kabarcık Sıralama

Kabarcık Sıralama, değerleri azalan sırada da sıralayabilir. Tek değişiklik karşılaştırma koşulundadır.

Artan sıralama için, sol öğe sağ öğeden büyük olduğunda yer değiştirin:

if ($numbers[$j] > $numbers[$j + 1])

Azalan sıralama için, sol öğe sağ öğeden küçük olduğunda yer değiştirin:

if ($numbers[$j] < $numbers[$j + 1])

İşte azalan sıralama için basit bir PHP örneği:

<?php

declare(strict_types=1);

function bubbleSortDescending(array $numbers): array
{
    $count = count($numbers);

    for ($i = 0; $i < $count - 1; $i++) {
        $swapped = false;

        for ($j = 0; $j < $count - $i - 1; $j++) {
            if ($numbers[$j] < $numbers[$j + 1]) {
                [$numbers[$j], $numbers[$j + 1]] = [$numbers[$j + 1], $numbers[$j]];
                $swapped = true;
            }
        }

        if ($swapped === false) {
            break;
        }
    }

    return $numbers;
}

Kabarcık Sıralama Uygulanırken Yapılan Yaygın Hatalar

Yeni başlayanlar genellikle Kabarcık Sıralama'nın genel fikrini anlarlar, ancak yine de küçük uygulama hataları yaparlar. Bu hatalar, yanlış çıktıya, gereksiz karşılaştırmalara ve hatta çalışma zamanı hatalarına neden olabilir.

Yaygın hatalar şunları içerir:

• Artan veya azalan sıralama için yanlış karşılaştırma operatörü kullanmak.

• Her geçişten sonra iç döngüyü azaltmayı unutmak.

• $j zaten son dizinde olduğunda $numbers[$j + 1] gibi geçersiz bir dizine erişmek.

• Her geçişin başında swapped bayrağını sıfırlamayı unutmak.

• Gerçek uygulamalarda büyük veri kümeleri için Kabarcık Sıralama kullanmak.

• Yazması kolay olduğu için Kabarcık Sıralama'nın verimli olduğunu düşünmek.

En önemli nokta döngü sınırlarını anlamaktır. Kabarcık Sıralama her öğeyi bir sonraki öğeyle karşılaştırır, bu nedenle iç döngü son kontrol edilmemiş dizinden önce durmalıdır.

Kabarcık Sıralama Ne Zaman Kullanılmalı?

Kabarcık Sıralama, esas olarak öğrenme ve öğretme amaçlı faydalıdır. Yeni başlayanların sıralamanın dahili olarak nasıl çalıştığını ve algoritmaların nasıl analiz edilebileceğini anlamalarına yardımcı olur.

Kabarcık Sıralama şu durumlarda kabul edilebilir olabilir:

• Veri kümesi çok küçükse.

• Dizi zaten sıralı veya neredeyse sıralıysa.

• Amaç performansa dayalı değil, eğitimsel ise.

• Yer değiştirme ve iç içe döngüleri göstermek istiyorsanız.

• En iyi, ortalama ve en kötü durum karmaşıklığını açıklamak istiyorsanız.

Profesyonel projelerde geliştiriciler genellikle Kabarcık Sıralama yerine yerleşik sıralama fonksiyonlarını veya daha verimli algoritmaları kullanır.

Kabarcık Sıralama Ne Zaman Kullanılmamalıdır?

Performans önemli olduğunda Kabarcık Sıralama kullanılmamalıdır. Giriş boyutu arttıkça yavaşlar çünkü ortalama ve en kötü durum zaman karmaşıklığı O(n²)'dir.

Kabarcık Sıralama'dan şu durumlarda kaçının:

• Veri kümesi çok sayıda öğe içeriyorsa.

• Uygulama hızlı sıralamaya ihtiyaç duyuyorsa.

• Kod üretimde sıkça çalışıyorsa.

• Sıralama işlemi kullanıcı deneyimini etkiliyorsa.

• Yerleşik optimize edilmiş bir sıralama fonksiyonu mevcutsa.

Örneğin, PHP'de sort(), usort(), asort() ve ksort() gibi fonksiyonlar gerçek projeler için genellikle daha iyi seçeneklerdir.

Kabarcık Sıralama'nın Daha İyi Sıralama Algoritmalarıyla Karşılaştırılması

Kabarcık Sıralama basittir, ancak daha verimli sıralama algoritmalarıyla rekabet edemez. Birleştirme Sıralaması (Merge Sort), Hızlı Sıralama (Quick Sort) ve Yığın Sıralaması (Heap Sort) gibi algoritmalar genellikle daha büyük veri kümeleri için çok daha hızlıdır.

Bu karşılaştırma, Kabarcık Sıralama'nın öğrenmek için neden önemli olduğunu, ancak genellikle üretim düzeyinde sıralama için seçilmediğini gösterir.

Kabarcık Sıralama ve Büyük O Gösterimi

Kabarcık Sıralama, Büyük O gösterimini anlamak için pratik bir örnektir. Büyük O, kesin yürütme süresini saniyeler cinsinden ölçmez. Bunun yerine, giriş boyutu arttıkça işlem sayısının nasıl büyüdüğünü açıklar.

Küçük diziler için Kabarcık Sıralama hızlı görünebilir. Ancak giriş boyutu büyüdüğünde, karşılaştırma sayısı hızla artar.

Bu büyüme, O(n²) algoritmalarının neden hızla maliyetli hale gelebileceğini açıklar.

Kabarcık Sıralama'yı Anlamak için Pratik Kontrol Listesi

Daha gelişmiş sıralama algoritmalarına geçmeden önce aşağıdaki noktaları anladığınızdan emin olun:

• Kabarcık Sıralama komşu öğeleri karşılaştırır.

• Yanlış sıradaysalar öğelerin yerini değiştirir.

• Her geçişten sonra, bir öğe nihai sıralanmış konumuna ulaşır.

• İç döngü her geçişten sonra kısalır.

• Optimize edilmiş sürüm, yer değiştirme olmazsa erken durabilir.

• En iyi durum zaman karmaşıklığı sadece optimizasyonla O(n)'dir.

• Ortalama ve en kötü durum zaman karmaşıklığı O(n²)'dir.

• Alan karmaşıklığı O(1)'dir.

• Kabarcık Sıralama, eşit öğeler yer değiştirilmediğinde kararlıdır.

• Kabarcık Sıralama, büyük üretim veri kümeleri için değil, esas olarak öğrenme amaçlı kullanışlıdır.

Sonuç

Kabarcık Sıralama, komşu öğeleri tekrar tekrar karşılaştıran ve yanlış sıradaysalar yerlerini değiştiren basit bir sıralama algoritmasıdır. Mantığı takip etmesi kolaydır, bu da sıralama, iç içe döngüler, yer değiştirme ve algoritma analizi konularını anlamak isteyen yeni başlayanlar için faydalı bir algoritma olmasını sağlar.

Manuel çalıştırma, en büyük değerlerin her geçişten sonra dizinin sonuna doğru yavaş yavaş nasıl hareket ettiğini gösterir. Optimize edilmiş sürüm, yer değiştirmeye gerek kalmadığında erken durarak en iyi durum performansını artırır.

Karmaşıklık açısından bakıldığında, optimize edildiğinde Kabarcık Sıralama'nın en iyi durum zaman karmaşıklığı O(n) iken, ortalama ve en kötü durum zaman karmaşıklığı O(n²)'dir. Yalnızca küçük bir ek bellek kullanarak verileri yerinde sıralayabildiği için alan karmaşıklığı O(1)'dir.

Gerçek yazılım projelerinde, Kabarcık Sıralama performans için nadiren en iyi seçimdir. Ancak, sıralamanın temelini öğrettiği ve geliştiricileri Ekleme Sıralaması, Birleştirme Sıralaması, Hızlı Sıralama ve Yığın Sıralaması gibi daha gelişmiş algoritmaları anlamaya hazırladığı için mükemmel bir eğitim algoritması olmaya devam etmektedir.