การจัดเรียงข้อมูล Sort
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)เข้าเป็นข้อมูลชุดเดียวกันพร้อมทั้งเรียงลำดับข้อมูล
มีขั้นตอนในการจัดเรียงข้อมูลดังนี้
- เลือก pivot มา 1 ตัว (นิยมตัวกลาง หรือสุ่ม)
- เตรียมตัวชี้ไว้ 2 ตัวนึงชี้ซ้าย ตัวนึงชี้ขวา
- ตัวชี้ซ้าย ให้ไล่ไปทางขวาเรื่อยๆ จนกว่าจะเจอตัวที่มากกว่าหรือเท่ากับ pivot
- ส่วนตัวขวา ให้ไล่ไปทางขวาเรื่อยๆ จนกว่าจะเจอตัวที่มากกว่าหรือเท่ากับ pivot
- จับตัวที่ตัวชี้ทั้ง 2 ชี้อยู่ สลับที่กัน แล้วขยับตัวชี้ทั้ง 2 เข้าหากัน 1 ตำแหน่ง
- ถ้าเกิดตัวชี้ทั้ง 2 ยังไม่ไขว้กัน กลับไปทำข้อ 3 ไปเรื่อยๆ
- ถ้าไขว้กันแล้ว แบ่งฟาก เรียงฟากซ้ายก่อน แล้วเรียงฟากขวา
ตัวอย่างเช่น : ให้ข้อมูล 5 1 1 4 8 6 3 ให้จัดเรียงแบบ Quick sort โดยหาค่าตำแหน่งสว่นกลางแล้วเปียบเทียบส่วนกลางหากเปียบเทียบไปด้านช้ายหาค่าที่สูงกว่า หากไปด้าขวาหาค่าทีตำกว่าส่วนกลาง เมือเจอแล้วให้หยุดแล้วสหลับที่ค่าด้านช้ายกับด้านขวาทำแบบนี้ไปจนกว่าข้อมูลจะจัดเรียงกัน
6. การจัดเรียงแบบฮีป หรือ Heap sort
Heap Sort หรือบางครั้งเรียกว่า Tree Sort จะอาศัยโครงสร้างข้อมูลแบบ Binary Tree แต่การแตกกิ่งก้านของโหนดในต้นไม้จะต้องอยู่ภายใต้เงื่อนไขต่อไปนี้
- ที่ทุกระดับของ Heap จะแตกสาขาออกไปได้ 2 ทาง คือทางซ้ายและทางขวา
- จะต้องมีโหนดในระดับบนครบ 2 ด้านก่อน จึงจะแตกโหนดต่อในระดับล่างได้
- การแตกโหนดออกไปนั้นจะต้องเริ่มจากทางซ้ายก่อน จึงจะแตกไปทางด้านขวาตามลำดับ
- ค่าคีย์ของโหนด จะต้องถูกจัดในลักษณะที่ว่า โหนดตัวบน (FATHER) จะต้องมีค่าของคีย์สูงกว่าโหนดตัวล่าง (SON)
- สร้างไบนารีทรี
- สร้างฮีป โดยให้โหนดแม่มีค่ามากกว่าโหนดลูกเสมอ
- สลับข้อมูลในตำแหน่งที่ 1 กับตำแหน่งที่ n แล้วตัดข้อมูลในตำแหน่งที่ n ออก
- ปรับทรีที่เหลือให้เป็นฮีป โดยทำการเปรียบเทียบโหนดลูกสองโหนดพร้อมกันในแต่ละระดับ ถ้าโหนดลูกโหนดใด มีค่ามากกว่าก็สลับตำแหน่งกับโหนดแม่
- สลับข้อมูลในตำแหน่งที่ 1 กับตำแหน่งที่ n-1
- ปรับทรีที่เหลือให้เป็นฮีป
- ทำวนไปอย่างนี้เรื่อยๆ จนกระทั่งถึงการสลับข้อมูลในตำแหน่งที่ 1 กับตำแหน่งที่ 2 ก็จะได้ข้อมูลที่เรียงลำดับจากน้อยไปหามากตามต้องการ
โดยในวีดีโอจะให้ข้อมูลมาคือ 11 6 4 1 3 7 8 12 โดยวางข้อมูลไวในไบรนารีทรี แล้วเปียนข้อมูลให้เป็น ( tree sort ) กอน แล้วจืงเรีมจัดการบ้อมูลให้มาเรียงรำดับแบบ ฮีป หากนำข้อมูลที่ถูกจัดเรียงแล้วนั้นออกไปอาจทำให้ tree นั้นหลุดออกจากการเป็น tree sort ก็จะเปลียน tree นั้นให้กลับมาเป็น tree sort เสยกอนแล้วค่อยเรียงรำดับข้อมูลตัวตอไปทำแบบนี้ไปเรียๆ จนข้อมูลเรียงอยู่ในตำแหน่งที่เหมาะสม
ความคิดเห็น
แสดงความคิดเห็น