Bubble Sort

Intuition

Watch the bars below: each pass walks left to right, swapping any two neighbors that are out of order. The largest remaining value always "bubbles" to the end of the unsorted range — do enough passes and the whole row settles into order, one simple local swap at a time.

Tushuncha (Intuition)

Quyidagi ustunlarga qarang: har bir pass chapdan o'ngga yurib, tartibsiz turgan har qanday qo'shni juftlikni almashtiradi. Qolgan eng katta qiymat doim tartiblanmagan qismning oxiriga "suzib" boradi — yetarlicha pass qilinsa, butun qator tartiblanadi, har safar bitta oddiy, mahalliy almashtirish orqali.

How It Works

Start at the beginning of the array, comparing the first two elements, arr[0] and arr[1].
If the left value is greater than the right value, swap them so the smaller one moves left.
Move one position to the right and compare the next pair. Keep going until you reach the end of the array — that full walk is called a pass.
By the end of a pass, the largest value among the elements you scanned has been pushed all the way to the last position of that range.
Shrink the range by one from the right — the last element is already correct, so the next pass doesn't need to check it again.
Repeat passes, each one shorter than the last, until a pass finishes with zero swaps — at that point the array is fully sorted, and you can stop early.

Qanday Ishlaydi

Array boshidan boshlang: birinchi ikkita elementni, arr[0] va arr[1] ni, solishtiring.
Agar chapdagi qiymat o'ngdagisidan katta bo'lsa, ularni swap qiling — shunda kichikroq qiymat chapga o'tadi.
Bir pozitsiyaga o'ngga siljing va keyingi juftlikni solishtiring. Array oxirigacha shu tarzda davom eting — bu to'liq yurish pass deb ataladi.
Pass oxiriga kelganda, tekshirilgan qism ichidagi eng katta qiymat o'sha qismning eng oxirgi o'rniga suriladi.
Qismning o'ng chetidan bitta elementni qisqartiring — oxirgi element allaqachon to'g'ri joyda, shuning uchun keyingi pass'da uni qayta tekshirish shart emas.
Pass'larni takrorlang, har biri avvalgisidan qisqaroq bo'lsin — biror pass hech qanday swap qilmasdan tugaguncha. Shu vaqtda array to'liq saralangan bo'ladi va erta to'xtash mumkin.

Complexity

Time: O(n²) in the average and worst case. For roughly every one of the n elements, a pass may need to compare across almost the full remaining range to bubble the right value into place — about n passes of up to n comparisons each multiply out to n² work. With the early-exit check in place, the best case (an already-sorted array) drops to O(n): one pass confirms nothing needs swapping, and the algorithm stops immediately.

Space: O(1). Bubble sort rearranges elements inside the same array using a single temporary swap — it never allocates a second array or any structure that grows with the input, so its memory footprint stays constant no matter how large the array is.

Murakkablik

Vaqt: O(n²) — o'rtacha va eng yomon holatda. Taxminan n ta elementning har biri uchun, to'g'ri qiymatni joyiga suzdirish uchun qolgan qismning deyarli hammasini solishtirish kerak bo'lishi mumkin — har biri n tagacha solishtirishdan iborat bo'lgan taxminan n ta pass ko'paytirilganda n² ish hosil bo'ladi. Erta to'xtash tekshiruvi bilan, eng yaxshi holat (array allaqachon saralangan) O(n) ga tushadi: bitta pass hech narsani swap qilish shart emasligini tasdiqlaydi va algoritm darhol to'xtaydi.

Xotira: O(1). Bubble sort elementlarni xuddi shu array ichida, bitta vaqtinchalik swap yordamida qayta joylashtiradi — u hech qachon ikkinchi array yoki kirish hajmiga qarab o'sadigan boshqa struktura ajratmaydi, shuning uchun xotira sarfi array qanchalik katta bo'lishidan qat'i nazar doimiy qoladi.

Common Mistakes

Not shrinking the inner loop's range after each pass. Fix: loop only up to n - 1 - i, since the last i elements are already in their final position.
Comparing values but writing a broken swap that overwrites one value before it's read. Fix: use Python's tuple assignment, arr[j], arr[j+1] = arr[j+1], arr[j], which reads both sides before writing either.
Writing the inner loop as range(n - i) instead of range(n - 1 - i), which lets j reach one index past the intended pair and risks an out-of-bounds access. Fix: always compare arr[j] to arr[j+1], so j's maximum must leave room for j+1.
Skipping the early-exit flag and assuming bubble sort is always O(n²). Fix: track whether any swap happened during a pass and break out of the loop immediately if it didn't.

