ਇਹ ਤਿੰਨ ਸਧਾਰਨ 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]
| 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 |
Insertion sort ਸੱਚਮੁੱਚ ਛੋਟੀ ਜਾਂ ਲਗਭਗ-ਸਾਰਟ ਕੀਤੀ ਐਰੇ ਲਈ ਤੇਜ਼ ਹੈ ਅਤੇ ਹਾਈਬ੍ਰਿਡ ਸਾਰਟਸ ਦੇ ਅੰਦਰ ਵਰਤੀ ਜਾਂਦੀ ਹੈ। ਵੱਡੀਆਂ ਅਣ-ਸਾਰਟ ਕੀਤੀਆਂ ਡੇਟਾ 'ਤੇ ਇਹ ਤਿੰਨਾਂ ਨੂੰ ਰੋਕੋ — ਇਸਦੀ ਬਜਾਏ O(n log n) ਸਾਰਟਸ ਵਰਤੋ।
ਇਹ ਸਾਰਟਸ ਤੁਹਾਨੂੰ ਉੱਨਤ ਐਲਗੋਰਿਦਮ ਨੂੰ ਸਮਝਣ ਤੋਂ ਪਹਿਲਾਂ invariants, swaps, ਅਤੇ stability ਲਈ ਬੋਧ ਬਣਾਉਂਦੇ ਹਨ।
Insertion sort ਖਾਸ ਤੌਰ 'ਤੇ production sorts (ਜਿਵੇਂ Timsort) ਦੇ ਅੰਦਰ ਛੋਟੀ subarrays ਲਈ ਦਿਖਾਈ ਦਿੰਦਾ ਹੈ।
ਜਾਣਨਾ ਕਿ ਉਹ ਕਿਉਂ O(n²) ਹਨ, O(n log n) ਸਾਰਟਸ ਤੱਕ ਜਾਣ ਨੂੰ ਅਰਥਪੂਰਣ ਬਣਾਉਂਦਾ ਹੈ।