บทความนี้เป็นส่วนที่ 3 ในชุดบทความที่สำรวจการนำอัลกอริทึมการจัดเรียงต่างๆ ไปใช้กับ Ruby ส่วนที่ 1 สำรวจ Bubble Sort และส่วนที่ 2 สำรวจ Selection Sort
ตามที่เราได้พูดคุยกันในบทความก่อนหน้านี้ของชุดนี้ การเข้าใจวิธีการจัดเรียงข้อมูลเป็นส่วนสำคัญในชุดเครื่องมือของวิศวกรซอฟต์แวร์ทุกคน โชคดีที่ภาษาระดับสูงส่วนใหญ่ เช่น Ruby มีเมธอดสำเร็จรูปที่มีประสิทธิภาพในการจัดเรียงอาร์เรย์อยู่แล้ว ตัวอย่างเช่น เมื่อคุณเรียก .sort บนอาร์เรย์ คุณก็กำลังใช้ Quicksort ภายใต้ฮู้ด ในบทความนี้เราจะเรียนรู้อัลกอริทึมที่คล้ายกับ Quick Sort คือ Merge Sort ทั้งสองอัลกอริทึมใช้แนวทาง "แบ่งและเอาชนะ" (Divide and Conquer) Merge Sort ถูกสร้างขึ้นโดย John von Neumann ในปี 1945 von Neumann เป็นนักวิทยาศาสตร์คอมพิวเตอร์และนักฟิสิกส์ที่มีชื่อเสียง ยังเป็นที่รู้จักจากงานในโครงการ Manhattan ทฤษฎี "Mini-max" วิธี Monte Carlo และอื่นๆ อีกมากมาย
ในภาพรวม อัลกอริทึม Merge Sort จะแบ่งอาร์เรย์ออกเป็นสองซับอาร์เรย์ซ้ำๆ (โดยใช้ Recursion) จนเหลือเพียงองค์ประกอบเดียว จากนั้นองค์ประกอบเหล่านี้จะถูก "รวม" (Merge) กลับเข้าด้วยกันเพื่อสร้างอาร์เรย์ที่จัดเรียงแล้วสุดท้าย ไม่เหมือน Bubble Sort และอัลกอริทึมที่คล้ายกัน Merge Sort ยากต่อการเข้าใจหากไม่มีการจินตนาการ ภาพประกอบต่อไปนี้เป็นภาพประกอบทีละขั้นตอนจาก Wikipedia ที่แสดงให้เห็นถึงการทำงานของ Merge Sort อย่างไรก็ตาม อย่ากลัวหากคุณยังงงอยู่เล็กน้อย เราจะเดินทางผ่านโค้ดต่อไป
ไม่เหมือนกับอัลกอริทึมที่เราพูดคุยกันมาก่อนหน้านี้ (เช่น Bubble และ Selection) ซึ่งเป็นพื้นฐานไม่ค่อยเหมาะสมสำหรับงานจริง Merge Sort ให้ประสิทธิภาพที่ดีกว่ามากในแง่ของ Big-O Notation หากคุณไม่คุ้นเคยกับ Big-O Notation มันแสดงถึงประสิทธิภาพสถานการณ์แย่ที่สุดของอัลกอริทึมต่างๆ ซึ่งทำให้เราเปรียบเทียบอัลกอริทึมได้ง่ายขึ้นจาก Big-O ของมัน ตัวอย่างเช่น อัลกอริทึมที่มี Big-O เป็น O(1) หมายความว่าเวลารันสถานการณ์แย่ที่สุดคงที่เมื่อจำนวนองค์ประกอบ "n" เพิ่มขึ้น ในขณะที่อัลกอริทึมที่มี Big-O เป็น O(n) หมายความว่าเวลารันสถานการณ์แย่ที่สุดเพิ่มขึ้นแบบเส้นตรงเมื่อ n เพิ่มขึ้น หมายความว่าหากคุณมีอาร์เรย์ 100 องค์ประกอบและต้องเลือกระหว่างอัลกอริทึมจัดเรียงที่เป็น O(n) และ O(1) คุณจะเลือก O(1) เพราะ O(1) ชนะ O(100) แน่นอน อัลกอริทึม Bubble และ Selection Sort ทั้งคู่มีสถานการณ์แย่ที่สุดเป็น O(n^2) นี่ไม่ค่อยมีประโยชน์เพราะหมายถึงอัลกอริทึมจะทำงานช้ามากเมื่อจำนวนองค์ประกอบเพิ่มขึ้น ในทางตรงข้าม Merge Sort ให้ประสิทธิภาพที่ n log(n) ซึ่งหมายถึงอัลกอริทึมจะไม่เสียประสิทธิภาพเท่า Bubble หรือ Selection Sort
มาเดินทางผ่านตัวอย่างในภาพประกอบกัน เราเริ่มต้นด้วยอาร์เรย์ [38, 27, 43, 3, 9, 82, 10] จากนั้นแบ่งอาร์เรย์ครึ่งซ้ำๆ จนเหลือองค์ประกอบเดี่ยว
- เราแบ่งอาร์เรย์เริ่มต้นออกเป็นสองครึ่ง:
[38, 27, 43, 3]และ[9, 82, 10] - เราแบ่งครึ่งแรกอีกครั้ง:
[38, 27]และ[43, 3] - เราแบ่งครึ่งแรกเป็นองค์ประกอบเดี่ยว:
[38],[27],[43], และ[3] - เราจัดเรียง 38 และ 27 ให้เป็น
[27, 38]และ 43 และ 3 ให้เป็น[3, 43] - นำมารวมกัน เราได้
[3, 27, 38, 43] - ตอนนี้เราย้ายไปครึ่งที่สองของอาร์เรย์เดิมซึ่งเป็น
[9, 82, 10]เราแบ่งครึ่งได้[9, 82]และ[10] - เราแบ่ง
[9, 82]เป็น[9]และ[82]และมี[10]ซึ่งเป็นองค์ประกอบเดี่ยวอยู่แล้ว - เราจัดเรียง
[9, 82]กลับเข้าด้วยกันแล้วรวม[10]กลับเข้าไป ทำให้ได้[9, 10, 82] - สุดท้ายเรารวม
[3, 27, 38, 43]และ[9, 10, 82]ได้[3, 9, 10, 27, 38, 43, 82]
การนำ Merge Sort ไปใช้กับ Ruby
ต่อไปนี้คืออัลกอริทึม Merge Sort ที่เขียนด้วย Ruby:
class MergeSort def sort(numbers) num_elements = numbers.length if num_elements <= 1 return numbers end half_of_elements = (num_elements / 2).round left = numbers.take(half_of_elements) right = numbers.drop(half_of_elements) sorted_left = sort(left) sorted_right = sort(right) merge(sorted_left, sorted_right) end def merge(left_array, right_array) if right_array.empty? return left_array end if left_array.empty? return right_array end smallest_number = if left_array.first <= right_array.first left_array.shift else right_array.shift end recursive = merge(left_array, right_array) [smallest_number].concat(recursive) end end มาเดินทางดูว่ากำลังเกิดอะไรขึ้นที่นี่กัน แรกเราจะเน้นที่เมธอด sort ด้านบน
def sort(numbers) num_elements = numbers.length if num_elements <= 1 return numbers end half_of_elements = (num_elements / 2).round left = numbers.take(half_of_elements) right = numbers.drop(half_of_elements) sorted_left = sort(left) sorted_right = sort(right) merge(sorted_left, sorted_right) end เป้าหมายของส่วนโค้ดนี้คือแบ่งตัวเลขที่กำหนดครึ่งซ้ำๆ จนเหลือเพียงรายการเดียวในแต่ละอัน หากต้องการดูการทำงาน ให้คอมเมนต์บรรทัดสุดท้าย (merge(sorted_left, sorted_right)) และแทนที่ด้วยการพิมพ์ sorted_left และ sorted_right การรันโปรแกรมโดยส่งอาร์เรย์ตัวอย่างของเรา คุณควรเห็นสิ่งนี้ในเทอร์มินัลของคุณ:
merge_sort = MergeSort.new puts merge_sort.sort([38, 27, 43, 3, 9, 82, 10]) ruby ruby-merge-sort.rb
27 43 38 3 9 82 10 ยอดเยี่ยม! โค้ดของเราได้รับอาร์เรย์เริ่มต้นและแบ่งครึ่งแล้ว มาดูส่วน merge ของโค้ดต่อไป
def merge(left_array, right_array) if right_array.empty? return left_array end if left_array.empty? return right_array end smallest_number = if left_array.first <= right_array.first left_array.shift else right_array.shift end recursive = merge(left_array, right_array) [smallest_number].concat(recursive) end แรกเราตรวจสอบว่าซับอาร์เรย์ใดซับอาร์เรย์หนึ่งว่างหรือไม่ หากใช่ เราสามารถคืนค่าอีกอันได้เลย มิฉะนั้น ถ้าทั้งสองซับอาร์เรย์ไม่ว่าง เราเปรียบเทียบค่าขององค์ประกอบแรกของแต่ละอาร์เรย์ จากนั้น shift ค่าที่เปรียบเทียบเพื่อป้องกันการสร้าง Infinite Loop ต่อไปเราใช้ Recursion (รายละเอียดเพิ่มเติมในส่วหนี้!) บนอาร์เรย์เดิมจนกว่าจะสามารถเชื่อมต่อสองอาร์เรย์เข้าด้วยกันได้อย่างสวยงามและจัดเรียงแล้ว
เพิ่มเติมเกี่ยวกับ Recursion
หากมีสิ่งที่ดูแปลกในโค้ดของเรา คาดเดาว่าคือบรรทัดนี้: recursive = merge(left_array, right_array) เรากำลังเรียกเมธอด merge จากภายในตัวมันเอง ว้าว! นี่คือสิ่งที่เราเรียกว่า Recursion — เทคนิคที่ฟังก์ชันเรียกตัวมันเองหนึ่งครั้งหรือหลายครั้งจนกว่าเงื่อนไขที่ระบุจะถูกตอบสนอง ในกรณีของเรา merge จะถูกเรียกซ้ำจนกว่าอาร์เรย์ซ้ายหรือขวาจะว่าง หากคุณสนใจเรียนรู้เพิ่มเติมเกี่ยวกับ Recursion นี่คือตัวอย่างที่เดินทางผ่านการใช้ Ruby และ Recursion เพื่อเขียนฟังก์ชันสำหรับลำดับฟีโบนัชชี
สรุป
หวังว่าคุณจะเพลิดเพลินกับการเรียนรู้เพิ่มเติมเกี่ยวกับ Merge Sort! การเข้าใจวิธีการทำงานในระดับภาพรวม รวมถึงเหตุผลที่มันเป็นตัวเลือกที่มีประสิทธิภาพกว่า Bubble หรือ Selection Sort อาจจะเป็นประโยชน์ในงานสัมภาษณ์หรืองานประจำวันของคุณ อีกทั้งยังมีรูปแบบต่างๆ ของ Merge Sort หลายแบบที่คุณสามารถอ่านเพิ่มเติมได้ที่ Wikipedia หากสนใจ จนกว่าจะพบกันใหม่ ... Happy Sorting!
