การจัดเรียงข้อมูล Sorting

Sorting

ความสำคัญของการจัดเรียงข้อมูล

การจัดเรียงข้อมูล เป็นการจัดการข้อมูลที่กระทำกันมากในงานประยุกต์ต่างๆ เช่น การนำข้อมูลนักศึกษามาจัดเรียงตามลำดับรหัสนักศึกษา เพื่อนำไปใช้ในการพิมพ์ใบเซ็นชื่อเข้าสอบ หรือการเรียงข้อมูลพนักงานตามรหัสพนักงานเพื่อใช้ในการพิมพ์

การจัดเรียงข้อมูลแบบแทรกใส่ (Insertion Sort)

เทคนิคมาจากลักษณะการจัดไพ่ในมือของผู้เล่น คือ เมื่อผู้เล่นได้ไพ่ใบใหม่เพิ่มขึ้นมา จะนำไพ่ใบนั้นไปแทรกในตำแหน่งที่เหมาะสม ทำให้ไพ่ในมือบางส่วนต้องขยับตำแหน่งออกไป ซึ่งการจัดเรียงลำดับข้อมูลแบบแทรกนี้จะเริ่มพิจารณาคีย์ในตำแหน่งที่ 2 เป็นต้นไป

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

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

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

การเรียงลำดับข้อมูลแบบเลือก ถือว่าเป็นวิธีการเรียงลำดับข้อมูลที่เรียบง่ายตรงไปตรงมา การทำงานในแต่ล่ะรอบของวิธีนี้จะค้นหาหรือสแกนค่าตัวเลยที่มีค่าน้อยที่สุดภายในลิสต์ โดยในรอบแรกจะเริ่มต้นสแกนค้นหาตั้งแต่ตัวแรกจนถึงตัวสุดท้าย หลังจากที่ได้พบตำแหน่งของค่าน้อยที่สุดแล้ว ก็จะทำการสลับตำแหน่งกัน จากนั้นในรอบต่อไปก็จะขยับตำแหน่งไปยังตัวถัดไป ซึ่งก็คือ ตัวที่ 2 และทำการสแกนข้อมูลที่มีค่าน้อยที่สุดตั้งแต่ตัวที่ 2 ไปจนถึงตัวสุดท้ายเมื่อพบแล้ว ก็จะสลับตำแหน่งกันเช่นเคย จนจะทำเช่นนี้ไปเรื่อยๆ จนครบทุกตัว ก็จะได้ชุดข้อมูลที่จัดเรียงสมบูรณ์

มีหลักการและขั้นตอนดังนี้

•        เริ่มจาก เลือกค่าของข้อมูลที่มีค่าน้อยที่สุด
•        นำมาแลกเปลี่ยนกับค่าในตำแหน่งแรกสุดของกลุ่ม
•        หลังจากนั้นกระทำตามหลักการทั้ง 2 กับข้อมูลที่เหลือ คือ ครั้งที่ 2 ค่า A(2) จะถูกแลกกับค่าที่เลือกแล้วว่าน้อยที่สุดในลิสต์ A(2)...A(N) และครั้งที่ 3 A(3) จะถูกแลกกับคืที่เลือกแล้วว่าน้อยที่สุดในลิสต์ A(3)...A(N)
•        และเรื่อยไปจนกระทั่งเหลือข้อมูลที่จะเปรียบเทียบแค่ 2 ค่าคือ A(N-1)
•        และ A(N) ดังนั้น จำนวนรอบในการกระทำเป็น n-1 รอบ

การจัดเรียงข้อมูลแบบฟองอากาศ (Bubble Sort)

ในการเรียงลำดับข้อมูลแบบ Bubble Sort เป็นหลักการเรียงลำดับข้อมูลด้วยการเปรียบเทียบข้อมูลเป็นคู่ที่ติดกันในแต่ล่ะรอบ

มีการทำงาน เพื่อสลับตำแหน่งกันดังนี้

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

