การเรียงลำดับข้อมูล (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
1. การเรียงลำดับแบบเลือก (Selection Sort)
เป็นวิธีที่ง่ายที่สุดในการเรียงลำดับข้อมูล โดยเริ่มจาก
# - หาตำแหน่งของข้อมูลที่มีค่าน้อยที่สุดแล้วสลับค่าของตำแหน่งข้อมูลนั้นกับค่าข้อมูลในตำแหน่ง A(1) จะได้ A(1) มีค่าน้อยที่สุด
# - หาตำแหน่งของข้อมูลที่มีค่าน้อยที่สุดในกลุ่ม A(2), A(3),....,A(n) แล้วทำกับสลับค่าข้อมูลในตำแหน่ง A(2) อย่างนี้เรื่อยไปจน กระทั่งไม่เกิน N-1 รอบ ก็จะได้ข้อมูลที่เรียงลำดับจากน้อยไปมาก

2. การเรียงลำดับแบบแทรก (Insertion Sort)
หลักการ คือ
  • 1. อ่านข้อมุลที่ต้องการเรียงลำดับเข้ามาทีละตัวโดยเริ่มจากตัวแรกก่อน และหาตำแหน่งของข้อมูลที่ควรจะอยู่
  • 2. หาที่ว่างสำหรับข้อ 1.
  • 3. Insert หรือแทรกข้อมูล ณ ตำแหน่งในข้อ 2.
3. การเรียงลำดับแบบบับเบิล (Bubble Sort)

วิธีการเรียงลำดับแบบบับเบิลจะทำการเปรียบเทียบข้อมูลที่อยู่ในตำแหน่งที่ติด กัน ถ้าข้อมูลไม่อยู่ใลำดับที่ถูกต้อง ก็จะทำการสลับตำแหน่งของข้อมูลที่เปรียบเทียบ โดยที่การเปรียบเทียบจะเริ่ม ที่ตำแหน่งที่ 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. การขจัดหนือการเคลื่อนย้ายข้อมูลในตำแหน่งสูงสุดหรือตำแหน่งยอดของของฮีพออกไปและสนับสนุนข้อมูลข้อมูล ตัวอื่นไปแทนตำแหน่งนั้น

0 ความคิดเห็น:

แสดงความคิดเห็น