การจัดเรียงข้อมูล (Sorting)

การจัดเรียงข้อมูล (Sorting)

        การจัดเรียงหรือเรียงลำดับข้อมูล(Sorting) คือ การจัดเรียงข้อมูลให้เรียงลำดับตามเงื่อนไขที่กำหนดไว้ โดยอาจเรียงจากน้อยไปมาก หรือค่ามากไปน้อยก็ได้ การเรียงลำดับข้อมูลในระบบคอมพิวเตอร์ จะแบ่งเป็น 2 ลักษณะใหญ่ ๆ คือ 

1. การจัดเรียงลำดับข้อมูลภายใน (Internal sorting) 

• ใช้กับข้อมูลที่มีจำนวนไม่ใหญ่กว่าเนื้อที่ในหน่วยความจำ (main memory)
• ไม่ต้องใช้หน่วยความจำสำรอง เช่น ดิสก์, เทป เป็นต้น

2. การเรียงลำดับข้อมูลภายนอก (External sorting)

• ใช้กับข้อมูลที่มีจำนวนใหญ่เกินกว่าที่จะเก็บลงในหน่วยความจำได้หมดภายในครั้งเดียว
• จะใช้หน่วยความจำภายนอก เช่น  ดิสก์, เทป สำหรับเก็บข้อมูลบางส่วนที่ได้รับการเรียงลำดับข้อมูลแล้ว แล้วจึงค่อยจัดการเรียงลำดับข้อมูลในส่วนต่อไป

ประเภทของการเรียงลำดับข้อมูล

1. Insertion Sort

        การจัดเรียงแบบแทรก คือ การเรียงข้อมูลโดยนำข้อมูลที่จะทำการจัดเรียงนั้นๆ ไปจัดเรียงทีละตัว โดยการแทรกตัวที่จะเรียงไว้ในตำแหน่งที่เหมาะสมของข้อมูลที่มีการจัดเรียงเรียบร้อยแล้ว ณ ตำแหน่งที่ถูกต้อง

ขั้นตอนการทำงาน

• เปรียบเทียบค่ากับตำแหน่งถัดไปแทน
• สลับตำแหน่งให้อยู่ในตำแหน่งที่เหมาะสม

2. Shell Sort

        การจัดเรียงแบบเชลล์ เป็นการจัดเรียงที่อาศัยเทคนิคการแบ่งข้อมูลออกเป็นกลุ่มย่อยหลายๆ กลุ่ม แล้วจัดเรียงข้อมูลในกลุ่มย่อยๆนั้น  หลังจากนั้นก็ให้รวมกลุ่มย่อยๆ ให้ใหญ่ขึ้นเรื่อยๆ ขั้นสุดท้ายให้จัดเรียงข้อมูลทั้งหมดนั้นอีกครั้ง

ตัวอย่าง กำหนด Segment เมื่อ K=3

ขั้นตอนการทำงาน

• โดยทั่วไปการเลือกค่า K ตัวแรกมักจะเลือกใช้ค่าเท่ากับครึ่งหนึ่งของข้อมูล เช่น ข้อมูลมี 10 ตัว K = n/2 = 10/2 = 5
• เรียงข้อมูลทุกตัวให้เสร็จสิ้น แล้วกำหนดค่า K ใหม่ (โดยทั่วไปจะเป็นครึ่งหนึ่งของค่า K ตัวแรก เช่น K1 = 5; K2 = 5/2 = 2)
• ถ้า K > 1 ให้ทำซ้ำ จนกระทั่งเหลือข้อมูลกลุ่มเดียว ถ้า K = 1 ให้เรียงลำดับตามปกติ

ตัวอย่างการทำงานในละรอบของ K

3. Selection Sort

        การจัดเรียงแบบเลือก เป็นวิธีการเรียงข้อมูลโดยจะเริ่มต้นค้นหาข้อมูลตัวที่น้อยที่สุดจากข้อมูลที่มีอยู่ทั้งหมด แล้วสลับที่ข้อมูลกับตัวแรก แล้วกลับไปหาข้อมูลตัวที่น้อยที่สุดในกองต่อไปสลับที่กับข้อมูลจนกว่าจะหมดกอง

ขั้นตอนการทำงาน

• ค้นหาตัวเลขที่มีค่าน้อย/มากที่สุดตั้งแต่ตัวแรกไปจนถึงตัวสุดท้าย
• สลับตำแหน่งตัวเลขที่มีค่าน้อย/มากที่สุด

4. Heap Sort

        ฮีปเป็นโครงสร้างข้อมูลที่มีลักษระการจัดเก็บข้อมูลแบบไบนารีทรี คือ แต่ละโหนดจะมีโหนดลูกได้ไม่เกิน 2 โหนด และการจัดเก็บข้อมูลจะต้องจัดเก็บให้เต็มทีละชั้นเรียงจากโหนดด้านซ้ายมือไปด้านขวามือเสมอ ฮีปแบ่งเป็น 2 ประเภท คือ

• Min Heap: ที่โหนดใดๆ ก็ตามภายในฮีป ข้อมูลที่ซับทรีจะต้องมีค่ามากกว่าหรือเท่ากับข้อมูลที่ตัวมันเสมอ(รูทโหนดมีค่าต่ำที่สุด)
•  Max Heap : ที่โหนดใดๆ ก็ตามภายในฮีป ข้อมูลที่ซับทรีจะต้องมีค่าน้อยกว่าหรือเท่ากับข้อมลูลที่ตัวมันเสมอ (รูทโหนดมคีค่าสูงที่สุด)

ขั้นตอนการทำงาน

5. Bubble Sort 

        การจัดเรียงแบบบับเบิล เป็นการจัดเรียงโดยการเปรียบเทียบค่า 2 ค่าที่ติดกัน ทำต่อเนื่องกันไปเรื่อยๆ 

ขั้นตอนการทำงาน

6. Quick Sort

        การจัดเรียงแบบควิกซ์ ใช้หลักการ divide-and-conquer อาศัยการจัดแบ่งข้อมูลทั้งหมดออกเป็น 2 กลุ่ม โดยกลุ่มแรกจะเป็นกลุ่มของข้อมูลที่มีค่าน้อยกว่าค่ากลางที่กำหนด และส่วนที่สองเป็นกลุ่มของข้อมูลที่มีค่ามากกว่าค่ากลางที่กำหนด หลังจากนั้นแบ่งข้อมูลแต่ละส่วนออกเป็น 2 ส่วนเช่นเดิม แบ่งไปเรื่อยๆจนไม่สามารถแบ่งได้ก็จะได้ข้อมูลที่เรียงกัน

ขั้นตอนการทำงาน

• มีการเลือกข้อมูลตัวหนึ่งเรียกว่า Pivot ที่ใช้เป็นตัวแบ่งแยกชุดข้อมูลที่เรามีออกเป็นส่วน คือ ข้อมูลที่มีค่าน้อยกว่า Pivot และข้อมูลที่มีค่ามากกว่า Pivot
• แบ่งข้อมูลไปเรื่อยๆ 
• เรียงข้อมูลแต่ละส่วนย่อยๆ

        การแบ่งส่วนข้อมูลใช้หลักการ Picking the pivot คือการกำหนดค่าสมมุติที่อยู่ตรงกลาง โดยจะเลือกข้อมูลที่อยู่ตรงกลางของข้อมูลทั้งหมด มาใช้เป็นค่ากึ่งกลาง ดังนั้น ข้อมูลอื่นๆที่มีค่ามากกว่าค่าที่อยู่ตรงกลางจะอยู่กลุ่มทางขวามือ ค่าที่น้อยกว่าจะอยู่กลุ่มทางซ้ายมือ

                                      ถ้าข้อมูล < Pivot แล้ว SortLeft = SortLeft + 1

                                      ถ้าข้อมูล >= Pivot แล้ว SortRight = SortRight - 1

                                      สลับ  Pivot กับข้อมูลตัวที่ SortLeft - 1

