یہ تینوں سادہ O(n²) موازنہ (comparison) sorts ہیں۔ یہ بڑی inputs پر سست ہیں لیکن سمجھنے میں آسان ہیں اور sorting کے طریقوں کو سکھانے کے لیے مفید ہیں۔
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 | بہترین | بدترین | Stable | In-place |
|---|---|---|---|---|
| Bubble | O(n) | O(n²) | ہاں | ہاں |
| Selection | O(n²) | O(n²) | نہیں | ہاں |
| Insertion | O(n) | O(n²) | ہاں | ہاں |
Insertion sort چھوٹی یا تقریباً sorted arrays کے لیے واقعی تیز ہے اور hybrid sorts کے اندر استعمال ہوتی ہے۔ بڑی unsorted data پر تینوں سے بچیں — بجائے اس کے O(n log n) sorts استعمال کریں۔
یہ sorts آپ کو invariants، swaps، اور stability کے لیے intuition دیتے ہیں اس سے پہلے کہ آپ advanced algorithms کا سامنا کریں۔
Insertion sort خاص طور پر production sorts (جیسے Timsort) کے اندر چھوٹی subarrays کے لیے نمودار ہوتی ہے۔
یہ جاننا کہ یہ کیوں O(n²) ہیں O(n log n) sorts کی طرف جانا معنی خیز بناتا ہے۔