การทำความรู้จักกับ Insertion Sort

 

การจัดเรียงข้อมูลเป็นหนึ่งในปัญหาที่พบบ่อยในวิทยาการคอมพิวเตอร์ หนึ่งในอัลกอริธึมที่ใช้สำหรับการจัดเรียงคือ Insertion Sort ซึ่งถ้าพูดในภาษาหมายถึง "การจัดเรียงโดยการแทรก" อัลกอริธึมนี้เหมาะสำหรับการจัดเรียงอาร์เรย์ที่มีขนาดเล็ก หรือในกรณีที่ข้อมูลเกือบจะจัดเรียงอยู่แล้ว ทำให้เป็นวิธีที่มีประสิทธิภาพในทั่วๆ ไป

ในบทความนี้ เราจะมาดูวิธีการทำงานของ Insertion Sort พร้อมตัวอย่างโค้ดที่เขียนด้วยภาษา PHP และหากระตุ้นให้คุณเข้ามาศึกษาวิชาการเขียนโปรแกรมที่ EPT!

 

Insertion Sort คืออะไร?

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

วิธีการทำงานของ Insertion Sort

1. เริ่มต้นด้วยการพิจารณาให้ตำแหน่งแรกในอาร์เรย์เป็นส่วนที่ได้จัดเรียงแล้ว

2. นำค่าถัดไป (จากส่วนที่ยังไม่ได้จัดเรียง) มาพิจารณาและเปรียบเทียบกับค่าในส่วนที่ได้จัดเรียง

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

4. เมื่อพบตำแหน่งที่ถูกต้อง ให้นำค่ามาแทรกและทำซ้ำขั้นตอนนี้จนกว่าจะผ่านอาร์เรย์ทั้งหมด

 

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

มาดูตัวอย่างโค้ดกันดีกว่า!

 <?php

function insertionSort(array &$arr) {
    $n = count($arr);
    for ($i = 1; $i < $n; $i++) {
        $key = $arr[$i];
        $j = $i - 1;

        // เลื่อนค่าที่มีอยู่ไปทางขวาจนกว่าจะพบตำแหน่งที่เหมาะสม
        while ($j >= 0 && $arr[$j] > $key) {
            $arr[$j + 1] = $arr[$j];
            $j--;
        }
        // แทรกค่า key ในตำแหน่งที่ถูกต้อง
        $arr[$j + 1] = $key;
    }
}

// ทดสอบ Insertion Sort
$array = [12, 11, 13, 5, 6];
insertionSort($array);
echo "Sorted array: \n";
print_r($array);

?>

อธิบายโค้ด

- ฟังก์ชัน `insertionSort` รับอาร์เรย์ที่ต้องการจัดเรียง

- ใช้ลูป `for` เพื่อเข้าไปในอาร์เรย์และเลือกค่าที่จะนำมาจัดเรียงหรือแทรก

- มีลูป `while` เพื่อเปรียบเทียบค่าสำหรับการเลื่อนค่าที่มีอยู่ จนกว่าจะพบตำแหน่งที่ถูกต้องสำหรับการแทรก `key`

- เมื่อทุกอย่างเรียบร้อย แสดงผลอาร์เรย์ที่จัดเรียงแล้ว

 

Use Case ของ Insertion Sort

Insertion Sort มักใช้ในสถานการณ์ที่:

- ขนาดของข้อมูลเล็ก เช่น การจัดเรียงข้อมูลจากข้อมูลที่ได้มาจากผู้ใช้

- ข้อมูลบางครั้งอาจจะถูกจัดเรียงอยู่แล้ว (Best case) ทำให้สามารถมีประสิทธิภาพในการจัดเรียง

- ในบริบทของการเรียนการสอน การทำงานของ Insertion Sort เหมาะสมสำหรับการเข้าถึงแนวคิดการจัดเรียงข้อมูลอย่างง่าย

 

การวิเคราะห์ Complexity

- Best case: O(n) - ความยาวของอาร์เรย์มีขนาดเล็กหรือต้องการประสิทธิภาพสูง - Average case: O(n^2) - แก้ไขเมื่อมีการเปรียบเทียบค่าทั้งหมด - Worst case: O(n^2) - เมื่ออาร์เรย์มีค่าที่ต้องการจัดเรียงในลำดับย้อนกลับก่อนหน้า

 

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

ข้อดี

1. ง่ายต่อการเข้าใจและนำไปใช้: สามารถทำความเข้าใจได้ง่ายและเพิ่มลงในโปรแกรมอื่นๆ ได้ง่าย 2. มีประสิทธิภาพสำหรับข้อมูลที่มีขนาดเล็ก: แสดงประสิทธิภาพดีในกรณีของอาร์เรย์ที่มีขนาดเล็กหรือข้อมูลถูกจัดเรียงอยู่แล้ว 3. ทำงานในที่เดียว: ใช้หน่วยความจำเพิ่มเพียงเล็กน้อย

ข้อเสีย

1. ไม่เหมาะสมสำหรับข้อมูลขนาดใหญ่: ประสิทธิภาพจะลดลงเมื่อจำนวนข้อมูลเพิ่มขึ้น 2. มีเวลาในการทำงานที่สูงกว่าเมื่อเทียบกับอัลกอริธึมที่มีความซับซ้อนเพิ่มขึ้น เช่น Quick Sort หรือ Merge Sort

 

สรุป

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

 

 

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