การเรียงลำดับข้อมูล (Sorting)
การจัดเรียงลำดับ (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 ก็จะต้องพิจารณาว่าจะไว้ก่อนหรือไว้หลังใบแรก
และเช่นเดียวกัน เมื่อหยิบไพ่ใบถัด ๆ มา ก็จะต้องพิจารณาว่าจะวางใบตำแหน่งใดเพื่อให้เกิดการเรียงลำดับ จนกระทั่งหมด
ตัวอย่าง: Insertion Sort
ข้อมูล 8 ตัวทำ 7 รอบ = 44,55,12,42,94,18,06,67
รอบที่ ข้อมูล
2 44 55 12 42 94 18 06 67
3 12 44 55 42 94 18 06 67
4 12 42 44 55 94 18 06 67
5 12 42 44 55 94 18 06 67
6 12 18 42 44 55 94 06 67
7 06 12 18 42 44 55 94 67
8 06 12 18 42 44 55 67 94
การจัดเรียงแบบเลือก (Selection Sort)
🔺เป็นการจัดเรียงโดยการเริ่มต้นค้นหาข้อมูลตัวที่น้อยที่สุดจากข้อมูลที่มีอยู่ทั้งหมด
แล้วเอามาเก็บไว้ข้างนอก
แล้วกลับไปหาข้อมูลตัวที่น้อยที่สุดในกองต่อไปจนกว่าจะหมดกอง
ตัวอย่าง: Selection Sort
ข้อมูล 8 ตัวทำ 7 รอบ = 44,55,12,42,94,18,06,67
รอบที่ ข้อมูล
1 06 55 12 42 94 18 44 67
2 06 12 55 42 94 18 44 67
3 06 12 18 42 94 55 44 67
4 06 12 18 42 94 55 44 67
5 06 12 18 42 44 55 94 67
6 06 12 18 42 44 55 94 67
7 06 12 18 42 44 55 67 94
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)
 |
Merge Sort |
⧭สรุป⧭
ไมควรใชการเรียงลําดับแบบฟอง
การเรียงลำดับแบบเลือกยายขอมูลนอยครั้งสุด
ถ้าขอมูลมีมากไม่ควรใช้การเรียงลำดับแบบแทรก
การเรียงลำดับแบบผสานเร็วกว่าถ้าขอมูลมีมากแตตองการเนื้อที่เสริม
การเรียงลำดับแบบฮีปเปน O(n log n) แตชา
การเรียงลำดับแบบเร็ว ตองเขียนดี ๆ
ถึงเร็ว
