การจัดเรียงลำดับ
(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)
ไม่มีความคิดเห็น:
แสดงความคิดเห็น