জাভা ইনসার্শন সর্ট (Insertion Sort) একটি লিস্টের প্রতিটি এলিমেন্ট যাচাই করে। যদি কোনো এলিমেন্ট তার পূর্ববর্তী এলিমেন্টের চেয়ে ছোট হয়, তবে সেগুলো সওয়্যাপ (swap) করা হয়। অন্যথায়, তাদের অবস্থান অপরিবর্তিত থাকে এবং পরবর্তী দুটি এলিমেন্ট তুলনা করা হয়।
Insertion Sort কী?
তাসের পাতা সাজানোর মতো: বাম থেকে ডান প্রস্থান করে প্রতিটি পাতা চেক করা হয়। যদি বর্তমান পাতা পূর্বের পাতার চেয়ে ছোট হয়, তবে সেটি বামে সরিয়ে দেওয়া হয়।
কখন ব্যবহার করবেন?
- ছোট লিস্ট বা প্রায় সর্টেড লিস্টের জন্য উপযোগী।
- বাবল সর্ট এবং সিলেকশন সর্ট চেয়ে দক্ষ।
- বিগিনারদের জন্য শেখা সহজ।
- বড় লিস্টের জন্য মার্জ সর্ট (Merge Sort) ভালো।
স্টেপ-বাই-স্টেপ উদাহরণ
লিস্ট: [8, 6, 3, 9]
- ৮ সর্টেড ধরে নেওয়া হয়।
- ৬ < ৮, তাই
[6, 8, 3, 9] - ৩ < ৮, তাই
[6, 3, 8, 9]→ ৩ < ৬, তাই[3, 6, 8, 9] - ৯ সব চেয়ে বড়, তাই পরিবর্তন নেই। ফাইনাল:
[3, 6, 8, 9]
জাভা কোড বাস্তবায়ন
import java.util.Arrays;
class SortGrades {
public static void insertionSort(int[] numbersToSort) {
int itemCount = numbersToSort.length;
for (int value = 1; value < itemCount; value++) {
int key = numbersToSort[value];
int last = value - 1;
while (last >= 0 && key < numbersToSort[last]) {
numbersToSort[last + 1] = numbersToSort[last];
last--;
}
numbersToSort[last + 1] = key;
}
}
public static void main(String args[]) {
int[] numbers = { 8, 6, 3, 9 };
SortGrades sortNumbers = new SortGrades();
sortNumbers.insertionSort(numbers);
System.out.println("Sorted list: " + Arrays.toString(numbers));
}
}
টাইম কমপ্লেক্সিটি
- Best Case: O(n) - ইতিমধ্যে সর্টেড থাকলে।
- Average/Worst Case: O(n²) - রিভার্স সর্টেড বা র্যান্ডম লিস্টে।
উপসংহার
ইনসার্শন সর্ট একটি সহজ কিন্তু কার্যকর সর্টিং অ্যালগরিদম। এখন আপনি জাভাতে নিজে ইনসার্শন সর্ট লিখতে পারবেন!
