Insertion Sort ใน Java: คู่มือวิธีการ

Java insertion sort ตรวจสอบแต่ละรายการในลิสต์ หากรายการน้อยกว่ารายการก่อนหน้า จะสลับที่ มิฉะนั้นคงที่ และเปรียบเทียบคู่ถัดไป

คอมพิวเตอร์เก่งการจัดเรียงลิสต์ ใช้ loops ค้นหาและเปลี่ยนลำดับจนได้ลำดับที่ต้องการ มี sorting algorithms มาตรฐานหลายแบบ Insertion sort เป็นหนึ่งใน common algorithms

Insertion Sort คืออะไร?

คล้ายการจัดไพ่ในมือ เล่นไพ่เวลาจัดไพ่: เริ่มซ้าย ตรวจไพ่ใบที่ 2 หากมากกว่าใบก่อน คงที่ มิฉะนั้นย้ายขึ้นไปข้างหน้า ทำซ้ำจนครบทุกใบ

เมื่อไหร่ควรใช้ Insertion Sort?

• เหมาะสำหรับข้อมูลน้อย ที่ต้องการเรียงเล็กน้อย
• ข้อมูลเยอะ ควรใช้ merge sort (มีประสิทธิภาพมากกว่า)
• Insertion sort มีประสิทธิภาพมากกว่า bubble sort และ selection sort
• อัลกอริทึมง่าย เหมาะสำหรับผู้เริ่มต้น

Walkthrough ตัวอย่าง

ลิสต์: [8, 6, 3, 9]

1. สมมติตัวแรก (8) เรียงแล้ว
2. เปรียบเทียบ 6 กับ 8 → 6 < 8 → สลับ: [6, 8, 3, 9]
3. เปรียบเทียบ 3 กับ 8 → 3 < 8 → สลับ: [6, 3, 8, 9]
4. เปรียบเทียบ 3 กับ 6 → 3 < 6 → สลับ: [3, 6, 8, 9]
5. เปรียบเทียบ 9 กับ 8,6,3 → 9 มากกว่าทั้งหมด → คงที่
6. ผลลัพธ์: [3, 6, 8, 9]

Implementation ใน Java

1. Import Arrays Library

import java.util.Arrays;

2. Sort Method

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;
    }
  }
}

key = ตัวที่กำลังจัดเรียง last = จำนวนตัวที่ต้องตรวจสอบทางซ้าย

3. Main Function

public static void main(String args[]) {
  int[] numbers = {8, 6, 3, 9};
  SortGrades sortNumbers = new SortGrades();
  sortNumbers.insertionSort(numbers);
  String arrayToString = Arrays.toString(numbers);
  System.out.println("Sorted list: " + arrayToString);
}

Complexity Analysis

• Average case: O(n²) - ไม่มีข้อมูลเรียง
• Best case: O(n) - ข้อมูลเรียงแล้ว (inner loop ไม่รัน)
• Worst case: O(n²) - ข้อมูลเรียงกลับด้าน ต้องเปรียบเทียบทุกคู่

สรุป

Insertion sort จัดเรียงข้อมูลได้มีประสิทธิוף เปรียบเทียบจากตัวที่ 2 หากน้อยกว่าตัวซ้าย ย้ายไปซ้ายจนกว่าจะถึงตัวที่น้อยกว่า พร้อมใช้งานได้แล้ว!