การจัดเรียงและค้นหาข้อมูล
การจัดเรียงหรือเรียงลำดับข้อมูล(Sorting) คือ การจัดเรียงข้อมูลให้เรียงลำดับตามเงื่อนไขที่กำหนดไว้ โดยอาจเรียงจากน้อยไปมาก หรือค่ามากไปน้อยก็ได้ การเรียงลำดับข้อมูลในระบบคอมพิวเตอร์ จะแบ่งเป็น 2 ลักษณะใหญ่ ๆ คือ
1. การจัดเรียงลำดับข้อมูลภายใน (Internal sorting)
- ใช้กับข้อมูลที่มีจำนวนไม่ใหญ่กว่าเนื้อที่ในหน่วยความจำ (main memory)
- ไม่ต้องใช้หน่วยความจำสำรอง เช่น ดิสก์, เทป เป็นต้น
- ใช้กับข้อมูลที่มีจำนวนใหญ่เกินกว่าที่จะเก็บลงในหน่วยความจำได้หมดภายในครั้งเดียว
- จะใช้หน่วยความจำภายนอก เช่น ดิสก์, เทป สำหรับเก็บข้อมูลบางส่วนที่ได้รับการเรียงลำดับข้อมูลแล้ว แล้วจึงค่อยจัดการเรียงลำดับข้อมูลในส่วนต่อไป
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 ให้เรียงลำดับตามปกติ
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
- เริ่มพิจารณาจากหลักที่มีค่าน้อยที่สุดก่อน นั่นคือถ้าข้อมูลเป็นเลขจำนวนเต็มจะพิจารณาหลักหน่วยก่อน
- การจัดเรียงจะนำข้อมูลทีละตัว แล้วนำไปเก็บไว้ที่ซึ่งจัดไว้สำหรับค่านั้น เป็นกลุ่มๆ ตามลำดับการเข้ามา
- ในแต่ละรอบเมื่อจัดกลุ่มเรียบร้อยแล้ว ให้รวบรวมข้อมูลจากทุกกลุ่มเข้าด้วยกัน โดยเริ่มเรียงจากกลุ่มที่มีค่าน้อยทีสุดก่อนแล้วเรียงไปเรื่อยๆ จนหมดทุกกลุ่ม
- ในรอบต่อไปนำข้อมูลทั้งหมดที่ได้จัดเรียงในหลักหน่วยเรียบร้อยแล้วมาพิจารณาจัดเรียงในหลักสิบต่อไป ทำไปเรื่อยๆ จนกระทั่งครบทุกหลัก
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 ก็ จะยุติการทำงาน
ไม่มีความคิดเห็น:
แสดงความคิดเห็น