Kabarcık Sıralama İçin C Programı: C'de Kabarcık Sıralama

Tanıtım

Bir dizinin sıralanması, bilgisayar biliminde çok büyük bir öneme sahiptir. Verileri belirli bir sırayla düzenlemeye ihtiyaç duyulduğunda, faydası fark edilir. Farklı türde sıralama algoritmaları vardır. En yaygın ve yaygın olarak kullanılan sıralama algoritması Bubble Sort'tur.

C'de Kabarcık Sıralaması

Bubble sort'da sıralama için kullanılan teknik basit ve anlaşılması kolaydır. Tek yaptığı, mevcut öğeyi bir sonraki öğeyle karşılaştırmak ve koşulun belirttiği gibi daha büyük veya daha küçükse onu değiştirmek. Algoritma çok doğru. Bir elemanın yeri bulununcaya kadar diğer elemanlarla her karşılaştırılmasına geçiş denir.

Bu algoritma, dizi benzeri kabarcıkların üst kısmını filtrelediği için sudaki kabarcıklarla karşılaştırılabilir. Sıralama için kullanılan tüm algoritmalar arasında Kabarcık sıralama, O(n^2) zaman karmaşıklığına sahip en kolay ve en yavaş olanıdır. Ancak, takas tamamlandığında döngüden çıkan bir bayrak değişkeni kullanılarak algoritma optimize edilebilir. Bubble sıralama için en iyi durum, dizi sıralandığında O(n) olabilir.

Örneğin, aşağıda verildiği gibi sıralanmamış bir beş sayı dizisini alalım.

13, 32,26, 34,9

Balon sıralama, ilk iki öğeyi dikkate almaya başlayacak ve hangisinin daha büyük olduğunu kontrol etmek için bunları karşılaştıracaktır. Bu durumda 32, 13'ten büyüktür. Yani bu kısım zaten y sıralanmıştır. Sonra 32 ile 26'yı karşılaştırırız. Böylece 32'nin 26'dan büyük olduğunu buluruz, bu yüzden yerlerinin değiştirilmesi gerekir. Yeni dizi şöyle görünecek

13, 26, 32,34,9

Sonra 32 ve 34'ü karşılaştırırız. Zaten sıralanmış olduklarını biliyoruz. Böylece son iki değişken olan 34 ve 9'a geçiyoruz. 34, 9'dan büyük olduğu için yer değiştirmeleri gerekiyor.

Değerleri yer değiştiririz ve ilk iterasyondan sonra dizinin sonuna geliriz. Şimdi dizi şöyle görünecek

13, 26. 32,9,34

İkinci yinelemeden sonra dizi şöyle görünecek:

13, 26, 9,32,34

Üçüncü yinelemeden sonra dizi

13,9,26,32,34

Dördüncü yinelemeden sonra dizi tamamen sıralanacaktır.

9, 13,26,32,34

Mutlaka Okuyun: C'de Proje Fikirleri

algoritma

Burada dizinin n elemanlı olduğunu varsayıyoruz. Ayrıca, değişim değerleri işlevinin, dizi numaralarını sıralı düzende yapmak için tüm değerleri değiştirdiğini varsayıyoruz.

BubbleSort'u (dizi) başlat

listenin tüm öğeleri için

if dizi[i]> dizi[i+1]

değişim değerleri(dizi[i], dizi[i+1] )

eğer son

için son

dönüş dizisi

Son Kabarcık Sıralaması

Okuyun: Veri Yapısında Sıralama: Kategoriler ve Türler

sözde kod

Yukarıdaki algoritmada, tüm dizi artan düzende sıralanana kadar dizi öğesinin her bir çifti arasında bir karşılaştırma olduğu açıktır. Dizi zaten artan düzende sıralandığında algoritmanın sonucu gibi birkaç karmaşıklık sorununa neden olabilir. Sorunu hafifletmek için, herhangi bir takas olup olmadığını görmemizi sağlayan bir bayrak değişkeni kullanacağız. Daha fazla takas gerekmiyorsa, iç döngüden çıkacağız.

BubbleSort algoritmasının sözde kodu aşağıdaki gibi yazılabilir.

prosedür BubbleSort (dizi: dizideki öğeler)

yineleme= dizi.sayım;

k=0 için yineleme-1 için şunu yapın:

bayrak = yanlış

l=0 için yineleme-1 için şunu yapın:

if (dizi[l]> dizi[l+1]) o zaman

değişim değerleri(dizi[l], dizi [l+1])

