Bubble, insertion, र selection sort को व्याख्या गर्नुहोस्।

Question

Accepted Answer

यी तीनवटा साधारण **O(n²)** comparison sorts हुन्। ठूलो inputमा यो सस्तो छ तर बुझ्न सजिलो र sorting को mechanics सिखाउनको लागि उपयोगी छ।

## कसरी प्रत्येक काम गर्छ

- **Bubble sort:** बारम्बार order बाहिर रहेका छेउछाउको जोडीहरू स्वैप गरिन्छ; ठूला मानहरू प्रत्येक pass मा अन्त्यमा "bubble" हुन्छन्।
- **Selection sort:** unsorted भागको minimum खोजी गरिन्छ र यसलाई जायगामा स्वैप गरिन्छ।
- **Insertion sort:** sorted prefix लाई प्रत्येक नयाँ element को सही जायगामा insert गरेर बढाइन्छ।

## उदाहरण (insertion sort)

```python
def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]                  # element to place
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]       # shift bigger elements right
            j -= 1
        arr[j + 1] = key              # drop key into the gap
    return arr

insertion_sort([5, 2, 4, 1])          # -> [1, 2, 4, 5]
```

## तुलना

| Sort | Best | Worst | Stable | In-place |
|------|------|-------|--------|----------|
| Bubble | O(n) | O(n²) | Yes | Yes |
| Selection | O(n²) | O(n²) | No | Yes |
| Insertion | O(n) | O(n²) | Yes | Yes |

## कहिले प्रयोग गर्नु / pitfalls

Insertion sort साँच्चै **साना वा लगभग-sorted** arrays को लागि छिटो छ र hybrid sorts भित्र प्रयोग गरिन्छ। ठूला unsorted data मा यी तीनवटा सबै दिन्छ — O(n log n) sorts को प्रयोग गर्नुहोस्।

## किन यो महत्वपूर्ण छ

यी sorts ले तपाइं advanced algorithms मा जानु अघि invariants, swaps, र stability को intuition निर्माण गर्छन्।

Bubble sort विशेष गरेर production sorts (Timsort जस्तो) भित्र साना subarrays को लागि देखा पर्छ।

किन यो O(n²) छ भनी जान्दा O(n log n) sorts मा कूद अर्थपूर्ण बनाउँछ।

Sort	Best	Worst	Stable	In-place
Bubble	O(n)	O(n²)	Yes	Yes
Selection	O(n²)	O(n²)	No	Yes
Insertion	O(n)	O(n²)	Yes	Yes