การเรียงลำดับข้อมูล
(Sorting) คือการจัดเรียงข้อมูลให้มีการเรียง ลำดับตามความต้องการ โดยจะเป็นการเรียงลำดับข้อมูลจากน้อยไปหามาก หรือจากมากไปหาน้อยข้อมูลที่ทำการจัด เรียงอาจเป็น ตัวเลข เช่น การเรียงลำดับคะแนนของนักเรียนจากคะแนนสูงสุดไปหาคะแนนต่ำสุด หรือ ข้อมูล ที่ทำการจัดเรียงอาจเป็นตัวอักษร เช่น การเรียงรายนามผู้ใช้โทรศัพท์ เป็นต้น
ประโยชน์ในการจัดเรียงข้อมูลก็คือ เพื่อให้สามารถเข้าถึงข้อมูลได้อย่างมีประสิทธิภาพ กล่าวคือ รวดเร็ว ถ้าหากมีข้อมูลมากๆแล้วไม่ทำการเรียงลำดับข้อมูลก็จะทำ ให้เสียเวลาในการ ค้นหาข้อมูลนั้น เราจึงต้องมีการเรียงลำดับข้อมูลกันก่อนที่จะดึงข้อมูลมาใช้ ถึงแม้จะต้องเสีย เวลาในการจัดเรียงไปบ้าง แต่การค้นหาข้อมูลจากข้อมูลที่จัดเรียงไว้แล้ว กับที่ไม่ได้จัดเรียง มี ประสิทธิภาพที่ต่างกันเป็นอย่างมาก
ประเภทของการเรียงลำดับข้อมูล
การเรียงลำดับข้อมูลสามารถแบ่งได้เป็น 2 ประเภทใหญ่ ๆ คือ
1. การเรียงลำดับข้อมูลแบบภายใน (Internal Sorting)
2. การเรียงลำดับข้อมูลแบบภายนอก (External Sorting)
การเรียงลำดับข้อมูลแบบภายใน (Internal Sorting)
การเรียงลำดับข้อมูลแบบภายใน หมายถึง กรรมวิธีในการเรียงลำดับที่เกิดขึ้นภายในหน่วยความจำหลัก (MainMemory) ของเครื่องคอมพิวเตอร์ ซึ่งเหมาะสำหรับข้อมูลที่มีจำนวนเพียงพอกับขนาดของหน่วยความจำ ข้อมูลมีขนาดไม่ใหญ่ไปกว่าหน่วยความจำที่กำหนดให้กับผู้ใช้แต่ละราย ดังนั้นข้อมูลทั้งหลายจึงจะเก็บอยู่ในหน่วยความจำหลัก และแบบการคำนวณสำหรับการเรียงข้อมูลสามารถอ่านข้อมูลแต่ละชิ้นจากหน่วยความจำหลักหรือเขียนข้อมูลเข้าสู่หน่วยความจำหลักได้เลย โดยไม่จำเป็นต้องใช้หน่วยความจำสำรอง (Secondary Storage) การเรียงลำดับข้อมูลแบบนี้ จำเป็นต้องคิดถึงเวลาที่เสียไปในการเปรียบเทียบและการเลื่อนข้อมูลในหน่วยความจำหลักเท่านั้นกรรมวิธีการเรียงลำดับข้อมูลแบบภายในแบ่งออกเป็นวิธีพื้นฐานได้ 3 วิธี ได้แก่ การเรียงลำดับแบบการเลือก(Selection Sort) การเรียงลำดับแบบการแลกเปลี่ยน (Exchange Sort) และการเรียงลำดับแบบการแทรก (Insertion Sort)ซึ่งแต่ละวิธีจะมีความเหมาะสมกับสถานการณ์ของข้อมูลไม่เหมือนกัน
การเรียงลำดับข้อมูลแบบภายนอก (External Sorting)
การเรียงลำดับข้อมูลแบบภายนอก หมายถึง กรรมวิธีในการเรียงลำดับข้อมูลที่เกิดขึ้นภายนอกหน่วยความจำหลักของเครื่องคอมพิวเตอร์ ซึ่งเหมาะสมสำหรับข้อมูลที่มีจำนวนมากและไม่สามารถนำข้อมูลผ่านขั้นตอนวิธีการเรียงลำดับข้อมูลแบบภายในได้พร้อมกันทั้งหมด ถ้าข้อมูลมีจำนวนมากเกินกว่าที่จะบรรจุลงในพื้นที่หน่วยความจำหลัก(Main Memory) ได้หมดในครั้งเดียวกัน จึงจำเป็นต้องแบ่งข้อมูลออกเป็นส่วนย่อย ๆ (Page) แต่ละส่วนมีขนาดพอใหญ่ที่จะบรรจุอยู่ในหน่วยความจำหลักได้ และจะได้รับการเรียงข้อมูลโดยใช้การคำนวณสำหรีบการเรียงข้อมูลแบบภายในตามแบบที่ผู้ใช้เห็นว่าเหมาะสม หลังจากนั้นก็ต้องมีการนำข้อมูลย่อยในส่วนที่เรียงแล้วเก็บลงไปยังหน่วยความจำสำรอง(Secondary Storage) เช่น เทป (Tape) หรือดิสก์ (Disk) ไว้สำหรับเก็บผลลัพธ์ชั่วคราวเพื่อรอที่จะรวมกับข้อมูลส่วน อื่น ๆ ที่เรียงลำดับแล้ว จากนั้นจึงไปนำข้อมูลในส่วนอื่น ๆ ที่ยังไม่ได้เรียงลำดับเข้ามายังหน่วยความจำหลัก และเรียงลำดับข้อมูลในลักษณะเดิมอีกจนหมดข้อมูล การเรียงลำดับข้อมูลแบบนี้ นอกจากจะต้องคิดถึงเวลาที่เสียไปในการเปรียบเทียบและการเลื่อนข้อมูลในหน่วยความจำหลักแล้ว ยังต้องคิดถึงเวลาในการถ่ายเทข้อมูลระหว่างหน่วยความจำหลักและหน่วยความจำสำรองอีกด้วย เวลาที่สูญเสียไปในระหว่างการถ่ายเทข้อมูลระหว่างหน่วยความจำหลักและหน่วยความจำสำรองจะเป็นตัวระบุประสิทธิภาพของวิธีการเรียงลำดับแบบภายนอกนี้ด้วย
Quick Sort
การเรียงลำดับในลักษณะนี้ เป็นการปรับปรุงมาจากการเรียงลำดับแบบ Bubble เพื่อให้การเรียงลำดับเร็วขึ้น วีธีนี้เหมาะกับการเรียงข้อมูลที่มีจำนวนมาก หรือมีขนาดใหญ่ และเป็นวิธีการเรียงข้อมูลที่ให้ค่าเฉลี่ยของเวลาน้อยที่สุดเท่าที่ค้นพบวิธีหนึ่งการเรียงลำดับแบบ Quick Sortจะเป็นการเปรียบเทียบสมาชิกที่ไม่อยู่ติดกัน โดยกำหนดข้อมูลค่าหนึ่ง เพื่อแบ่งชุดข้อมูลที่ต้องการเรียงลำดับออกเป้น 2 ส่วน จากนั้นก็จะทำการแบ่งย่อยชุดข้อมูล 2 ส่วนนั้นลงไปอีก ทำแบบนี้ไปเรื่อยๆจนข้อมูลแต่ละชุดมีสมาชิกเหลือเพียงตัวเดียวและทำ
ให้
ชุดข้อมูลทั้งหมดมีการเรียงลำดับ
