બબલ, ઇન્સર્શન અને સિલેક્શન સોર્ટને સમજાવો.

Question

IT Interview Practice · Accepted Answer

આ ત્રણ સરળ **O(n²)** સરખામણી સોર્ટ છે. તેઓ મોટા ઇનપુટ પર ધીમા છે પરંતુ સમજવા માટે સરળ છે અને સોર્ટિંગ મેકેનિક્સ શીખવવા માટે ઉપયોગી છે.

## દરેક કેવી રીતે કાર્ય કરે છે

- **બબલ સોર્ટ:** વારંવાર અડીને આવેલા ખોટી ક્રમમાં આવેલા જોડી સ્વેપ કરો; મોટા મૂલ્યો દરેક પાસમાં અંતમાં "બબલ" થાય છે.
- **સિલેક્શન સોર્ટ:** અનસોર્ટ કરેલા ભાગનું ન્યૂનતમ શોધો અને તેને સ્થાનમાં સ્વેપ કરો.
- **ઇન્સર્શન સોર્ટ:** દરેક નવા તત્વને તેના સાચા સ્થાને દાખલ કરીને સોર્ટ કરેલ ઉપસર્ગ વધારો.

## ઉદાહરણ (ઇન્સર્શન સોર્ટ)

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

## તુલના

| સોર્ટ | શ્રેષ્ઠ | સૌથી ખરાબ | સ્થિર | જગ્યામાં |
|------|------|-------|--------|----------|
| બબલ | O(n) | O(n²) | હા | હા |
| સિલેક્શન | O(n²) | O(n²) | ના | હા |
| ઇન્સર્શન | O(n) | O(n²) | હા | હા |

## ક્યારે ઉપયોગ કરો / સમસ્યાઓ

ઇન્સર્શન સોર્ટ **નાની અથવા લગભગ-સોર્ટ કરેલી** એરેઓ માટે ખરેખર ઝડપી છે અને હાઇબ્રિડ સોર્ટમાં વાપરવામાં આવે છે. મોટા અનસોર્ટ કરેલા ડેટા પર આ ત્રણને ટાળો — તેના બદલે O(n log n) સોર્ટનો ઉપયોગ કરો.

## શા માટે તે મહત્વપૂર્ણ છે

આ સોર્ટ અદ્યતન અલ્ગોરિધમનો સામનો કરતા પહેલા અવ્યવસ્થા, સ્વેપ અને સ્થિરતા માટે અંતર્જ્ઞાન બનાવે છે.

ઇન્સર્શન સોર્ટ ખાસ કરીને પણ નાની સબએરેઓ માટે પ્રોડક્શન સોર્ટ (જેમ કે Timsort) માં દેખાય છે.

જાણવું કે તે શા માટે O(n²) છે તે O(n log n) સોર્ટમાં કૂદકો અર્થપૂર્ણ બનાવે છે.

સોર્ટ	શ્રેષ્ઠ	સૌથી ખરાબ	સ્થિર	જગ્યામાં
બબલ	O(n)	O(n²)	હા	હા
સિલેક્શન	O(n²)	O(n²)	ના	હા
ઇન્સર્શન	O(n)	O(n²)	હા	હા

દરેક કેવી રીતે કાર્ય કરે છે

ઉદાહરણ (ઇન્સર્શન સોર્ટ)

તુલના

ક્યારે ઉપયોગ કરો / સમસ્યાઓ

શા માટે તે મહત્વપૂર્ણ છે

સંબંધિત પ્રશ્નો