วิทยาการคำนวณ: การจัดเรียงข้อมูล

เมื่อเรามีการทำงานกับข้อมูลมาก ๆ ข้อมูลทั้งหมดอาจอยู่แบบปะปนกันไม่เป็นระเบียบยากต่อการค้นหา วิธีที่เราควรทำเพื่อให้ข้อมูลดูเป็นระบบระเบียบ ง่ายต่อการค้นหา และการนำไปใช้งานต่อ คือ การจัดเรียงข้อมูล

ในวิชาวิทยาการคำนวณ ชั้นมัธยมศึกษาปีที่ 4 เรื่องของ การจัดเรียงข้อมูล ได้นำเสนอการจัดเรียงข้อมูลไว้ 2 แบบ คือ การจัดเรียงแบบเลือก(Selection Sort) และการเรียงลำดับแบบแทรก(Insertion) แต่ในความเป็นจริงหากเรียนในชั้นที่สูงขึ้นอย่างปริญญาตรี ก็จะพบกับการจัดเรียงข้อมูลที่หลากหลายขึ้น เช่น Heap, Shell, Quick และBubble เป็นต้น

การจัดเรียงแบบเลือก(Selection Sort)

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

วิธีการ

  • เขียนข้อมูลทั้งหมดให้อยู่ในแถวเดียวกัน
  • นำค่าที่เหมาะสมที่สุดมาวางไว้ด้านหน้าแถว(อาจเป็นค่าที่มากที่สุด หรือน้อยที่สุดก็ได้)
  • นำข้อมูลที่มีค่าถัดมา มาต่อท้ายข้อมูลตัวแรก โดยใช้การสลับที่
  • ทำซ้ำจนครบทุกจำนวน

อ่านวิธีการแล้วอาจจะงงกัน ตอนผมเรียนแรก ๆ ก็งงเช่นกัน แต่พอเรียนจบมาได้สักพักแล้วกลับมาอ่าน ดันเข้าใจเฉยเลย ฉะนั้นถ้าอยากเข้าใจควรทบทวนจากตัวอย่างบ่อย ๆ และลองทำด้วยตัวเอง

ตัวอย่าง

ให้ทำการจัดเรียงข้อมูล 6, 8, 2, 0, 5 จากน้อยไปมาก โดยใช้การจัดเรียงแบบเลือก

การจัดเรียงแบบเลือก

อธิบายการทำงาน

  1. ทำการนำข้อมูลทั้งหมดมาเขียนต่อกันเป็นแถวเดียว
  2. นำข้อมูลที่มีค่าเหมาะสมที่สุดมาวางไว้หน้าสุด ในโจทย์กำหนดให้เรียงจากน้อยไปมาก ฉะนั้นเลขที่น้อยที่สุดคือ 0
  3. นำ 2 ที่มีค่าถัดจาก 0 มาต่อท้าย 0 โดยใช้การสลับที่กันระหว่าง 2 และ 8
  4. นำ 5 ที่มีค่าถัดจาก 2 มาต่อท้าย 2 โดยใช้การสลับที่กันระหว่าง 5 และ 8
  5. ไม่ต้องทำการจัดเรียง เพราะข้อมูลทุกอย่างเรียงครบหมดแล้ว

การเรียงลำดับแบบแทรก(Insertion)

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

วิธีการ

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

ตัวอย่าง

ให้ทำการจัดเรียงข้อมูล 4, 3, 1, 0, 2 จากน้อยไปมาก โดยใช้การเรียงลำดับแบบแทรก

การเรียงลำดับแบบแทรก
*สีเหลือง คือ ส่วนที่ยังไม่ได้จัดเรียง
**สีส้ม คือ ส่วนที่จัดเรียงแล้ว

อธิบายการทำงาน

  1. ทำการนำข้อมูลทั้งหมดมาเขียนต่อกันเป็นแถวเดียว
  2. ทำ 4 ให้เป็นส่วนที่จัดเรียงแล้ว
  3. เปรียบเทียบข้อมูลที่จัดเรียงแล้วกับข้อมูลตัวถัดไปที่ยังไม่ได้จัดเรียง คือ 4 และ 3 ปรากฏว่า 3 มีค่าน้อยกว่า 4 จึงนำ 3 มาวางในตำแหน่งที่เหมาะสมในส่วนที่จัดเรียงแล้วคือด้านหน้า 4
  4. เปรียบเทียบข้อมูลที่จัดเรียงแล้วกับ 1 ปรากฏว่า 1 มีค่าน้อยสุด จึงนำ 1 มาวางไว้หน้าสุด
  5. เปรียบเทียบข้อมูลที่จัดเรียงแล้วกับ 0 ปรากฏว่า 0 มีค่าน้อยสุด จึงนำ 0 มาวางไว้หน้าสุด
  6. เปรียบเทียบข้อมูลที่จัดเรียงแล้วกับ 2 ปรากฏว่า 2 มีค่าอยู่ระหว่าง 1 และ 3 จึงนำ 2 มาวางไว้ระหว่าง 1 และ 3

หากใครยังไม่เข้าใจก็ผมก็มีเว็บไซต์ศึกษาเพิ่ม kru-it.com

ติดตามบทความอื่น ๆ ได้ ที่นี่