Insertion Sort เป็นอัลกอริทึมการเรียงลำดับข้อมูลชนิดหนึ่ง โดยมีหลักการคล้ายคลึงกับวิธีที่คนเราเรียงไพ่ในมือ คือการเลือกข้อมูลตัวหนึ่ง (หรือไพ่ตัวหนึ่ง) และจัดเรียงมันให้อยู่ในตำแหน่งที่ถูกต้องเมื่อเทียบกับข้อมูลที่ได้จัดเรียงไว้แล้วในชุดข้อมูลนั้น ๆ
Algorithm ของ Insertion Sort ทำงานโดยจะแบ่ง array เป็นส่วนที่เรียงแล้ว (sorted) และส่วนที่ยังไม่เรียง (unsorted) นำตัวแรกสุดในส่วน unsorted ไปเปรียบเทียบกับข้อมูลในส่วน sorted และจัดเรียงข้อมูลนั้นให้เข้าไปอยู่ในตำแหน่งที่เหมาะสม
fn insertion_sort(arr: &mut [i32]) {
for i in 1..arr.len() {
let mut j = i;
while j > 0 && arr[j - 1] > arr[j] {
arr.swap(j - 1, j);
j -= 1;
}
}
}
fn main() {
let mut numbers = [5, 3, 4, 1, 2];
println!("Original array: {:?}", numbers);
insertion_sort(&mut numbers);
println!("Sorted array: {:?}", numbers);
}
ในตัวอย่างนี้ เราได้สร้างฟังก์ชันชื่อว่า `insertion_sort` ที่รับ array ของตัวเลขเข้ามาและเรียงลำดับภายใน array นั้นด้วยวิธี insertion sort เมื่อรันโปรแกรม ผลลัพธ์ที่ได้คือ array ที่เรียงลำดับแล้ว
Insertion Sort มักใช้กับชุดข้อมูลที่มีขนาดเล็ก หรือเมื่อข้อมูลส่วนใหญ่ของชุดนั้นเรียงลำดับอยู่แล้ว เช่น ระบบจัดเรียงการ์ดของผู้เล่นโป๊กเกอร์อัตโนมัติ หรือแอปพลิเคชันที่ต้องการอัปเดตและเรียงลำดับข้อมูลเล็ก ๆ น้อย ๆ แบบเรียลไทม์
Insertion Sort มี Time Complexity ในการเรียงลำดับเป็น O(n^2) ในกรณีเฉลี่ยและ worst case scenarios แต่สำหรับ best case scenario (เมื่อข้อมูลเรียงลำดับอยู่แล้ว) มี Time Complexity เป็น O(n)
ข้อดี:
1. ง่ายต่อการเข้าใจและใช้งาน
2. มีประสิทธิภาพเมื่อใช้กับข้อมูลขนาดเล็ก
3. ค่อนข้างรวดเร็วเมื่อข้อมูลเรียงลำดับอยู่แล้ว
4. เป็น Stable Sort คือ ไม่เปลี่ยนแปลงลำดับของข้อมูลที่เท่ากัน
ข้อเสีย:
1. ไม่เหมาะกับชุดข้อมูลที่มีขนาดใหญ่เนื่องจาก Time Complexity ที่สูง
2. มีประสิทธิภาพไม่ดีเท่ากับอัลกอริทึมการเรียงลำดับแบบอื่น ๆ เช่น Quick Sort หรือ Merge Sort
การเลือกใช้อัลกอริทึมเหล่านี้ให้เหมาะสมกับสถานการณ์นั้นมีความสำคัญอย่างยิ่ง เพื่อให้ได้ประสิทธิภาพที่ดีที่สุดในการแก้ไขปัญหา ณ EPT (Expert-Programming-Tutor) เราพร้อมให้ความรู้และแนะนำเทคนิคต่างๆ ในการเขียนโปรแกรมและเลือกใช้งานอัลกอริทึมที่เหมาะสม เพื่อสนับสนุนนักเรียนของเราให้ก้าวไปสู่ความเป็นนักพัฒนาซอฟต์แวร์ที่มีความสามารถจริงๆ!
หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง
Tag ที่น่าสนใจ: insertion_sort algorithm rust sorting programming time_complexity stable_sort performance data_structure programming_language
หากมีข้อผิดพลาด/ต้องการพูดคุยเพิ่มเติมเกี่ยวกับบทความนี้ กรุณาแจ้งที่ http://m.me/Expert.Programming.Tutor
085-350-7540 (DTAC)
084-88-00-255 (AIS)
026-111-618
หรือทาง EMAIL: NTPRINTF@GMAIL.COM