Ko'p Uchraydigan Xatolar

Har pass'dan keyin ichki loop diapazonini qisqartirmaslik. Yechim: faqat n - 1 - i gacha loop qiling, chunki oxirgi i ta element allaqachon o'z joyida.
Qiymatlarni solishtirib, lekin bitta qiymatni o'qishdan oldin ustiga yozib qo'yadigan buzuq swap yozish. Yechim: Python'ning tuple assignment'idan foydalaning — arr[j], arr[j+1] = arr[j+1], arr[j] — bu yozishdan oldin ikkala tomonni ham o'qiydi.
Ichki loop'ni range(n - i) deb yozish, range(n - 1 - i) o'rniga — bu jning mo'ljallangan juftlikdan bitta index oshib ketishiga va chegaradan chiqib ketish xavfiga olib keladi. Yechim: har doim arr[j] ni arr[j+1] bilan solishtiring, shuning uchun jning maksimal qiymati j+1 uchun joy qoldirishi kerak.
Erta to'xtash flagini o'tkazib yuborish va bubble sort doim O(n²) deb o'ylash. Yechim: pass davomida biror swap bo'lganmi yoki yo'qligini kuzatib boring va bo'lmasa loop'dan darhol chiqing.

When to Use It

You're teaching or learning sorting for the first time — bubble sort's logic is transparent enough to trace by hand, which makes the underlying invariants (why the last element settles first, why the range shrinks) easy to see.
The array is tiny — a handful of elements — where the overhead of a smarter algorithm isn't worth it and simplicity wins.
The data is already nearly sorted and you've implemented the early-exit flag — bubble sort approaches O(n) when very few swaps are needed.
Never reach for it on real, large-scale data: Python's built-in sorted() / list.sort() (Timsort) or a proper O(n log n) algorithm like merge sort will always outperform it.

Qachon Ishlatish Kerak

Saralashni birinchi marta o'rgatayotgan yoki o'rganayotgan bo'lsangiz — bubble sort mantig'i qo'lda kuzatish uchun yetarlicha shaffof, bu esa asosidagi invariantlarni (nega oxirgi element birinchi joylashadi, nega diapazon qisqaradi) ko'rish oson qiladi.
Array juda kichik — bir nechta element — bunda murakkabroq algoritmning qo'shimcha yuki foyda bermaydi va soddalik g'olib chiqadi.
Ma'lumot allaqachon deyarli saralangan va erta to'xtash flagini qo'shgan bo'lsangiz — bubble sort juda kam swap kerak bo'lganda O(n) ga yaqinlashadi.
Haqiqiy, katta hajmdagi ma'lumotlar uchun hech qachon tanlamang: Python'ning o'rnatilgan sorted() / list.sort() (Timsort) funksiyasi yoki merge sort kabi to'g'ri O(n log n) algoritm doim undan ustun bo'ladi.

LeetCode Practice

912. Sort an Array ↗

Restated: given an integer array nums, sort it in ascending order and return it.

Restate the goal. sortArray(nums) must return nums sorted ascending — nothing more exotic than the sorting we've already been doing by hand.
Translate the mechanics directly. We already know the moves: walk the array, compare neighbors, swap the ones out of order, shrink the range by one each pass. Turn that directly into two nested loops.
Add the early-exit flag. It's nearly free to add and pays off on any input that's already sorted or close to it — track whether a pass made any swaps, and stop the moment one doesn't.
Check it against LeetCode's constraints. The problem allows arrays up to 5 × 10⁴ elements. O(n²) means roughly 2.5 billion comparisons in the worst case — the judge times out long before that finishes.
Be honest about the result. This solution is correct and demonstrates the algorithm perfectly, but it will not pass every test case on LeetCode — it hits Time Limit Exceeded on the largest inputs. LC 912 is really asking for an O(n log n) approach; merge sort (split the array in half, sort each half recursively, merge the two sorted halves back together) is the standard accepted solution, and Python's own sorted() uses a refined relative of it under the hood.

def sortArray(nums):
    # Bubble sort solves LeetCode 912 correctly, but its O(n^2)
    # time causes Time Limit Exceeded on the largest test cases.
    # An O(n log n) approach (e.g. merge sort) is required to pass.
    n = len(nums)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
                swapped = True
        if not swapped:
            break  # a pass with no swaps means nums is sorted
    return nums

LeetCode Amaliyoti