Explicați bubble sort, insertion sort și selection sort.

Question

Accepted Answer

Acestea sunt trei sortări simple de comparație **O(n²)**. Sunt lente pe intrări mari, dar ușor de înțeles și utile pentru predarea mecanicii sortării.

## Cum funcționează fiecare

- **Bubble sort:** schimbă în mod repetat perechile adiacente dezordonate; valorile mari "plutesc" la sfârșit la fiecare trecere.
- **Selection sort:** găsește minimul din partea nesortată și îl schimbă în poziție.
- **Insertion sort:** crește un prefix sortat prin inserarea fiecărui element nou în locul său corect.

## Exemplu (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]
```

## Comparație

| Sort | Cel mai bun | Cel mai rău | Stabil | In-place |
|------|------|-------|--------|----------|
| Bubble | O(n) | O(n²) | Da | Da |
| Selection | O(n²) | O(n²) | Nu | Da |
| Insertion | O(n) | O(n²) | Da | Da |

## Când se folosesc / capcane

Insertion sort este cu adevărat rapid pentru **tablouri mici sau aproape sortate** și este folosit în sortări hibride. Evitați toți trei pe date mari nesortate — folosiți în schimb sortări O(n log n).

## De ce conteaza

Aceste sortări construiesc intuiție pentru invarianți, schimburi și stabilitate înainte de a aborda algoritmi avansați.

Insertion sort în special apare în sortări din producție (cum ar fi Timsort) pentru submatrice minuscule.

Cunoscerea motivului pentru care sunt O(n²) face salt către sortări O(n log n) semnificativ.

Sort	Cel mai bun	Cel mai rău	Stabil	In-place
Bubble	O(n)	O(n²)	Da	Da
Selection	O(n²)	O(n²)	Nu	Da
Insertion	O(n)	O(n²)	Da	Da