การทำความรู้จักกับ Insertion Sort ใน Node.js

 

ถ้าพูดถึงการจัดเรียงข้อมูลในโปรแกรมมิ่ง ทุกคนคงรู้ดีว่ามี algorithm หลายแบบที่สามารถใช้งานได้ แต่หนึ่งใน algorithm ที่ง่าย และเข้าใจได้ไม่ยากเลย คือ Insertion Sort ในบทความนี้ เราจะมาทำความเข้าใจกับการทำงานของ Insertion Sort ว่าคืออะไร ใช้แก้ปัญหาอะไร ยกตัวอย่างโค้ดใน Node.js พร้อมวิเคราะห์การใช้งานในโลกจริงรวมถึง Complexity ของ algorithm นี้

Insertion Sort คืออะไร?

Insertion Sort เป็น algorithm สำหรับการจัดเรียงข้อมูลที่ทำงานในลักษณะเดียวกับการจัดเรียงไพ่ในมือของเราในขณะที่เล่นไพ่ โดยการแบ่งข้อมูลออกเป็นสองส่วน คือส่วนที่จัดเรียงแล้ว และส่วนที่ยังไม่จัดเรียง จากนั้นเลือกข้อมูลจากส่วนที่ยังไม่จัดเรียงเพื่อนำไปเพิ่มในตำแหน่งที่เหมาะสมในส่วนที่จัดเรียงแล้ว

การทำงานของ Insertion Sort

1. เริ่มต้นจากตำแหน่งที่สอง (index 1 เนื่องจาก index เริ่มที่ 0) และเปรียบเทียบกับค่าตำแหน่งก่อนหน้า

2. หากค่าตำแหน่งปัจจุบันมีค่าน้อยกว่า ค่าตำแหน่งก่อนหน้า ให้ย้ายค่าตำแหน่งก่อนหน้าไปยังตำแหน่งถัดไป และทำการเปรียบเทียบและเคลื่อนย้ายไปเรื่อย ๆ จนกว่าจะเจอตำแหน่งที่เหมาะสม

3. ทำตามขั้นตอนนี้ไปเรื่อย ๆ จนครบทุกตำแหน่งใน array

ตัวอย่างโค้ด Insertion Sort ใน Node.js

มาดูตัวอย่างโค้ดกันเลย:

 function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i];
    let j = i - 1;

    // Move elements of arr[0..i-1], that are greater than key,
    // to one position ahead of their current position
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}

// ตัวอย่างการใช้งาน
const arrayToSort = [12, 11, 13, 5, 6];
console.log("Sorted array:", insertionSort(arrayToSort));

Use Case ในโลกจริง

Insertion Sort มักจะใช้ในกรณีที่มีข้อมูลขนาดเล็ก และต้องการคำตอบที่รวดเร็ว เช่น ในการจัดเรียงข้อมูลที่มีการรับข้อมูลใหม่บ่อย ๆ ในขณะที่ยังคงรักษาข้อมูลที่จัดเรียงแล้วอยู่ อย่างเช่น การจัดอันดับผู้เล่นในเกมที่เก็บคะแนนตามลำดับไปเรื่อย ๆ หรืองานด้านการตรวจสอบข้อมูลที่ต้องการการอัปเดตแบบเรียลไทม์

การวิเคราะห์ Complexity ของ Insertion Sort

- Best Case: O(n) — เมื่อตัวแปรใน array เรียงกันอยู่แล้ว - Average Case: O(n^2) — เมื่อมีการเปรียบเทียบและย้ายค่ามากมาย - Worst Case: O(n^2) — เมื่อตัวแปรใน array เรียงอยู่ในลำดับกลับกัน

ซึ่งเน้นให้เห็นว่า Insertion Sort มีประสิทธิภาพสูงในกรณีที่ขนาดของข้อมูลเล็ก และข้อมูลเบื้องต้นมีการเรียงลำดับกันอยู่แล้ว

ข้อดีและข้อเสียของ Insertion Sort

ข้อดี:

- ง่ายต่อการเข้าใจและเขียน: เหมาะสำหรับผู้เริ่มต้นศึกษาการเขียนโปรแกรม - ทำงานได้เร็วในกรณีที่ข้อมูลมีขนาดเล็ก: อาจจะเร็วกว่าหลาย algorithm ที่ซับซ้อนกว่า - ไม่ต้องใช้พื้นที่เพิ่มเติม: ใช้งานได้ในที่จัดเก็บของ array เดิมที่ต้องการจะจัดเรียง

ข้อเสีย:

- มีประสิทธิภาพต่ำในกรณีที่ข้อมูลมีขนาดใหญ่: เช่นเดียวกับหลาย ๆ algorithm ที่ใช้งานการเปรียบเทียบ - การจัดเรียงในลำดับไม่เป็นการคงที่: ไม่เหมาะในการจัดเรียงข้อมูลที่มีการสั่งทำงานพร้อมกันตลอดเวลา

 

สรุป

Insertion Sort คือ algorithm การจัดเรียงที่ง่ายต่อการเข้าใจและใช้งาน แม้ว่ามันจะมีข้อจำกัดบางประการในการใช้งานกับข้อมูลขนาดใหญ่ แต่ก็มีตัวอย่างการใช้งานในชีวิตประจำวันที่เราสามารถพึงพอใจได้ ด้วยการเข้าใจและศึกษาการใช้งาน algorithm นี้ในการเขียนโปรแกรม เรียนรู้การเขียนโปรแกรมเพิ่มเติมได้ที่ EPT ที่จะช่วยให้คุณมีพื้นฐานการเขียนโปรแกรมที่มั่นคง พร้อมที่จะพัฒนาต่อไปในอนาคต!

 

 

หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง