การเรียงลำดับข้อมูล
การจัดเรียงลำดับ (Sorting)
การจัดเรียงข้อมูล ให้เรียงลำดับตามเงื่อนไขที่กำหนดไว้ (มากไปน้อย หรือ น้อยไปมาก)
ในกรณีที่ข้อมูลในแต่ละ Record มีหลาย Field เราต้องพิจารณาเลือก Field ที่สนใจเพื่อใช้ในการเรียงลำดับ เช่น การจัดเรียงลำดับประวัตินักศึกษา อาจใช้หมายเลขประจำตัวของนักศึกษาเป็น Field โดยเรียงจากน้อยไปมาก
ประเภทของการเรียงลำดับข้อมูล
การจัดเรียงภายใน (Internal Sorting)
การจัดเรียงลำดับข้อมูลที่เก็บอยู่ในหน่วยความจำของเครื่องคอมพิวเตอร์ การจัดเรียงแบบนี้จะต้องอาศัยเทคนิคและวิธีการของโครงสร้างข้อมูลมาช่วย เช่น การใช้ Array หรือ Linked-List เข้ามาช่วย
การจัดเรียงภายนอก (External Sorting)
การจัดเรียงข้อมูลที่เก็บอยู่ในสื่อบันทึกข้อมูล เช่น Disk โดยทั่วไปการเรียงประเภทนี้ มักใช้กับข้อมูลที่มีจำนวนมาก ที่ไม่สามารถเก็บไว้ในหน่วยความจำได้หมด การเรียงในแบบนี้จะต้องแบ่งข้อมูลออกเป็นส่วนย่อย แล้วนำมาเรียงด้วยการจัดเรียงแบบภายในก่อน แล้วจึงนำแต่ละส่วนย่อยมารวมกัน
วิธีการจัดเรียงข้อมูล
การจัดเรียงแบบแลกเปลี่ยน (Exchange Sort)
การจัดเรียงแบบแทรก (Insertion Sort)
การจัดเรียงแบบเลือก (Selection Sort)
การจัดเรียงแบบแลกเปลี่ยน (BUBBLE SORT)
เป็นการจัดเรียงโดยการเปรียบเทียบค่า 2 ค่าที่ติดกัน
ทำต่อเนื่องกันไปเรื่อย ๆ และตัดสินใจว่าจะสลับตำแหน่งกันหรือไม่ เช่น ถ้าต้องการเรียงข้อมูลจากน้อยไปมาก ก็คือ
- ข้อมูลที่มีค่าน้อย ต้องอยู่ในตำแหน่งหน้า
- ข้อมูลที่มีค่ามาก จะอยู่ตำแหน่งหลัง
- ข้อมูล 2 ตัวที่อยู่ติดกัน ถ้า
- ถ้าข้อมูลตัวแรกมากกว่าตัวหลัง ก็จะต้องสลับตำแหน่งกัน
- แต่ถ้าข้อมูลตัวแรกน้อยกว่าข้อมูลตัวหลัง ก็ไม่ต้องสลับตำแหน่ง
- ทำเช่นนี้ซ้ำกันไปเรื่อย ๆ จนกว่าการเปรียบเทียบของข้อมูลตลอดทั้งชุดจะไม่ต้องมีการสลับตำแหน่งเลย
Bubble Sort
แนวคิด คือค่าที่มากๆ จะต้องถูกนำไป (ลอยไป) ไว้ด้านท้าย
เหมือนลูกโป่งที่ขนาดใหญ่จะลอยได้เร็วและสูง
แนวคิด
- เริ่มนำข้อมูลตัวแรกเทียบกับตัวที่ 2 ตัวไหนมากก็จะถูกสลับกัน ทำอย่างนี้ไปจนถึงตัวสุดท้าย เราจะได้
- ค่าที่มากที่สุด 1 ตัวไว้ด้านท้าย
- แต่ละครั้งจะได้ค่ามากที่สุดไปไว้ท้ายสุด
- จากนั้นเริ่มการเปรียบเทียบใหม่ตั้งแต่ตัวแรกถึงตัวที่ N-1
- จากนั้นเริ่มการเปรียบเทียบใหม่ตั้งแต่ตัวแรกถึงตัวที่ N-2
- จากนั้นเริ่มการเปรียบเทียบใหม่ตั้งแต่ตัวแรกถึงตัวที่ N-x
ทำจน x = N-1
ตัวอย่าง: Bubble Sort
ข้อมูล 8 ตัวทำ 7 รอบ = 44,55,12,42,94,18,06,67
รอบที่ ข้อมูล
1 06 44 55 12 42 94 18 67
2 06 12 44 55 18 42 94 67
3 06 12 18 44 55 42 67 94
4 06 12 18 42 44 55 67 94
5 06 12 18 42 44 55 67 94
6 06 12 18 42 44 55 67 94
7 06 12 18 42 44 55 67 94
การจัดเรียงแบบแทรก (Insertion Sort)
เป็นการจัดเรียงโดยการนำข้อมูลที่จะทำการเรียงนั้น ๆ ไปจัดเรียงทีละตัว
โดยการแทรกตัวที่จะเรียงไว้ในตำแหน่งที่เหมาะสมของข้อมูลที่มีการจัดเรียงเรียบร้อยแล้ว ณ ตำแหน่งที่ถูกต้อง
⧭ วิธีการลักษณะนี้จะคล้ายกับการหยิบไพ่ขึ้นมาเรียงทีละใบ ซึ่ง
ไพ่ใบแรกจะไม่ต้องสนใจอะไร
แต่เมื่อหยิบไพ่ใบที่ 2 ก็จะต้องพิจารณาว่าจะไว้ก่อนหรือไว้หลังใบแรก
และเช่นเดียวกัน เมื่อหยิบไพ่ใบถัด ๆ มา ก็จะต้องพิจารณาว่าจะวางใบตำแหน่งใดเพื่อให้เกิดการเรียงลำดับ จนกระทั่งหมด
การจัดเรียงแบบเลือก (Selection Sort)
🔺เป็นการจัดเรียงโดยการเริ่มต้นค้นหาข้อมูลตัวที่น้อยที่สุดจากข้อมูลที่มีอยู่ทั้งหมดแล้วเอามาเก็บไว้ข้างนอกแล้วกลับไปหาข้อมูลตัวที่น้อยที่สุดในกองต่อไปจนกว่าจะหมดกอง
HEAP SORT
- ในการจัดเรียงด้วยเวลา O(N log N) อัลกอริทึมที่ใช้พื้นฐานแนวคิดนี้ เรียกว่า heapsort และมี Big-Oh running time ดีกว่าอัลกอริทึมอื่น ๆ ที่กล่าวมาแล้ว
-วิธีการ คือ สร้าง binary heap (มีสมาชิก N ตัว) ซึ่งใช้เวลา O(N) จากนั้นทำ deleteMin N ครั้ง สมาชิกที่ถูกย้ายออกไปจาก heap ตัวแรก คือตัวที่มีค่าน้อยที่สุด และเรียงลำดับตามค่าไป แล้วนำไปเก็บใน Arrray อีกตัวหนึ่งจากนั้นก็คัดลอกกลับไปยัง Array เดิมซึ่งก็จะเป็นคำตอบในการจัดเรียง เนื่องจากการทำ deleteMin แต่ละตัวใช้ O(log N) ดังนั้น running time รวมทั้งหมด คือ O(N log N)
- หลังการทำงานจนเสร็จ Array ที่ได้ก็จะเป็น Arrayของสมาชิกที่จัดเรียงจากมากไปน้อย
- ถ้าต้องการจัดเรียงจากน้อยไปมาก เราก็จะใช้ heap ที่ parent มีค่ามากกว่า child ของมัน นั่นคือ (max)heap
- เราจะใช้ (max)heap ในการ implement ของเราและยังคงใช้ Array เช่นเดิม
- ขั้นแรกสร้าง heap ด้วย linear time จากนั้นทำ deleteMaxes จำนวน N - 1 ครั้ง ด้วยการสลับสมาชิกตัวสุดท้ายใน heap กับสมาชิกตัวแรก แล้วลดขนาดของ heap ลงแล้วทำการ percolating down
- หลังจบอัลกอริทึมจะได้ Arrayที่มีสมาชิกเรียงตามลำดับค่า
QUICK SORT
หลักการดำเนินงาน
- หาตำแหน่งในการแยกลิสต์
- แบ่งแยกข้อมูลออกเป็นสองส่วน และหาตำแหน่งในการแยกลิสต์
- ทำจนกว่าข้อมูลจะเรียงลำดับเรียบร้อย
การดำเนินการ
- เริ่มต้นใช้ข้อมูลตัวแรกเป็นตัวเปรียบเทียบ (pivot)
- ทำการเปรียบเทียบค่าของข้อมูลที่ชี้โดย first กับPivot ถ้าน้อยกว่า pivot ให้ทำการเลื่อน firstไปยังข้อมูลต่อไปและเปรียบเทียบไปจนกว่าจะพบแล้วจึงหยุดการเปรียบเทียบ
- เมื่อพบตำแหน่งแล้ว จะหันมาพิจารณาที่ last ชี้อยู่หากค่าที่ last ชี้อยู่มีค่าน้อยกว่าที่ first ชี้อยู่ให้สลับตำแหน่ง
- ทำการเปรียบเทียบค่าของข้อมูลที่ชี้โดย first กับPivot ถ้าน้อยกว่า pivot ให้ทำการเลื่อน firstไปยังข้อมูลต่อไปและเปรียบเทียบไปจนกว่าจะพบแล้วจึงหยุดการเปรียบเทียบ
- เมื่อพบตำแหน่งแล้ว จะหันมาพิจารณาที่ last ชี้อยู่หากค่าที่ last ชี้อยู่มีค่าน้อยกว่าที่ first ชี้อยู่ให้สลับตำแหน่ง
- พบตำแหน่งที่จะใช้แบ่งชุดข้อมูลแล้ว จึงทำการแบ่งข้อมูลออกเป็นสองชุด
-ดำเนินการแบบเดียวกับกับข้อมูลชุดขวามือดำเนินการกับข้อมูลที่เหลือเหมือนเดิมจนกว่าจะได้ข้อมูลในตำแหน่งต่างๆ จนครบ
MERGE SORT
กระบวนการแยกชุดข้อมูล
กระบวนการรวมชุดข้อมูล
ได้ชุดข้อมูลที่เรียงลำดับเรียบร้อยแล้ว
Merge Sort Algorithm Analysis
จำนวนครั้งของการเปรียบเทียบทั้งหมด
=ผลบวกทุกระดับของ(จำนวนลิสต์ในแต่ละระดับ * จำนวนครั้งของการเปรียบเทียบแต่ละลิสต์ )
= (N-1) *1 + (N/2 -1)*2 + (N/4 – 1)*4 +..+(2-1)*N/2
= ( N-1) + (N-2)+(N-4)+..+(N-N/2)
= Nlog2N จะได้ bigO(Nlog2N)
ไม่มีความคิดเห็น:
แสดงความคิดเห็น