Kabarcık Sıralama Algoritmasına Giriş

Sıralama, verilere uygulayabileceğiniz en temel işlemlerden biridir. Hızlı Sıralama, Kabarcık Sıralaması, Birleştirme Sıralaması, Yerleştirme Sıralaması gibi çeşitli sıralama algoritmalarını kullanarak farklı programlama dillerindeki öğeleri sıralayabilirsiniz. Bubble Sort tüm bunlar arasında en basit algoritmadır.

Bu makalede, Bubble Sort'un sözde kodu olan Bubble Sort algoritmasının çalışması hakkında bilgi edineceksiniz. algoritması, zaman ve mekan karmaşıklığı ve C++, Python, C gibi çeşitli programlama dillerinde uygulanması ve JavaScript.

Kabarcık Sıralama Algoritması Nasıl Çalışır?

Bubble Sort, listede art arda adım atan, bitişik öğeleri karşılaştıran ve yanlış sıradaysa bunları değiştiren en basit sıralama algoritmasıdır. Bu kavram bir örnek yardımıyla daha verimli bir şekilde açıklanabilir. Şu öğelere sahip sıralanmamış bir dizi düşünün: {16, 12, 15, 13, 19}.

Misal:

Burada bitişik öğeler karşılaştırılır ve artan sırada değilse değiştirilirler.

Kabarcık Sıralama Algoritmasının Sözde Kodu

sözde kodda, Kabarcık Sıralama algoritması şu şekilde ifade edilebilir:

bubbleSort (Arr[], boyut)
// her dizi elemanına erişmek için döngü
i=0 ila boyut-1 için şunları yapın:
// dizi öğelerini karşılaştırmak için döngü
j=0 için size-i-1 için şunları yapın:
// bitişik elemanları karşılaştır
eğer Varış[j] > Varış[j+1] ise o zaman
// onları değiştir
takas (Dar[j], Varış[j+1])
eğer son
için son
için son
son

Yukarıdaki algoritma, dizi zaten sıralanmış olsa bile tüm karşılaştırmaları işler. İç döngü herhangi bir takasa neden olmadıysa, algoritma durdurularak daha da optimize edilebilir. Bu, algoritmanın yürütme süresini azaltacaktır.

Böylece, optimize edilmiş Bubble Sort algoritmasının sözde kodu şu şekilde ifade edilebilir:

bubbleSort (Arr[], boyut)
// her dizi elemanına erişmek için döngü
i=0 ila boyut-1 için şunları yapın:
// takas olup olmadığını kontrol et
takas = yanlış
// dizi öğelerini karşılaştırmak için döngü
j=0 için size-i-1 için şunları yapın:
// bitişik elemanları karşılaştır
eğer Varış[j] > Varış[j+1] ise o zaman
// onları değiştir
takas (Dar[j], Varış[j+1])
takas = doğru
eğer son
için son
// hiçbir öğe değiştirilmediyse, bu, dizinin şimdi sıralandığı anlamına gelir, o zaman döngüyü kırın.
eğer (değiştirilmezse) o zaman
kırmak
eğer son
için son
son

Kabarcık Sıralama Algoritmasının Zaman Karmaşıklığı ve Yardımcı Uzay

Kabarcık Sıralama Algoritmasının en kötü zaman karmaşıklığı O(n^2)'dir. Dizi azalan düzendeyken ve onu artan düzende veya tam tersi sırada sıralamak istediğinizde oluşur.

Kabarcık Sıralama Algoritmasının en iyi durum karmaşıklığı O(n)'dir. Dizi zaten sıralanmış olduğunda oluşur.

İlişkili: Big-O Notasyonu Nedir?

Kabarcık Sıralama Algoritmasının ortalama durum zaman karmaşıklığı O(n^2)'dir. Dizinin öğeleri karışık sırada olduğunda oluşur.

Kabarcık Sıralama algoritması için gereken yardımcı alan O(1)'dir.

Kabarcık Sıralama Algoritmasının C++ Uygulaması

Aşağıda Bubble Sort algoritmasının C++ uygulaması yer almaktadır:

// C++ uygulaması
// optimize edilmiş Kabarcık Sıralama algoritması
#Dahil etmek 
ad alanı std kullanarak;
// Kabarcık Sıralaması gerçekleştirme işlevi
void bubbleSort (int dizi[], int boyut) {
// Dizinin her bir elemanına erişmek için döngü
için (int i=0; ben// Takas olup olmadığını kontrol etmek için değişken
bool takas edildi = yanlış;
// dizinin iki bitişik öğesini karşılaştırmak için döngü
for (int j = 0; j < (beden-i-1); j++) {
// İki bitişik dizi öğesinin karşılaştırılması
if (dizi[j] > dizi[j + 1]) {
// İki elemanı da değiş tokuş et
// doğru sırada değil
int sıcaklık = dizi[j];
dizi[j] = dizi[j + 1];
arr[j + 1] = sıcaklık;
takas = doğru;
}
}
// Hiçbir öğe değiştirilmediyse, bu, dizinin şimdi sıralandığı anlamına gelir,
// sonra döngüyü kır.
if (takas edildi == yanlış) {
kırmak;
}
}
}
// Dizinin elemanlarını yazdırır
void printArray (int dizi[], int boyut) {
için (int i = 0; ben < boyut; ben++) {
cout << dizi[i] << " ";
}
cout << endl;
}
int ana() {
int dizi[] = {16, 12, 15, 13, 19};
// Dizinin uzunluğunu bulma
int boyut = sizeof (dizi) / sizeof (dizi[0]);
// Verilen sıralanmamış diziyi yazdırma
cout << "Sıralanmamış Dizi: " << endl;
printArray (dizi, boyut);
// bubbleSort() işlevinin çağrılması
bubbleSort (dizi, boyut);
// Sıralanan diziyi yazdırma
cout << "Artan Düzende Sıralanmış Dizi:" << endl;
printArray (dizi, boyut);
0 döndür;
}

Çıktı:

Sıralanmamış Dizi: 
16 12 15 13 19 
Artan Sırada Sıralanmış Dizi:
12 13 15 16 19

Kabarcık Sıralama Algoritmasının Python Uygulaması

Aşağıda Bubble Sort algoritmasının Python uygulaması yer almaktadır:

# Python uygulaması
# optimize edilmiş Kabarcık Sıralama algoritması
# Kabarcık Sıralaması gerçekleştirme işlevi
def bubbleSort (dizi, boyut):
# Listenin her bir öğesine erişmek için döngü
i aralığında (boyut-1):
# Değişkenin değişip değişmediğini kontrol etmek için değişken
takas = Yanlış
# listenin iki bitişik öğesini karşılaştırmak için döngü
j aralığında (size-i-1):
# İki bitişik liste öğesinin karşılaştırılması
eğer dizi[j] > dizi[j+1] ise:
sıcaklık = dizi[j]
dizi[j] = dizi[j+1]
arr[j+1] = sıcaklık
takas = Doğru
# Hiçbir öğe değiştirilmediyse, bu, listenin şimdi sıralandığı anlamına gelir,
# sonra döngüyü kır.
takas edilirse == Yanlış:
kırmak
# Listenin öğelerini yazdırır
def printArray (dizi):
arr öğesi için:
yazdır (öğe, bitiş=" ")
Yazdır("")
dizi = [16, 12, 15, 13, 19]
# Listenin uzunluğunu bulma
boyut = uzunluk (arr)
# Verilen sıralanmamış listenin yazdırılması
print("Sıralanmamış Liste:")
printArray (dizi)
# bubbleSort() işlevinin çağrılması
bubbleSort (dizi, boyut)
# Sıralanan listenin yazdırılması
print("Artan Düzende Sıralanmış Liste:")
printArray (dizi)

Çıktı:

Sıralanmamış Liste:
16 12 15 13 19 
Artan Düzende Sıralanmış Liste:
12 13 15 16 19

İlişkili: Python'da Döngüler İçin Nasıl Kullanılır

C Kabarcık Sıralama Algoritmasının Uygulanması

Aşağıda Bubble Sort algoritmasının C uygulaması yer almaktadır:

// C uygulaması
// optimize edilmiş Kabarcık Sıralama algoritması
#Dahil etmek 
#Dahil etmek 
// Kabarcık Sıralaması gerçekleştirme işlevi
void bubbleSort (int dizi[], int boyut) {
// Dizinin her bir elemanına erişmek için döngü
için (int i=0; ben// Takas olup olmadığını kontrol etmek için değişken
bool takas edildi = yanlış;
// dizinin iki bitişik öğesini karşılaştırmak için döngü
for (int j = 0; j < (beden-i-1); j++) {
// İki bitişik dizi öğesinin karşılaştırılması
if (dizi[j] > dizi[j + 1]) {
// İki elemanı da değiş tokuş et
// doğru sırada değil
int sıcaklık = dizi[j];
dizi[j] = dizi[j + 1];
arr[j + 1] = sıcaklık;
takas = doğru;
}
}
// Hiçbir öğe değiştirilmediyse, bu, dizinin şimdi sıralandığı anlamına gelir,
// sonra döngüyü kır.
if (takas edildi == yanlış) {
kırmak;
}
}
}
// Dizinin elemanlarını yazdırır
void printArray (int dizi[], int boyut) {
için (int i = 0; ben < boyut; ben++) {
printf("%d ", dizi[i]);
}
printf(" \ n ");
}
int ana() {
int dizi[] = {16, 12, 15, 13, 19};
// Dizinin uzunluğunu bulma
int boyut = sizeof (dizi) / sizeof (dizi[0]);
// Verilen sıralanmamış diziyi yazdırma
printf("Sıralanmamış Dizi: \ \n");
printArray (dizi, boyut);
// bubbleSort() işlevinin çağrılması
bubbleSort (dizi, boyut);
// Sıralanan diziyi yazdırma
printf("Array Artan Düzende Sıralandı: \ \n");
printArray (dizi, boyut);
0 döndür;
}

Çıktı:

Sıralanmamış Dizi: 
16 12 15 13 19 
Artan Sırada Sıralanmış Dizi: 
12 13 15 16 19

Kabarcık Sıralama Algoritmasının JavaScript Uygulaması

Aşağıda Bubble Sort algoritmasının JavaScript uygulaması yer almaktadır:

// JavaScript uygulaması
// optimize edilmiş Kabarcık Sıralama algoritması
// Kabarcık Sıralaması gerçekleştirme işlevi
işlev bubbleSort (dizi, boyut) {
// Dizinin her bir elemanına erişmek için döngü
için (i=0; ben// Takas olup olmadığını kontrol etmek için değişken
var takas = false;
// dizinin iki bitişik öğesini karşılaştırmak için döngü
için (j=0 olsun; j// İki bitişik dizi öğesinin karşılaştırılması
if (dizi[j] > dizi[j+1]) {
// İki elemanı da değiş tokuş et
// doğru sırada değil
sıcaklık = dizi[j];
dizi[j] = dizi[j+1];
arr[j+1] = sıcaklık;
takas = doğru;
}
// Hiçbir öğe değiştirilmediyse, bu, dizinin şimdi sıralandığı anlamına gelir,
// sonra döngüyü kır.
if (takas edildi == yanlış) {
kırmak;
}
}
}
}
// Dizinin elemanlarını yazdırır
function printArray (dizi, boyut) {
için (i=0; benbelge.write (dizi[i] + " ");
}
belge.yaz("
")
}
var dizi = [16, 12, 15, 13, 19];
// Dizinin uzunluğunu bulma
var size = dizi.uzunluk;
// Verilen sıralanmamış diziyi yazdırma
document.write("Sıralanmamış Dizi: 
");
printArray (dizi, boyut);
// bubbleSort() işlevinin çağrılması
bubbleSort (dizi, boyut);
// Sıralanan diziyi yazdırma
document.write("Artan Düzende Sıralanmış Dizi: 
");
printArray (dizi, boyut);

Çıktı:

Sıralanmamış Dizi:
16 12 15 13 19
Artan Sırada Sıralanmış Dizi:
12 15 13 16 19

Artık Kabarcık Sıralama Algoritmasının Çalışmasını Anlıyorsunuz

Bubble Sort, en basit sıralama algoritmasıdır ve esas olarak sıralamanın temellerini anlamak için kullanılır. Bubble Sort, özyinelemeli olarak da uygulanabilir, ancak bunu yapmak için ek avantajlar sağlamaz.

Python'u kullanarak Bubble Sort algoritmasını kolaylıkla uygulayabilirsiniz. Python'a aşina değilseniz ve yolculuğunuza hızlı bir başlangıç ​​yapmak istiyorsanız, bir "Merhaba Dünya" betiğiyle başlamak harika bir seçimdir.

Bir "Merhaba Dünya" Komut Dosyası Kullanarak Python'a Nasıl Başlanır?

Python, günümüzde kullanılan en popüler programlama dillerinden biridir. İlk Python betiğinizi kullanmaya başlamak için bu öğreticiyi izleyin.

Sonrakini Oku

Yazar hakkında