7. Merge Sort

        การเรียงแบบผสาน (Merge Sort ) -- การทำ Merge Sort ใช้หลักการ divide-and-conquer เหมือนกับ Quick Sort มีลักษณะของการแบ่งข้อมูลออกเป็นส่วนๆ แต่กระบวนการเรียงข้อมูลนั้นจะแตกต่างไปจาก Quick sort  Quick sort กระทำการสลับข้อมูลไปพร้อมกับการแบ่งข้อมูลออกเป็นส่วนๆ แต่ merge sort นี้ กระทำการแบ่งข้อมูลออกเป็นส่วนๆก่อน แล้วค่อยเรียงข้อมูลในส่วนย่อย จากนั้นนำเอาข้อมูลส่วนย่อยที่เรียงไว้แล้ว มารวมกันและเรียงไปในเวลาเดียวกัน อัลกอริทึมจะเรียงพร้อมกับผสานข้อมูล เข้าด้วยกันจนกระทั่งข้อมูลทุกตัวรวมกันกลายเป็นข้อมูลเดียวอีกครั้ง 

ขั้นตอนการทำงาน

8. Radix Sort

        การเรียงลำดับแบบฐานเป็นการเรียงลำดับโดยการพิจารณาข้อมูลทีละหลักใช้ข้อมูลกับ Linked List

1. เริ่มพิจารณาจากหลักที่มีค่าน้อยที่สุดก่อน นั่นคือถ้าข้อมูลเป็นเลขจำนวนเต็มจะพิจารณาหลักหน่วยก่อน
2. การจัดเรียงจะนำข้อมูลทีละตัว แล้วนำไปเก็บไว้ที่ซึ่งจัดไว้สำหรับค่านั้น เป็นกลุ่มๆ ตามลำดับการเข้ามา
3. ในแต่ละรอบเมื่อจัดกลุ่มเรียบร้อยแล้ว ให้รวบรวมข้อมูลจากทุกกลุ่มเข้าด้วยกัน โดยเริ่มเรียงจากกลุ่มที่มีค่าน้อยทีสุดก่อนแล้วเรียงไปเรื่อยๆ จนหมดทุกกลุ่ม
4. ในรอบต่อไปนำข้อมูลทั้งหมดที่ได้จัดเรียงในหลักหน่วยเรียบร้อยแล้วมาพิจารณาจัดเรียงในหลักสิบต่อไป ทำไปเรื่อยๆ จนกระทั่งครบทุกหลัก

9. Bucket Sort

        สมมติว่าเรารู้ว่าขนาดของ array ที่เราต้องจัดเรียงข้อมูลมีขนาดเล็ก และแน่นอน เราอาจเลือกใช  การจัดเรียงแบบกระจาย (distribution sort) มาทำการจัดเรียงข้อมูลให้เราและ Bucket sort ก็เป็นเทคนิควิธีอีก แบบหนึ่งที่ใช้การกระจายของข้อมูลมาเป็นตัวช่วยในการจัดเรียงลองดูภาพตัวอย่างของข้อมูลที่มีอยู่ใน array 

ตัวอย่าง

10. Comb Sort

        เป็น algorithm สำหรับการจัดเรียงข้อมูลที่ปรับปรุงมาจาก bubble sort โดยกำหนดให้การเปรียบเทียบข้อมูลไม่จำเป็นที่จะต้องเป็นข้อมูลที่อยู่ติดกันเสมอไป (gap = 1) กระบวนจะเริ่มด้วยการหา gap ระหว่างข้อมูลซึ่งในทางปฏิบัตินั้นจะให้gap มีค่าเท่ากับขนาด ของ list หารด้วย 1.3 (เรียกว่า shrink factor – เป็นค่าที่ผู้ออกแบบ comb sort กำหนด) การจัดเรียงจะใช้ค่า gap นี้และจะทำการจัดเรียงด้วยการหาค่า gap ใหม่จนกว่า gap จะเท่ากับ 1 ก็ จะยุติการทำงาน