มันไม่ง่ายเลยที่จะเข้าใจ Sorting Algorithm ep.4

ความเดิมตอนที่แล้ว

มันไม่ง่ายเลยที่จะเข้าใจ Sorting Algorithm ep.3

จากตอนที่แล้วหลายแล้ว(แล้ว 100 ตัว) เราก็เริ่มเจออะไรเยอะขึ้นมาบ้าง ตอนนี้ก็จะเป็นเวลาที่จะต้องไปหาความท้าทายใหม่ที่รออยู่ข้างหน้า

นั่นคือ Merge sort นั่นเอง เจ้าตัวนี้มันเป็นจั่งไส กดปุ่ม spacebar 1ครั้งเพื่อรับชมครับ

Merge sort

เป็นวิธีการเรียงข้อมูล ที่เริ่มจะมีความโหดขึ้นมาหน่อยๆ ถือว่าเป็นจุดเริ่มต้นที่ดีในการลิ้มลองวิชา Algorithm ที่น่าทึ่งนี้ทีเดียว

Merge sort มีรูปแบบการเรียงนึกภาพออกได้ไม่ยากครับ ให้เราลองนึกถึง จอมมารบูจากการ์ตูนเรื่อง Dragon Ball Z ที่ไม่ว่าเราจะจัดการมันอย่างไร ก็ยังสามารถรวมร่างจากชิ้นส่วนเล็ก ๆ จนกลายมีสภาพหล่อเหมือนเดิมตลอด (แข็งแกร่งจริงๆ)

This is จอมมารบู จ้า

กลับมาเข้าเรื่องกันต่อ …

ก่อนที่เราจะไปต่อได้ ผมในฐานะผู้เขียนอยากให้ผู้ที่อ่านเข้าใจใน Recursive function เสียก่อน เพราะครั้งนี้เราจะใช้ Recursive function ในการแก้ปัญหาเจ้าตัวนี้กัน กดที่ลิ้งค์ด้านล่างได้เลยนะครับ

RECURSIVE FUNCTION ติดจรวด

เนื่องเจ้าตัว Merge sort มีความจำเป็นที่จะต้องแบ่งตัวของมันไปเรื่อยๆจนกว่าจะมีขนาดเล็กที่สุด ดังนั้นการใช้ loop ธรรมดาคงจะเป็นเรื่องที่น่าปวดหัวไม่น้อยเลย ในขณะที่ Recursive function สามารถวนใช้งานไปได้เรื่อย ๆ จนกว่าจะเจอจุดจบของมันได้อย่างไม่ยากเย็น

อาจจะมองภาพไม่ออก ไม่เป็นไรจะอธิบายให้ฟัง

ภาพมา!

เราจะใช้ชุดข้อมูลนี้กัน

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

ซึ่งจากข้างบน ผมก็ใบ้ไว้แล้วว่าการแยกนั้นจะทำได้แบบชิล ๆ ต้องใช้ Recursive function ดังนั้นจะขออธิบายให้เข้าใจได้ง่าย ๆ ด้วย Recursive starter kit ที่อยู่ในบทความที่ใส่ไว้ข้างต้นครับ

สุดยอดจริม ๆ

มาดูวิธีการแตกกันต่อ…

แตกยังไงให้คุ้มที่สุด?

สมมติว่าผมมีเลขในใจที่อยู่ในช่วง 1 -100 แล้วให้ผู้อ่านลองเดาเลขไปเรื่อย ๆ วิธีการเดาก็มีหลายแบบหลายวิธี แต่ถ้าอยากจะ play safe มากที่สุดเราก็คงจะเริ่มที่เลข 50 แล้วไล่ไปทีละครึ่งเรื่อย ๆ ใช่มั๊ยล่ะครับ

แนวทางเดียวกัน ในชุดข้อมูลที่มีอยู่จำนวนหนึ่ง การจะแบ่งข้อมูลให้มีจำนวนขั้นตอนน้อยที่สุดที่นิยมใช้กัน เรามักจะแบ่งทีละครึ่งของข้อมูล

ทีละครึ่งๆ

แต่ข้อมูลเป็นแถวๆแบบนี้มันจะแยกออกมาได้ยังไง?

เราก็แค่สมมติว่ามันแยกออกมาโดยการสร้างขอบเขตขึ้นมาเป็นตัวกำหนด ซึ่งมี 3 ตัว นั่นคือ left, middle, right นั่นเอง

3 มุมวาไรตี้

1.left index แทนเป็นขอบซ้ายหรือตัวแรกของชุดข้อมูล

2.right index แทนเป็นขอบขวาหรือตัวสุดท้ายของชุดข้อมูล

3.middle index จะได้มาจาก (left + right) /2 ซึ่งมีไว้ใช้แบ่งทีละครึ่งนั่นเอง

แล้วจะดูยังไงว่าเหลือตัวเดียวล่ะ?

เล็กเหมือนเกรดผู้เขียนเลย (ฮา)

ซึ่งตั้งแต่ที่บอกไปแล้วว่าเราคงจะแยกตรงๆไม่ได้ เราก็จะใช้ left กับ right มากำหนดด้วยโดยที่มันจะถือว่ามีกล่องเดียวก็ต่อเมื่อ left กับ right อยู่ที่เดียวกันนั่นเอง

same same

กลับมาที่ Recursive starter kit ของเรา…

ดังนั้นการสร้าง Merge_sort function จำเป็นต้องส่ง Arguement ไป 3 ตัวใหญ่ๆนั่นก็คือ

1. ชุดข้อมูล : ไม่ว่าจะเป็น array หรืออะไรก็ตามแต่
2. left index
3. right index

ส่วน middle index เราสามารถคำนวณจาก left กับ right ได้ ไม่มีปัญหา

จะได้ชื่อของมันเป็น merge_sort(int data[], int left, int right); มาใส่ในช่อง name ของ starter kit แล้ว!

ส่วน Next กับ Ending ของ Merge sort

เราจะมาดูส่วนของ Next กันก่อน

การที่ Next ยังทำงานอยู่ได้ จะหมายความว่ายังมีสมาชิกในข้อมูลมากกว่า 1 ตัวแน่ๆ ดังนั้นการที่มันจะทำงานภายใต้เงื่อนไขของ left < right

left น้อยกว่าจริงๆนะ

และการเรียกใช้ครั้งต่อไปหน้าตาจะออกมาประมาณนี้

เริ่มเห็นภาพรึยังครับ

การเขียน Recursive ต่อไปก็จะออกมาประมาณนี้้

merge_sort(int data[], int left, int mid);

และ

merge_sort(int data[], int mid+1, int right);

เราจะได้ Starter kit ออกมาแบบนี้

สุดยอด!

หากเขียนเป็น source code จะออกมาประมาณนี้

ถึงตอนนี้ก็เพียงพอต่อหัวที่กำลังค่อยๆรับความรู้ของพวกเราแล้ว

แต่เดี๋ยวก่อน! ยังไม่ได้ sort เลย

แล้วจะ sort อย่างไรใช้วิธีไหนลองอยากให้ทุกๆคนลองเดาก่อนที่จะดูตอนต่อไปนะครับ

สำหรับตอนนี้ขอจบเพียงเท่านี้ก่อนครับ

อ๊ากกกกกก