Bir geçiş

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.

Örnek çözümü göster

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]))

Kendini test et

Geçiş sayısı

n elemanlı dizi için ____ geçiş gerekir.

Cevabı göster

n elemanlı dizi için n - 1 geçiş gerekir.

Bir geçiş: kavramları eşleştir

Bubble sort

O(n^2)
Geçiş

n-1 kez
Swap

Yer değiştir
Sıralı

O(n) en iyi
Bubble sort'un karmaşıklığı nedir?
- O(n log n)
- O(n)
- O(1)
- O(n^2)
Cevabı göster

O(n log n) — Bubble sort O(n^2)'dir.

Sıradaki ders: Tam sıralama

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler