Complexity Analysis
Coddy'nin Kabarcık Sıralaması kursunda ders 5 / 11.
Kabarcık sıralamasının (bubble sort) karmaşıklık analizi.
Zaman karmaşıklığı, gerçekleştirilen karşılaştırma ve yer değiştirme (swap) sayısına bağlıdır.
n adet geçiş yapmamız gerekir ve her geçişte (n-1) karşılaştırma yaparız. Burada n, listedeki eleman sayısıdır.
Toplam karşılaştırma=(n-1)+(n-1)+(n-1)....n kez
=n*(n-1)
=n2-n
Kabarcık sıralama algoritması için Zaman Karmaşıklığı O(n2)'dir.
Alan karmaşıklığından (Space complexity) bahsedecek olursak, algoritmada fazladan alan kullanılmaz, yerinde (in-place) sıralama gerçekleştirilir ve elemanlar orijinal listenin kendi içinde düzenlenir.
Kabarcık sıralama algoritması için Alan Karmaşıklığı O(1) (Sabit)'dir.
Görev
KolayBir dizi ve dizinin boyutunu alan count_swaps adında bir fonksiyon oluşturun. Dizi üzerinde bubble sort algoritmasını uygulayın ve yer değiştirme (swapping) işleminin kaç kez yapıldığını sayın.
Kendin dene
#include <stdio.h>
#include <stdlib.h>
int count_swaps(int* arr, int arr_size, int n) {
// Kodu buraya yazın
return 0;
}
Kabarcık Sıralaması bölümündeki tüm dersler
1Basics of Bubble Sort
IntroductionWorking of the Bubble SortSwap adjacent elementsBubble Sort Algorithm