การจัดเรียงข้อมูล มี กี่ แบบ อะไร บาง แตก ต่าง กัน อย่างไร

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

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

1. การจัดเรียงข้อมูลแบบแทรก หรือ insertion sort 

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

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

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

ตัวอย่างเช่น : ให้ข้อมูล 2 5 1 4 3 มาจัดเรียงแบบ Insertion sort

2. การจัดเรียงข้อมูลแบบเลือ หรือ 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 รอบ

           ตัวอย่างเช่น : ให้ข้อมูล 3 1 4 8 5 2 9 6 7 ให้จัดเรียงแบบ selection sort

3. การจัดเรียงข้อมูลแบบฟองอากาศ หรือ bubble sort 

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

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

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

            ตัวอย่างเช่น : ให้ข้อมูล 2 3 4 5 1 ให้จัดเรียงแบบ bubble sort โดยสีเขียวแสดงคู่ที่เห็นว่าข้อมูลอยู่ถูตำแหน่งแล้วจึงไม่มีการสหลับ สวนสีแดงแสดงถึง การเปียบเทียบคู่แล้วอยู่ไม่ถูตำแหน่งแล้วสหลับที่ จากนั้นก็ไปเปียบเทียบกับข้อมูลตัวถัดไปทำแบบนี้ไปเรื้อยๆจนกวาข้อมูลจะอยู่ถูกตำแหน่ง

4. การจัดเรียงข้อมูลแบบรวมข้อมูลเข้าด้วยกัน หรือ Merge sort 

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

 ตัวอย่างเช่น : ให้ข้อมูล 12  35  87  26  9  28  7 ให้จัดเรียงแบบ Merge sort โดยแยกข้อมูลออกเป็นสองส่วนจนไม่สามารถแยกได้แล้ว แล้วเปลียบเทียบที่ละสวนโดยการจัดเรียงข้อมูลไปที่ละสวนแล้วค่อยๆรวมข้อมูลเข้าด้วยกันเรื่อยๆ จนข้อมูลเรียงรำดับอย่างถูกตำแหน่ง

5. การจัดเรียงข้อมูลแบบเร็ว หรือ 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. ถ้าไขว้กันแล้ว แบ่งฟาก เรียงฟากซ้ายก่อน แล้วเรียงฟากขวา

        ตัวอย่างเช่น : ให้ข้อมูล 5 1 1 4 8 6 3  ให้จัดเรียงแบบ Quick sort โดยหาค่าตำแหน่งสว่นกลางแล้วเปียบเทียบส่วนกลางหากเปียบเทียบไปด้านช้ายหาค่าที่สูงกว่า หากไปด้าขวาหาค่าทีตำกว่าส่วนกลาง เมือเจอแล้วให้หยุดแล้วสหลับที่ค่าด้านช้ายกับด้านขวาทำแบบนี้ไปจนกว่าข้อมูลจะจัดเรียงกัน

6. การจัดเรียงแบบฮีป หรือ 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 ก็จะได้ข้อมูลที่เรียงลำดับจากน้อยไปหามากตามต้องการ

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

โดยในวีดีโอจะให้ข้อมูลมาคือ 11 6 4 1 3 7 8 12 โดยวางข้อมูลไวในไบรนารีทรี แล้วเปียนข้อมูลให้เป็น  ( tree sort ) กอน แล้วจืงเรีมจัดการบ้อมูลให้มาเรียงรำดับแบบ ฮีป หากนำข้อมูลที่ถูกจัดเรียงแล้วนั้นออกไปอาจทำให้ tree  นั้นหลุดออกจากการเป็น tree sort ก็จะเปลียน tree นั้นให้กลับมาเป็น tree sort เสยกอนแล้วค่อยเรียงรำดับข้อมูลตัวตอไปทำแบบนี้ไปเรียๆ จนข้อมูลเรียงอยู่ในตำแหน่งที่เหมาะสม