Menü

Örneklerle C ++ 'da Kabarcık Sıralama

  • Ana
  • Diğer
  • Örneklerle C ++ 'da Kabarcık Sıralama

bubble sort c with examples

Sorunları Ortadan Kaldırmak Için Enstrümanımızı Deneyin

C ++ 'da Kabarcık Sıralama Tekniği.

Kabarcık Sıralama, sıralama tekniklerinin en basitidir.

Kabarcık sıralama tekniğinde, listedeki öğelerin her biri bitişiğindeki öğeyle karşılaştırılır. Bu nedenle, A listesinde n eleman varsa, o zaman A (0), A (1) ile, A (1), A (2) ve benzeri ile karşılaştırılır.

İlk elemanın ikinciden daha büyük olup olmadığını karşılaştırdıktan sonra, iki eleman değiştirilir.

=> Uzmanlardan Tam C ++ Kursu İçin Burayı Ziyaret Edin.

BUBBLE SIRALAMA

Ne öğreneceksin:

sdlc'de uygulama aşaması nedir

Kabarcık Sıralama Tekniği

Kabarcıklı sıralama tekniğini kullanarak, sıralama geçişlerde veya yinelemelerde yapılır. Böylece her yinelemenin sonunda, en ağır eleman listedeki uygun yerine yerleştirilir. Başka bir deyişle, listedeki en büyük öğe kabarcıklar.

Aşağıda genel bir balon sıralama tekniği algoritması verdik.

Genel Algoritma

Aşama 1 : İ = 0 ila N-1 için 2. Adımı tekrarlayın
Adım 2 : J = i + 1'den N'ye - tekrar ediyorum
Aşama 3 : eğer A (J)> A (i)
A (J) ve A (i) 'yi değiştirin
(İç döngü sonu)
(Döngü için Dışsa Bitir)
4. adım : Çıkış

Burada, iki yinelemeli döngü kullanarak listeyi dolaştığımız kabarcık sıralama algoritması için sözde bir kod var.

İlk döngüde 0'dan başlıyoruzinciBir sonraki döngüde, bitişik bir öğeden başlıyoruz. İç döngü gövdesinde, bitişik elemanların her birini karşılaştırır ve sıralı değilse onları değiştiririz. Dış döngünün her yinelemesinin sonunda, en ağır öğe sonunda kabarcıklar oluşturur.

Sözde kod

Procedure bubble_sort (array , N) array – list of items to be sorted N – size of array begin swapped = false repeat for I = 1 to N-1 if array(i-1) > array(i) then swap array(i-1) and array(i) swapped = true end if end for until not swapped end procedure

Yukarıda verilen, kabarcık sıralama tekniği için sözde koddur. Şimdi bu tekniği ayrıntılı bir örnekle açıklayalım.

İllüstrasyon

5 boyutlu bir dizi alıyoruz ve kabarcık sıralama algoritmasını gösteriyoruz.

Kabarcık Sıralama İllüstrasyon - Geçiş 1

Kabarcık Sıralama İllüstrasyon - Geçiş 2

Kabarcık İllüstrasyon - Geçiş 3

Dizi tamamen sıralandı.

Yukarıdaki çizim, aşağıda gösterildiği gibi tablo şeklinde özetlenebilir:

GeçmekSıralanmamış listekarşılaştırmaSıralanmış liste
{5,0,10,12,15}{10.12}{5,0,10,12,15}
1{10,5,15,0,12}{10.5}{5,10,15,0,12}
{5,10,15,0,12}{10.15}{5,10,15,0,12}
{5,10,15,0,12}{15.0}{5,10,0,15,12}
{5,10,0,15,12}{15.12}{5,10,0,12,15}
iki{5,10,0,12,15}{5,10}{5,10,0,12,15}
{5,10,0,12,15}{10.0}{5,0,10,12,15}
3{5,0,10,12,15}{5,0}{0,5,10,12,15}
{5,0,10,12,15}{5,10}{5,0,10,12,15}
{5,0,10,12,15}SIRALANMIŞ

Çizimde gösterildiği gibi, her geçişte, en büyük eleman sonuncuya kadar kabarcıklar ve böylece her geçişte listeyi sıralar. Girişte belirtildiği gibi, her bir öğe bitişiğindeki öğesiyle karşılaştırılır ve sıralı değilse birbiriyle değiştirilir.

