Bir geçiş
- Algoritmalar kursu
- Başlangıç
- Ders 22/80
- 4 dk
Tek bir geçişte komşu çiftleri nasıl tarayacağını öğrenirsin.
Tam sıralama
Bubble sort'un tam sıralaması için n-1 geçiş gerekir. Her geçiş bir elemanı doğru yerine taşır, böylece dizi yavaş yavaş sıralanır.
Her geçişten sonra sıralanmamış kısım bir eleman kısalır. Son geçişten sonra dizi tamamen sıralıdır.
Karmaşıklık
Bubble sort'un karmaşıklığı O(n^2)'dir. İç içe iki döngü vardır: dış döngü n-1 kez, iç döngü her seferinde bir azalan sayıda döner.
En iyi durum (zaten sıralı dizi) O(n)'dir çünkü bir geçişte hiç yer değiştirme olmaz. Ancak genelde O(n^2) olarak kabul edilir.
Uygulama Bubble sort
bubble_sort(arr) yaz. Diziyi tamamen sırala ve döndür. print(bubble_sort([3, 1, 4, 1, 5])) ile [1, 1, 3, 4, 5] yazdır.
Başlangıç kodu
def bubble_sort(arr):
# Diziyi sıralaÖrnek çözüm
def bubble_sort(arr):
# Diziyi sırala
n = len(arr)
for i in range(n - 1):
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
print(bubble_sort([3, 1, 4, 1, 5]))Beklenen çıktı
[1, 1, 3, 4, 5]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Geçiş sayısı
n elemanlı dizi için ____ geçiş gerekir.n elemanlı dizi için n - 1 geçiş gerekir.Açıklama: n - 1 doğru.
2 Bir geçiş: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Bubble sort |
O(n^2) |
Geçiş |
n-1 kez |
Swap |
Yer değiştir |
Sıralı |
O(n) en iyi |
3 Bubble sort'un karmaşıklığı nedir?
- O(n log n) Doğru cevap
- O(n)
- O(1)
- O(n^2)
Açıklama: Bubble sort O(n^2)'dir.