การเรียงลำดับข้อมูล (SORTING)
การ เรียงลำดับข้อมูลเป็นเรื่องสำคัญมากเรื่องหนึ่งเนื่องจากทำให้ผู้ต้องการใช้ ข้อมุลเช่น ผู้บริหาร,ผู้ปฏิบัติงาน (พนักงาน) สามารถทำความเข้าใจกับข้อมูลหรือทำการค้นหาข้อมูลได้ง่ายและเร็วยิ่งขึ้นตาม ที่ต้องการ
ประเภทของการจัดการจัดเรียงข้อมูลในระบบคอมพิวเตอร์ แบ่งเป็น 2 ประเภทคือ
- 1. Internal Sorting คือ การเรียงลำดับข้อมูลโดยเก็บไว้ในหน่วยความจำหลัก และข้อมูลของสมาชิกจะถูกเก็บ อยู่ในโครงสร้างอะเรย์
- 2. External Sorting คือ การเรียงลำดับข้อมูลโดยเก็บไว้ในหน่วยความจำสำรอง ข้อมูลส่วนใหญ่มีจำนวนมาก จึงไม่ สามารถเก็บไว้ในหน่วยความจำหลักได้ทั้งหมด
ใน หัวข้อการเรียงลำดับ นี้จะอธิบายวิธีการเรียงลำดับข้อมูลในแต่ละวิธีโดยสรุปอย่างย่อ ๆ เพื่อใช้เป็นแนวทางในการศึกษาใน ระดับชั้นสูงขึ้นไป คงจะไม่ได้กล่าวถึงวิธีการขั้นตอนในการจัดเรียงอย่างละเอียดแต่จะพยายามชี้ ให้เห็นถึงจุดเด่นต่าง ๆ ของการจัด เรียงลำดับในแต่ละวิธี
วิธีหรือชนิดของการเรียงลำดับ มีวิธีต่าง ๆ ที่มักจะได้พบโดยทั่วไปดังนี้
- 1. SELECTION SORT
- 2. INSERTION SORT / LINEAR INSERTION SORT
- 3. BUBBLE SORT
- 4. SHELL SORT
- 5. BUCKET SORT /RADIX SORT
- 6. QUICK SORT
- 7. HEAP SORT / TREE SORT
เป็นวิธีที่ง่ายที่สุดในการเรียงลำดับข้อมูล โดยเริ่มจาก
# - หาตำแหน่งของข้อมูลที่มีค่าน้อยที่สุดแล้วสลับค่าของตำแหน่งข้อมูลนั้นกับค่าข้อมูลในตำแหน่ง A(1) จะได้ A(1) มีค่าน้อยที่สุด
# - หาตำแหน่งของข้อมูลที่มีค่าน้อยที่สุดในกลุ่ม A(2), A(3),....,A(n) แล้วทำกับสลับค่าข้อมูลในตำแหน่ง A(2) อย่างนี้เรื่อยไปจน กระทั่งไม่เกิน N-1 รอบ ก็จะได้ข้อมูลที่เรียงลำดับจากน้อยไปมาก
2. การเรียงลำดับแบบแทรก (Insertion Sort)
หลักการ คือ
- 1. อ่านข้อมุลที่ต้องการเรียงลำดับเข้ามาทีละตัวโดยเริ่มจากตัวแรกก่อน และหาตำแหน่งของข้อมูลที่ควรจะอยู่
- 2. หาที่ว่างสำหรับข้อ 1.
- 3. Insert หรือแทรกข้อมูล ณ ตำแหน่งในข้อ 2.
วิธีการเรียงลำดับแบบบับเบิลจะทำการเปรียบเทียบข้อมูลที่อยู่ในตำแหน่งที่ติด กัน ถ้าข้อมูลไม่อยู่ใลำดับที่ถูกต้อง ก็จะทำการสลับตำแหน่งของข้อมูลที่เปรียบเทียบ โดยที่การเปรียบเทียบจะเริ่ม ที่ตำแหน่งที่ 1 กับตำแหน่งที่ 2 ก่อน ต่อไปนี้เทียบกับ ตำแหน่งที่ 2 และตำแหน่งที่ 3 จนถึงตำแหน่งที่จัดเรียงแล้ว จากนั้นจะกลับไปเริ่มต้นการเปรียบเทียบอีกจนกระทั่งจัดเรียง เรียบร้อยหมดทุกตำแหน่ง
ในวิธีแบบ Bubble Sort ค่าในการเปรียบเทียบที่น้อยที่สุดหรือมากที่สุด จะลอยขึ้นข้างบน เหมือนกับฟองอากาศ
4. การรียงลำดับแบบเชลล์(shell sort)
เป็นรูปแบบของการ sort ข้อมูลโดยการนำเอาข้อดีของการค้นหาข้อมูลแบบ แทรกและแบบเลือกและหลีกเลี่ยง การเกิดปัญหาของทั้งแบบแทรกและแบบเลือก ซึ่งการเปรียบเทียบข้อมูลในการเรียงลำดับแบบแทรก โดยการเปรียบเทียบ ข้อมูลที่อยู่ไกลออกไป ซึ่งจะทำให้เราสามารถเรียงดับข้อมูลในตำแหน่งที่อยู่ไกลออกไปหลังจากนั้นก็ จะเรียงลำดับข้อมูล ที่อยู่ใกล้กันเข้ามา(กว่าในครั้งแรก) และความห่างของข้อมูลที่เปรียบเทียบก็จะน้อยลงจนเหลือ 1
วิธีนี้คิดค้นเมื่อปี ค.ศ.1959 โดย ดี.แอล.เชลล์(D.L.SHELL) เรียกว่า การเรียงลำดับแบบเชลล์(shell sort)
5. การเรียงลำดับโดยการใช้ฐานเลข(radix sort)
การเรียงลำดับแบบนี้การเรียงลำดับ จะอยู่บนพื้นฐานของการแทนตำแหน่งของตัวเลขที่ต้องการนำมาเรียงลำดับ จะเริ่มจากตัวที่มีเลขนัยสำคัญสูงที่สุด ดำเนินจนกระทั่งถึงตัวเลขที่มีเลขนัยสำคัญต่ำสุด การเรียงลำดับในวิธีนี้การเรียงลำดับ จะเรียงจากตัวเลขที่มีนัยสำคัญน้อยที่สุดก่อน เมื่อตัวเลขทั้งหมดถูกนำมาเรียงลำดับตามเลขนัยสำคัญที่สูงขึ้น ตัวเลขที่เหมือนกัน ในตำแหน่งน้น จะต่างกันในตำแหน่งของเลขนัยสำคัญที่น้อยกว่า การประมวลผลแบบนี้จะประมวลผลกับข้อมูลทั้งหมดได้ โดยที่ไม่ต้องมีการแบ่งข้อมูลแบบกลุ่มย่อย
6. การเรียงลำดับอย่างเร็ว(quick sort)
ถูก สร้างและตั้งชื่อโดย ซี.เอ.อาร์.ฮาร์เวร์ (C.A.R HOARE) การเรียงลำดับอย่างเร็ว จะแบ่งข้อมูลเป็นสองกลุ่ม โดยใน การจัดเรียงจะเลือกข้อมุลตัวใดตัวหนึ่งออกมา ซึ่งจะเป็นตัวที่แบ่งข้อมูลออกเป็นสองกลุ่ม โดยกลุ่มแรกจะต้องมีข้อมูลน้อยกว่า ตัวแบ่ง และกลุ่มที่มีข้อมูลน้อยกว่าตัวแบ่ง และอีกกลุ่มจะมีข้อมูลที่มากกว่าตัวแบ่ง ซึ่งเราเรียกตัวแบ่งว่า ตัวหลัก(pivot) ในการเลือกตัวหลักจะมีอิสระในการเลือกข้อมูลตัวใดก็ได้ที่เราต้องการ การเรียงลำดับแบบเร็วเหมาะกับข้อมูลที่มีการเรียกซ้ำ
7.การเรียงลำดับฮีพ(heapsort)
เป็นการเรียงลำดับที่อยู่บนพื้นฐานบนพื้นฐานของโครงสร้างแบบไบนารี จะดำเนินการ 2 ขั้นตอน คือ
- 1. การจัดข้อมูลในอะเรย์ให้สอดคล้องกับความต้องการของฮีพ
- 2. การขจัดหนือการเคลื่อนย้ายข้อมูลในตำแหน่งสูงสุดหรือตำแหน่งยอดของของฮีพออกไปและสนับสนุนข้อมูลข้อมูล ตัวอื่นไปแทนตำแหน่งนั้น