bayrak=doğru

eğer son

için son

Eğer (değiştirilmezse) o zaman

Kırmak

Eğer son

için son

Prosedür dönüş dizisini sonlandır

C'de örnek bir bubble sort programı deneyelim :

# dahil<stdio.h>

ana geçersiz

{

int dizisi [10], ben, j, sayı

(i=0; i<=9; i++) için

{

scanf(“%d”, &dizi[i])

}

for(i=0;i<=9;i++)

{

for(j=0;j<=9-i;j++)

{

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

{

sayı= dizi[j];

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

dizi[j+1]=sayı;

}

}

}

printf(“Sıralanan dizi /n”);

for(i=0;i<=9;i++)

{

printf(“%d ”,&dizi[i])

}

}

Örnekte gösterildiği gibi, bu kabarcık sıralama algoritması, kullanıcıdan 10 sayı kabul eder ve dizide saklar. Bir sonraki bölümde, iki adet for döngüsü vardır. Dış döngü, sıfırdan dokuza eşit olan I değeri için çalışır. Dış döngünün işlevi, diğer öğelerle karşılaştırılması gereken değerin tüm öğeleriyle ilgilenmektir.

Dış döngünün içinde başka bir döngü var. j=0'dan başlar ve sekizden küçük veya sekize eşit olana kadar devam eder. İçeride, [j] dizisinin [j+1] dizisinden büyük olup olmadığını karşılaştıran ve kontrol eden koşullu bir if ifadesi vardır. Koşul sağlanırsa, [j] dizisi ve [j+1] dizisinin değerleri birbiriyle değiştirilir.

Bunun için num adında bir değişken kullanılır. Önce [j] dizisi num'a, ardından [j+1] dizisi [j] dizisine ve son olarak da [j+1] dizisine sayı atanır. Bu işlem dizideki tüm elemanlar artan düzende sıralanıncaya kadar devam edecektir. Bundan sonra, sıralanan dizi yazdırılır.

Bubble Sort uygulamasının optimize edilmiş uygulaması

Sonuçları iyileştirmek için kabarcık sıralama için optimize edilmiş bir algoritmamız var. Bir bayrak değişkeninin kullanılması optimizasyonu yapar. Bayrak değişkeni 1'i tutar, eğer bir takas varsa, döngüden çıkar. Aşağıda, C'deki optimize edilmiş kabarcık sıralama programı bulunmaktadır.

#include<stdio.h>

ana geçersiz

{

int dizi [10], i, j, num, flag=0;

(i=0; i<=9; i++) için

{

scanf(“%d”, &dizi[i])

}

for(i=0;i<=9;i++)

{

for(j=0;j<=9-i;j++)

{

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

{

sayı= dizi[j];

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

dizi[j+1]=sayı;

bayrak=1;

}

if(! bayrak)

{

kırmak;

}

}

}

printf(“Sıralanan dizi /n”);

for(i=0;i<=9;i++)

{

printf(“%d ”,&dizi[i])

}

}

Verilen program, normal baloncuk sıralama programına benzer bir şekilde yürütülür. Tek değişiklik, bayrak değişkeninin kullanılmasıdır. Başlangıçta, bayrak 0'a ayarlanır. Ancak, bir takas gerçekleşirse, bayrak 1 olur. Bu, dizinin hala bir kontrol daha gerektirdiğini gösterir. Öte yandan, eğer flag 1 değilse, takasın gerçekleşmediğini ima ederse, dizinin zaten sıralanmış olduğunu varsayarak iç döngüden çıkarız. Bir kez yürütüldüğünde, normal Bubble sort ile aynı sonucu alacağız.

Zaman Karmaşıklığı

Kabarcık sıralama için en iyi durum zaman karmaşıklığı O(n)'dir. Dizi zaten sıralandığında olur. En kötü durum, dizi sıralanmadığında O(n*n) olur.

Okuyun: Bugün Kontrol Etmeniz Gereken Java'daki En İyi 12 Kalıp Programı

Sıradaki ne?

Java, full-stack yazılım geliştirme hakkında daha fazla bilgi edinmek istiyorsanız, upGrad & IIIT-B'nin çalışan profesyoneller için tasarlanmış ve 500+ saatlik zorlu eğitim, 9+ proje sunan Full-stack Yazılım Geliştirme PG Diplomasına göz atın , ve ödevler, IIIT-B Mezunları statüsü, pratik uygulamalı bitirme projeleri ve en iyi firmalarla iş yardımı.