วันอาทิตย์ที่ 23 เมษายน พ.ศ. 2560
บที่ 9
การจัดเรียงข้อมูล Sorting
ความสำคัญของการจัดเรียงข้อมูล
การจัดเรียงข้อมูล เป็นการจัดการข้อมูลที่กระทำกันมากในงานประยุกต์ต่างๆ เช่น การทำข้อมูลนักศึกษามาจัดเลียงลำดับรหัสนักศึกษา เพื่อนำไปใช้ในการพิมพ์ใบเซ็นชื่อเข้าสอบหรือการเรียงข้อมูลพนักงานตามรหัสพนักงานเพื่อใช้งการพิมพ์สลิปเงินเดือน เป็นต้น
การจัดเรียงข้อมูลแบบแทรกใส่
Insertion Sort
จะมีลักษณะเป็นแบบการจัดไพ่ในมือของผู้เล่น คือ มีผู้เล่นได้ไพ่ใบไหม่ เพิ่มขึ้นมา จะนไพ่ใบนั้นไปแทรกในำแต่งที่เหมาะสม ทำให้ไพ่ในมือบ่างส่วนต้องขยับตำแหน่งออกไป ซึ่งการจัดเรียงลำดับข้อมูลแบบแทรกนิจะเริ่มพิจารณาคีย์ในตำแหน่งที่ 2 เป็นต้นไป โดยนำคีย์พิจารณาไปแทรกในตำแหน่งที่ถูกต้องและจะมีผลคีย์ให้ตำแหน่งที่อยู่หลังตำแหน่งที่แทรกขยับตำแหน่งออกไปเรื่อย ๆ
หลักการทำคือ จะอ่านข้อมูลมาที่ละตัว แล้วนำไปแทรกลงในจตำแหน่งที่เหมาะสมบนแถวข้อมูบไหม่ที่เตี่ยมไว้จะมขั้นตอนดังนี้
- สร้งแถวข้อมูลมาไหม่ที่มีขนาดเท่ากับจำนวนข้อมูลที่ต้องการจัดเรียง
- อ่านข้อมูลแรกแล้วไส่ลงในตำแหน่งแทรกในแทวข้อมูลไหม่
- อ่านข้อมูลทัดไปมา 1 ตัวแล้วเปรียบเทียมกับข้อมูลไหม่ที่ละตัว ตั้งแต่ตัวแรกไปจนถึงตัวสุดท้าย เพื่อหาตำแหน่งที่เหมาะสมในแถวข้อมูลไหม่โดยถ้าข้อมูลที่อ่านมาน้อยกว่าข้อมูลใดในแถวก็จะเลื่อนข้อมูบในแถวตั้งแต่ข้อมูลนั้นไป แล้วใส่ข้อมูลที่อ่านเข้ามาลงในตำแหน่งนั้น ถ้าข้อมูลทั้งหมดในแถวน้อยกว่าข้อมูลที่อ่านมาก็จะใส่ข้อมูลที่อ่านมาไว้ทัดจากข้อมูลตัวสุดท้ายในแถว
- ทำซ้ำข้้นตอนที่ 3 จนครบทั้งชุดข้อมูล
ตัวอย่าง
{23, 78, 45, 8, 32, 56}
การเรียงลำดับแบบแทรก จะมีการเรียงลำดับข้อมูลทั้งหมด n-1 รอบ
กรณีที่ดีที่สุด ข้อมูลถูกจัดเรียงลำดับเรียบรอยแล้ว กรณีแต่ละรอบจำมีการเปรียบเทียบคีย์เพียงครั้งเดี่ยว เพราะฉะนั้นจำนวนการเปรียบเทียบคีย์คือ n-1
กรณี่แย่ที่สุด ข้อมูลถูกจัดเรียงลำดับกลับกัน คือ เรียงลำดับค่าคีย์จากมากไปห้าน้อย (ในกรณีที่ต้องการจัดเรียงลำดับจากน้อยไปหากมาก)
การจัดเรียงข้อมูลแบบเลือก
Selection Sort
จะเป็นการเรียงลำดับข้อมูลที่เรียงงายตรงไปตรงมา การทำงานของแต่ละรอบของวิธีนี้จะค้นหาหรือสแกนค่าตัวเลขที่มาค่าน้อยที่สุดภายในลิสต์โดยในรอบแรกจเริ่มต้นสแกนค้นหาตั้งแต่ตัวแรกจนถึงต้วสุดท้าย หลังจากที่ได้พบตำแหนงของค่าที่น้อยที่สุดแล้ว ก็จะทำการสะลับตำแหน่งกัน จากนั้นในรอบต่อไปก็จะขยับตำแหน่งไปยังตัวถัดไป ซึ่งก็คือ ตัวที่สอง และทำการสแกนข้อมูลที่มีค่าน้อยทีสุดตั้งแต่ตัวที่สองจนถึงตัวสุดท้าย เมื่อพบแล้ว ก็จะสลับตำแหน่งกันเช่นเคย โดยจำทำเช่นนี้ไปเรื่อย ๆ จนครบทุกตัว ก็จะได้ชุดข้อมูลที่จัดเรียงสมบูรณ์
ขั้นตอนในการทำ
- เริ่มจาก เลือกค่าของข้อมูลที่มีค่าน้อยที่สุด
- นำมาแลกเปลี่ยกับค่าในตำแหน่งแรกสุดของกลุ่ม
- หลังจากนั้นกระทำตามหลักการทั้ง 2 กับข้อมูลที่เหลื่อ คือ ครั้งที่ 2 ค่า A(2) จะถูกแลกกับค่าที่เหลือกแล้วว่าน้อยที่สุดในลิสต์ A(2)....A(n)
- และครั้งที่ 3 ค่า A(3) จะถูกแลกกับค่าที่เลือกแล้วว่าน้อยที่สุดในลิตส์ A(3)....A(n)
- และเรียงไปจนกระทั่งเลือข้อมูลที่ถูกเปรี่ยบเทียบแค่ 2 ค่าคือ A(n-1) และ A(n) ดั้งนั้นจำนวนรอบในากรกระทำเป็น n-1 รอบ
ตัวอย่าง
{44, 33, 11, 85, 77, 60}
เป็นการเรียงข้อมูลแบบ Selection Sort เป็นวิธีเรียบง่าย แต่ก็เป็นวิธีที่มีจำนวนรอบการทำงานมากที่สุด ดั้งนั้นหากข้อมูลดอินพุตมีประริมาณมาก การเรียงข้อมูลด้วยวิธีนี้จึงไม่เหมาะเท่าไร
การจัดเรียงข้อมูลแบบฟองอากาศ
Bubble Sort
เป็นการเรียงลำดับข้อมูลด้วยการเปรียบเทียบข้อมูลเป็นคู่ที่ติดกันในแต่ละรอบ การทำงานเพื่อสลับตำ แหน่งกัน โดย
- ใช้เปรี่ยบเทียบคีย์ที่อยู่ติดกันทีละคู่
- ถ้าคีย์ที่เปรียบเทียบไม่อยู่ในตำแหน่งที่ต้องการสลับที่กัน
- ทิศทางการทำงานอาจจะทำจากคู่ซ้ายไปหาขวา หรือคู่ขวาไปหาซ้าย
- ในแต่ระรอบที่เปรียบเทียบ คีย์ที่มีค่ามากจะถูกสลับไปตำแหน่งท้าย กรือคีย์ที่มีค่าน้อยจะถูกสลับไปยังตำแหน่งตอนบน(จะเลือกเปรียบเทียบจากขวามาซ้าย หรือซ้ายไปหาขวาก็ได้)
- ข้อมูลที่มีค่ามากกว่าสลับไปตอนท้ายของข้อมูล
- การทำงานจะแบ่งลิตส์ออกเป็นสองส่วน คือส่วนที่จัดเรียงแล้วอยู่ฝั่งซ้ายและส่วนที่ยังไม่จัดเรียงจะยอู่ฝั่งขวา
- ในแต่ระรอบการทำงานจะมีการเปรียบเทียบค่าในแต่ละคู่ที่อยู่ติดกัน
- การทำงานเริ่มต้นที่ท้ายลิสต์ (เรียงจากน้อยไปมาก) และจะสลับค่าเมืออยู่ผิดลำดับ ซึ่งจะทำไปเรื้อย ๆ จากนั้นค่าที่น้อยทีสุดจะถูกขยับขึ้นไปเก็บไว้ในฝั่งลิสต์ที่ได้จัดเรียงแล้ว
- กำแพงที่ทำหน้าที่ตำแหน่ง ดรรชนีจะเพิ่มค่าอีกหนึ่งด้วยการขยับไปทางขวาอีกหนึ่งตำแหน่งเพื่อจะได้จัดการเปรียบเทียบกับค่าที่ยังไม่ได้จัดเรียง จนกว่าข้อมูลในลิสต์จะถูกจัดเรียงหมด
ตัวอย่าง
{23, 78, 45, 8, 32, 56}
การจัดเรียงข้อมูลโดยใช้ฮีพ
Heap Sort
Heap Sort หรือบางครั้งเรียกว่า Tree Sort จะอาศัยโครงสร้างข้อมูล
แบบ Binary Tree แต่กแตกกิ่งก้านของโหนดในต้นไม้จะต้องอยู่ภายใต้เงื่อนไข ต่อไปนี้น
- ที่ทุกระดับของ Heap จะแตกสาขาออกไปได 2 ทาง คือทางซ้ายและ ทางขวา
- จะต้องมีโหนดในระดับบนครบ 2 ด้านก่อน จึงจะแตกโหนดต่อในระดับล่างได้
- การแตกโหนดออกไปนั้นจะต้องเริ่มทางด้านซ้ายก่อน จึงจะแตกไปทางด้านขวาตามลำดับ
- ค่าคีย์ของโหนด จะต้องถูกจัดในลักษณะที่ว่า โหนดตัวบน (FATHER)จะต้องมีค่าของคีย์สูงกว่าโหนดตัวล่าง (SON)
ขั้นตอนการเรียงลำดับข้อมูล
- สร้างไบนารีทรี
- สร้างฮีป โดยให้โหนดแม่มีค่ามากกว่าโหนดลูกเสมอ
- สลับข้อมูลในตำแหน่งท 1 กับตำแหน่งที่ n แล้วตัดข้อมูลในตำแหน่ง ที่ n ออก
- ปรับทรีที่เหลือให้เป็นฮีป โดยทำการเปรียบเทียบโหนดลูกสองโหนดพร้อมกันในแต่ละระดับ ถ้าโหนดลูกโหนดใด มีค่ามากกว่าก็ให้สลับตำแหน่งกับโหนดแม่
- สลับข้อมูลในตำแหน่งที่ 1กับตำแหน่งที่ n -1
- ปรับทรีที่เหลือให้เป็นฮีป
- ทำวนไปอย่างนี้ เรื่อย ๆ จนกระทั่งถึงการสลับข้อมูลในตำแหน่งที่ 1 กับ ตำแหน่งที่ 2 ก็จะได้ข้อมูลที่เรียงลำดับจากน้อยไปมากตามต้องการ
ตัวอย่าง
เป็ นการเรียงลำดับที่อาศัยหลักการ Divide and Conquer โดยจะแบ่ง
ข้อมูลออกเป็ น 2 ส่วน ซึ่งแต่ละส่วนจะแบ่งย่อยข้อมูลเป็ นอีก 2 ส่วนเรื่อยไป จนกระทั่งไม่สามารถแบ่งได้อีก แล้วจึงเรียงลำดับข้อมูลแต่ละส่วนย่อย จากนั้นนำข้อมูลข้อมูลแต่ละส่วนย่อยมารวม (Merge) เข้าเป็นข้อมูลชุดเดียวกันพร้อมทั้งเรียงลำดับ
ตัวอย่าง
การจัดเรียงข้อมูลแบบเร็ว
Quick Sort
เป็ นการเรียงลำดับที่อาศัยหลักการ Divide and Conquer โดยจะแบ่ง ข้อมูลออกเป็น 2 ส่วน ซึ่งแต่ละส่วนจะแบ่งย่อยข้อมูลเป็นอีก 2 ส่วนเรื่อยไป จนกระทั่งไม่สามารถแบ่งได้อีก แล้วจึงเรียงลำดับข้อมูลแต่ละส่วนย่อย จากนั้นนำ ข้อมูลแต่ละส่วนย่อยมารวม (Merge) เข้าเป็นข้อมูลชุดเดียวกันพร้อมทั้งเรียงลำดับข้อมูล
ตัอวอย่าง
3 9 1 2 6 7 5 4 8 //Start
3 4 1 2 5 7 6 9 8
1 4 3 2 5 7 6 9 8
1 2 3 4 5 7 6 9
8
1 2 3 4 5 6 7 9 8
.1 2 3 4 5 6 7 8 9
- .เลือก pivot มา 1 ตัว (นิยมตัวกลาง หรือสุ่ม)
- เตรียมตัวชี้ ไว้ 2 ตัว ตัวนึงชี้ ซ้าย ตัวนึ่งชี้ ขวา
- ตัวชี้ ซ้าย ให้ไล่ไปทางขวาเรื่อยๆ จนกว่าเจอตัวที่มากกว่าหรือเท่ากับ pivot
- .ส่วนตัวขวา ให้ไล่ไปทางซ้ายเรื่อยๆ จนกว่าเจอตัวที่น้อยกว่าหรือเท่ากับ pivot
- จับตัวที่ตัวชี้ ทั้ง 2 ชี้ อยู่ สลับที่กัน แล้วขยับตัวชี้ ทั้ง 2 เข้าหากัน 1 ต าแหน่ง
- ถ้าเกิดตัวชี้ ทั้ง 2 ยังไม่ไขว้กัน กลับไปท าข้อ 3 ไปเรื่อยๆ
- .ถ้าไขว้กันแล้ว แบ่งฟาก เรียงฟากซ้ายก่อน แล้วเรียงฟากขวา
Xดี
ตอบลบXd
ตอบลบ