Bubble Sort with TypeScript

Bir önceki yazımda Selection Sort’ u anlatmaya çalışmıştım.

Bu yazımda da bir başka sıralama algoritması olan Bubble Sort Algoritmasının çalışma mantığını anlatacağım ve TypeScript Dilini kullanarak yazacağım.

Bubble Sort Algoritması Nasıl Çalışır?

Elimizde küçükten büyüğe sıralamak istediğimiz n elemanlı sıralı olmayan 1 küme sayının olduğunu düşünelim.

Öncelikle algoritmamız şunu yapmak isteyecek : Kümedeki birinci ve ikinci elemanı alıp kıyaslama yapacak. Eğer birinci eleman ikinci elemandan büyükse bunların yerlerini değiştirecek ve bir sıra atlayarak ikinci ve üçüncü elemanlar için aynı işlemi tekrarlayacak.

Bu açıklama üzerine biraz düşünecek olursak en büyük değerli elemanın en sona kadar sürüklenmiş olacağını göreceğiz.

En büyük sayımızı en sona yerleştirdik ama henüz diğer elemanlar yani n-1 tane eleman hala sıralı biçimde değil. O halde biz kümemizde bir önceki kıyaslama işlemlerini tekrar ve tekrar gerçekleştirmeliyiz bunu da iç içe döngü kullanarak yapacağız; ancak bu defa n kere değil n-1 kere çünkü son elemanımız yerine yerleşti. Aşağıdaki örnek daha açıklayıcı olacaktır.

Örnek:
Ham dizi : [2,4,5,3,1];
1. Adım  : [2,4,3,5,1];
2. Adım  : [2,4,3,1,5];
3. Adım  : [2,3,4,1,5];
4. Adım  : [2,3,1,4,5];
5. Adım  : [2,1,3,4,5];
6. Adım  : [1,2,3,4,5];

Şimdiki konuştuklarımızı basitçe bir koda dökelim:

let arr : number[] = [3,2,1,5,24];
let n : number = arr.length;
for(let i : number = 0; i< n; i++){
  for(let j : number = 0; j< n-i; j++){
    // Yer Değiştirme metodumuz
  }
}

Öncelikle dizimizi tanımladık ve dizimizin boyutunu n isimli bir değişkene atadık.

Benzer şekilde nested for döngüsü yazacağımızı zaten belli etmiştik.

function control(first : number,second : number) : boolean{
  return arr[first] > arr[second];
}

İşe ilk olarak sürekli kullanacağım iki sayıyı kıyaslama metodunu yazarak başlıyorum. Bu metot tuttuğumuz iki sayıdan birincisini ikincisi ile kıyaslıyor ve birincisi büyük ise true değilse false değeri dönüyor.

function swap(first : number,second : number) : void{
  if(control(first,second)){
    let temp : number;
    temp = arr[first];
    arr[first] = arr[second];
    arr[second] = temp;
    return true;
  }
  else{
    return false;
  }
}

Şimdi de yer değiştirme metodunu yazdım. Bu metoda iki sayı gönderiyorum ve birinci sayı, ikinciden büyükse birinci sayıyı ikincinin yerine ikinci sayıyı ise birincinin yerine yazıyorum yani yerlerini değiştiriyorum.

Şimdi işin en önemli yerine geldik: döngümüzü oluşturmaya

function loop() : void{
  for(let i : number = 0; i< n-1; i++){
    for(let j : number = 0; j< n-i-1; j++){
      swap(j,j+1);
    }
  }
}

Tam Kod

let arr : number[] = [3,2,1,5,24];
console.log(arr);
loop();
console.log(arr);
function control(first : number,second : number) : boolean{
  return arr[first] > arr[second];
}
function swap(first : number,second : number) : void{
  if(control(first,second)){
    let temp : number;
    temp = arr[first];
    arr[first] = arr[second];
    arr[second] = temp;
    return true;
  }
  else{
    return false;
  }
}
function loop() : void{
  for(let i : number = 0; i < n-1; i++){
    for(let j : number = 0; j < n-i-1; j++){
      swap(j,j+1);
    }
  }
}

Bu yazımda Veri Yapıları için önemli bir konu olan Bubble Sort Algoritmasının nasıl çalıştığını ve nasıl kodlandığını TypeScript Dili kullanarak anlatmaya çalıştım. Umarım sizler için yararlı bir yazı olur.