આ ત્રણ સરળ O(n²) સરખામણી સોર્ટ છે. તેઓ મોટા ઇનપુટ પર ધીમા છે પરંતુ સમજવા માટે સરળ છે અને સોર્ટિંગ મેકેનિક્સ શીખવવા માટે ઉપયોગી છે.
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) સોર્ટમાં કૂદકો અર્થપૂર્ણ બનાવે છે.