Bu eğitimde, balon sıralamanın nasıl çalıştığını öğreneceksiniz. Ayrıca, C, C ++, Java ve Python'da kabarcık sıralamanın çalışma örneklerini bulacaksınız.
Kabarcık sıralama, bitişik öğeleri karşılaştıran ve amaçlanan sırada değillerse konumlarını değiştiren bir algoritmadır. Sıra artan veya azalan olabilir.
Bubble Sort Nasıl Çalışır?
- İlk dizinden başlayarak, birinci ve ikinci öğeleri karşılaştırın. İlk öğe ikinci öğeden büyükse, değiştirilirler.
Şimdi ikinci ve üçüncü unsurları karşılaştırın. Sıralı değilse onları değiştirin.
Yukarıdaki süreç son elemana kadar devam ediyor.
Bitişik öğeleri karşılaştırın - Kalan yinelemeler için aynı süreç devam ediyor. Her yinelemeden sonra, sıralanmamış öğeler arasında en büyük öğe sona yerleştirilir.
Her yinelemede karşılaştırma, sıralanmamış son öğeye kadar gerçekleşir.
Dizi, sıralanmamış tüm öğeler doğru konumlarına yerleştirildiğinde sıralanır.
Bitişik elemanları 
karşılaştırın Bitişik elemanları karşılaştırın Bitişik elemanları 
karşılaştırın
Kabarcık Sıralama Algoritması
bubbleSort (array) i rightElement için leftElement ve rightElement end bubbleSort için swap
Python, Java ve C / C ++ Örnekleri
Python Java C C ++ # Bubble sort in Python def bubbleSort(array): # run loops two times: one for walking throught the array # and the other for comparison for i in range(len(array)): for j in range(0, len(array) - i - 1): # To sort in descending order, change> to array(j + 1): # swap if greater is at the rear position (array(j), array(j + 1)) = (array(j + 1), array(j)) data = (-2, 45, 0, 11, -9) bubbleSort(data) print('Sorted Array in Asc ending Order:') print(data)
// Bubble sort in Java import java.util.Arrays; class BubbleSort ( void bubbleSort(int array()) ( int size = array.length; // run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - 1; i++) for (int j = 0; j to array(j + 1)) ( // swap if greater is at the rear position int temp = array(j); array(j) = array(j + 1); array(j + 1) = temp; ) ) // driver code public static void main(String args()) ( int() data = ( -2, 45, 0, 11, -9 ); BubbleSort bs = new BubbleSort(); bs.bubbleSort(data); System.out.println("Sorted Array in Ascending Order:"); System.out.println(Arrays.toString(data)); ) )
// Bubble sort in C #include void bubbleSort(int array(), int size) ( // run loops two times: one for walking throught the array // and the other for comparison for (int step = 0; step < size - 1; ++step) ( for (int i = 0; i " to " array(i + 1)) ( // swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; ) ) ) ) // function to print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); printf("Sorted Array in Ascending Order:"); printArray(data, size); )
// Bubble sort in C++ #include using namespace std; void bubbleSort(int array(), int size) ( // run loops two times: one for walking throught the array // and the other for comparison for (int step = 0; step < size - 1; ++step) ( for (int i = 0; i to array(i + 1)) ( // swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; ) ) ) ) // function to print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( cout << " " << array(i); ) cout << ""; ) // driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:"; printArray(data, size); )
Optimize Edilmiş Kabarcık Sıralama
Yukarıdaki kodda, dizi önceden sıralanmış olsa bile tüm olası karşılaştırmalar yapılır. Yürütme süresini artırır.
Kod, değiştirilen fazladan bir değişken eklenerek optimize edilebilir. Her yinelemeden sonra, herhangi bir takas yapılmazsa, daha fazla döngü gerçekleştirmeye gerek yoktur.
Böyle bir durumda, takas edilen değişken yanlış olarak ayarlanır. Böylece daha fazla yinelemeyi önleyebiliriz.
Optimize edilmiş kabarcık sıralama için algoritma
bubbleSort (dizi) swapped <- false for i rightElement swap leftElement ve rightElement swapped <- true end bubbleSort
Optimize Edilmiş Kabarcık Sıralama Örnekleri
Python Java C C + # Optimized bubble sort in python def bubbleSort(array): # Run loops two times: one for walking throught the array # and the other for comparison for i in range(len(array)): # swapped keeps track of swapping swapped = True for j in range(0, len(array) - i - 1): # To sort in descending order, change> to array(j + 1): # Swap if greater is at the rear position (array(j), array(j + 1)) = (array(j + 1), array(j)) swapped = False # If there is not swapping in the last swap, then the array is already sorted. if swapped: break data = (-2, 45, 0, 11, -9) bubbleSort(data) print('Sorted Array in Ascending Order:') print(data)
// Optimized bubble sort in Java import java.util.Arrays; class BubbleSort ( void bubbleSort(int array()) ( int size = array.length; // Run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - 1; i++) ( // swapped keeps track of swapping boolean swapped = true; for (int j = 0; j to array(j + 1)) ( // Swap if greater is at the rear position int temp = array(j); array(j) = array(j + 1); array(j + 1) = temp; swapped = false; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == true) break; ) ) // Driver code public static void main(String args()) ( int() data = ( -2, 45, 0, 11, -9 ); BubbleSort bs = new BubbleSort(); bs.bubbleSort(data); System.out.println("Sorted Array in Ascending Order:"); System.out.println(Arrays.toString(data)); ) )
// Optimized bubble sort in C #include void bubbleSort(int arrayay(), int size) ( for (int step = 0; step < size - 1; ++step) ( // Swapped keeps track of swapping int swapped = 0; // Run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i to arrayay(i + 1)) ( // Swap if greater is at the rear position int temp = arrayay(i); arrayay(i) = arrayay(i + 1); arrayay(i + 1) = temp; swapped = 1; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == 0) break; ) ) // Function to print an array void printarrayay(int arrayay(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", arrayay(i)); ) printf(""); ) // Driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); printf("Sorted Array in Ascending Order:"); printarrayay(data, size); )
// Optimized bubble sort in C++ #include using namespace std; void bubbleSort(int array(), int size) ( for (int step = 0; step < size - 1; ++step) (
// Run loops two times: one for walking throught the array // and the other for comparison int swapped = 0; for (int i = 0; i to array(i + 1)) ( // Swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; swapped = 1; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == 0) break; ) ) // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( cout << " " << array(i); ) cout << ""; ) // Driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:"; printArray(data, size); )
Karmaşıklık
Bubble Sort, en basit sıralama algoritmalarından biridir. Algoritmada iki döngü uygulanmaktadır.
| Döngü | Karşılaştırma Sayısı |
|---|---|
| 1 inci | (n-1) |
| 2. | (n-2) |
| 3 üncü | (n-3) |
| …. | … |
| son | 1 |
Karşılaştırma sayısı: (n - 1) + (n - 2) + (n - 3) +… + 1 = n (n - 1) / 2 neredeyse n 2'ye eşittir
Karmaşıklık: O (n 2 )
Ayrıca, karmaşıklığı basitçe döngü sayısını gözlemleyerek analiz edebiliriz. 2 döngü vardır, dolayısıyla karmaşıklıkn*n = n2
Zaman Karmaşıklıkları:
-
En Kötü Durum Karmaşıklığı: Artan düzende sıralamak istiyorsak ve dizi azalan sıradaysa, en kötü durum ortaya çıkar.
O(n2) -
En İyi Durum Karmaşıklığı:
O(n)
Dizi zaten sıralanmışsa, sıralamaya gerek yoktur. -
Ortalama Durum Karmaşıklığı: Dizinin öğeleri karışık sırada olduğunda (ne artan ne de azalan) ortaya çıkar.
O(n2)
Uzay Karmaşıklığı:
Uzay karmaşıklığı, O(1)takas için ekstra değişken bir sıcaklık kullanılmasıdır.
Optimize edilmiş algoritmada, değiştirilen değişken alan karmaşıklığına katkıda bulunur ve böylece onu yapar O(2).
Bubble Sort Uygulamaları
Kabarcık sıralama şu durumlarda kullanılır:
- kodun karmaşıklığı önemli değil.
- kısa bir kod tercih edilir.