Böylece, yukarıdaki şekilde gösterildiği gibi, ilk geçişin sonunda, dizi artan sırada sıralanacaksa, en büyük eleman listenin sonuna yerleştirilir. İkinci geçiş için, ikinci en büyük eleman listedeki ikinci son konuma yerleştirilir ve bu böyle devam eder.

N-1'e (burada N, listedeki toplam öğe sayısıdır) ulaştığımızda, tüm listeyi sıralı hale getireceğiz.

kullanılacak en iyi e-posta nedir

Kabarcık sıralama tekniği herhangi bir programlama dilinde uygulanabilir. Kabarcık sıralama algoritmasını aşağıdaki C ++ ve Java dilini kullanarak uyguladık.

C ++ Örneği

Kabarcıklı sıralamayı göstermek için bir programlama Örneği görelim.

#include using namespace std; int main () { int i, j,temp,pass=0; int a(10) = {10,2,0,14,43,25,18,1,5,45}; cout <<'Input list ... '; for(i = 0; i<10; i++) { cout <

Çıktı:

Giriş listesi…

10 2 0 14 43 25 18 1 5 45

Sıralanmış Öğe Listesi…

0 1 2 5 10 14 18 25 43 45

Listeyi sıralamak için alınan geçiş sayısı: 10

Java Örneği

class Main { public static void main(String() args) { int pass = 0; int() a = {10,-2,0,14,43,25,18,1,5,45}; System.out.println('Input List...'); for(int i=0;i<10;i++) { System.out.print(a(i) + ' '); } for(int i=0;i<10;i++) { for (int j=0;j<10;j++) { if(a(i)

Çıktı:

bubble_sort Java Çıkışı

Her iki programda da 10 elemanlık bir dizi kullandık ve bunu kabarcık sıralama tekniğini kullanarak sıraladık. Her iki programda, dizinin bitişik öğeleri arasında yineleme yapmak için iki for döngüsü kullandık.

Her geçişin (dış döngü) sonunda, dizideki en büyük öğe dizinin sonuna kadar köpürtülür. Ayrıca tüm diziyi sıralamak için gereken geçiş sayısını da sayarız.

Kabarcık Sıralama Algoritmasının Karmaşıklık Analizi

Yukarıda gördüğümüz sözde kod ve resimden, kabarcık sıralamasında, ilk geçişte N-1, ikinci geçişte N-2 karşılaştırmaları vb.

Dolayısıyla, balon sıralamasındaki toplam karşılaştırma sayısı:

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

= N (N-1) / 2

= O (niki) => Kabarcık sıralama tekniğinin zaman karmaşıklığı

Bu nedenle, kabarcık sıralama tekniği için çeşitli karmaşıklıklar aşağıda verilmiştir:

En kötü durum zaman karmaşıklığıO (n 2)
En iyi vaka süresi karmaşıklığıO (n)
Ortalama zaman karmaşıklığıO (n 2)
Uzay karmaşıklığıO (1)

Kabarcıklı sıralama tekniği, takas işlemini kolaylaştırmak için geçici değişken için yalnızca tek bir ek bellek alanı gerektirir. Dolayısıyla, kabarcık sıralama algoritması için uzay karmaşıklığı O (1) 'dir.

Kabarcık sıralama tekniği için en iyi durum zaman karmaşıklığının, liste halihazırda sıralandığı zaman olacağını ve bunun O (n) olacağını unutmayın.

Sonuç

Bubble Sort'un ana avantajı, algoritmanın basitliğidir. Kabarcık sıralamasında, her geçişte, dizi artan sırada sıralanırsa, en büyük eleman listenin sonuna kadar kabarcıklar.

Benzer şekilde, azalan sırada sıralanacak liste için, en küçük eleman her geçişin sonunda uygun yerinde olacaktır.

En basit ve uygulaması kolay sıralama tekniği olan balonlu sıralama, genellikle izleyicilere sıralamayı tanıtmak için kullanılır. İkinci olarak, kabarcık sıralama, çokgen kenarların doldurulması, vb .'nin çokgeni kaplayan köşeleri sıralamak için kabarcık sıralama gerektirdiği bilgisayar grafikleri gibi uygulamalarda da kullanılır.

Yaklaşan eğitimimizde, Seçim Sıralama hakkında ayrıntılı olarak bilgi edineceğiz.

=> Sıfırdan C ++ Öğrenmek İçin Burayı Ziyaret Edin.

anime izlemek için en iyi 10 site

Önerilen Kaynaklar

^