এগুলি তিনটি সহজ 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) সর্টে লাফ দেওয়া অর্থপূর্ণ করে তোলে।