การจัดเรียงข้อมูลโดยใช้ฮีป Heap Sort

Heap Sort หรือบางครั้งเรียกว่า Tree Sort จะอาศัยโครงสร้างข้อมูลแบบ Binary Tree แต่การแตกกิ่งก้านของโหนดในต้นไม้จะต้องอยู่ภายใต้เงื่อนไขต่อไปนี้

•        ที่ทุกระดับของ Heap จะแตกสาขาออกไปได้ 2 ทาง คือทางซ้ายและทางขวา
•        จะต้องมีโหนดในระดับบนครบ 2 ด้านก่อน จึงจะแตกโหนดต่อในระดับล่างได้
•        การแตกโหนดออกไปนั้นจะต้องเริ่มจากทางซ้ายก่อน จึงจะแตกไปทางด้านขวาตามลำดับ
•        ค่าคีย์ของโหนด จะต้องถูกจัดในลักษณะที่ว่า โหนดตัวบน (FATHER) จะต้องมีค่าของคีย์สูงกว่าโหนดตัวล่าง (SON)

ขั้นตอนในการเรียงลำดับข้อมูลด้วยวิธีดังต่อไปนี้

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

การจัดเรียงข้อมูลโดยการรวมข้อมูลเข้าด้วยกัน Merge Sort

เป็นการเรียงลำดับที่อาศัยหลักการ Divide and Conquer โดยจะแบ่งข้อมูลออกป็น 2 ส่วน ซึ่งแต่ละส่วนจะแบ่งย้อย ข้อมูลออกป็น 2 ส่วนเรื่อยไปจนกระทั่งไม่สามารถแบ่งได้อีก แล้วจึงเรียงลำดับข้อมูลแต่ละส่วนย่อย จากนั้นนำข้อมูลแต่ละส่วนย่อยมารวม (Merge)เข้าเป็นข้อมูลชุดเดียวกันพร้อมทั้งเรียงลำดับข้อมูล

การจัดเรียงข้อมูลแบบเร็ว Quick Sort

เป็นการเรียงลำดับที่อาศัยหลักการ Divide and Conquer โดยจะแบ่งข้อมูลออกป็น 2 ส่วน ซึ่งแต่ละส่วนจะแบ่งย้อย ข้อมูลออกป็น 2 ส่วนเรื่อยไปจนกระทั่งไม่สามารถแบ่งได้อีก แล้วจึงเรียงลำดับข้อมูลแต่ละส่วนย่อย จากนั้นนำข้อมูลแต่ละส่วนย่อยมารวม (Merge)เข้าเป็นข้อมูลชุดเดียวกันพร้อมทั้งเรียงลำดับข้อมูล

มีขั้นตอนในการจัดเรียงข้อมูลดังนี้

1. เลือก pivot  มา 1 ตัว (นิยมตัวกลาง หรือสุ่ม)
2. เตรียมตัวชี้ไว้ 2 ตัวนึงชี้ซ้าย ตัวนึงชี้ขวา
3. ตัวชี้ซ้าย ให้ไล่ไปทางขวาเรื่อยๆ จนกว่าจะเจอตัวที่มากกว่าหรือเท่ากับ pivot  
4. ส่วนตัวขวา ให้ไล่ไปทางขวาเรื่อยๆ จนกว่าจะเจอตัวที่มากกว่าหรือเท่ากับ pivot  
5. จับตัวที่ตัวชี้ทั้ง 2 ชี้อยู่ สลับที่กัน แล้วขยับตัวชี้ทั้ง 2 เข้าหากัน 1 ตำแหน่ง
6. ถ้าเกิดตัวชี้ทั้ง 2 ยังไม่ไขว้กัน กลับไปทำข้อ 3 ไปเรื่อยๆ
7. ถ้าไขว้กันแล้ว แบ่งฟาก เรียงฟากซ้ายก่อน แล้วเรียงฟากขวา