สำรวจ Merge Sort กับ Ruby

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

ดังที่เราได้พูดคุยกันในโพสต์ก่อนหน้านี้ในชุดนี้ การทำความเข้าใจวิธีการจัดเรียงข้อมูลเป็นส่วนสำคัญของชุดเครื่องมือของวิศวกรซอฟต์แวร์ โชคดีที่ภาษาระดับสูงส่วนใหญ่ เช่น Ruby มีเมธอดในตัวที่มีประสิทธิภาพในการจัดเรียงอาร์เรย์ ตัวอย่างเช่น เมื่อคุณเรียก .sort ในอาร์เรย์ คุณกำลังใช้การเรียงลำดับอย่างรวดเร็วภายใต้ประทุน ในบทความนี้ เราจะมาเรียนรู้อัลกอริทึมที่คล้ายคลึงกันในการเรียงลำดับอย่างรวดเร็ว -- การเรียงลำดับแบบผสาน อัลกอริธึมทั้งสองนี้ใช้ "วิธีการแบ่งและพิชิต" การเรียงลำดับแบบผสานถูกคิดค้นโดย John von Neumann ในปี 1945 Von Neumann เป็นนักวิทยาศาสตร์คอมพิวเตอร์และนักฟิสิกส์ที่มีชื่อเสียงซึ่งเป็นที่รู้จักจากการทำงานในโครงการแมนฮัตตัน ทฤษฎีบท "mini-max" วิธี Monte Carlo และอื่นๆ

ในระดับสูง อัลกอริธึมการเรียงลำดับการผสานจะแยกอาร์เรย์ออกเป็นสองอาร์เรย์ย่อยครั้งแล้วครั้งเล่า (โดยใช้การเรียกซ้ำ) จนกว่าจะเหลือเพียงองค์ประกอบเดียว จากนั้นองค์ประกอบจะถูก "รวม" กลับเข้าด้วยกันเพื่อสร้างอาร์เรย์ที่เรียงลำดับขั้นสุดท้าย แตกต่างจากการเรียงลำดับแบบฟองและอัลกอริธึมอื่นที่คล้ายคลึงกัน การเรียงลำดับการผสานเป็นเรื่องยากที่จะเข้าใจหากไม่มีการแสดงภาพ ไดอะแกรมต่อไปนี้เป็นภาพประกอบทีละขั้นตอนจาก Wikipedia ที่แสดงให้เห็นว่าการเรียงลำดับการผสานทำงานอย่างไร อย่างไรก็ตาม อย่ากังวลหากคุณยังคลุมเครือเล็กน้อยเกี่ยวกับสิ่งที่เกิดขึ้น เราจะดำเนินการผ่านโค้ดต่อไป

ต่างจากอัลกอริธึมที่เราได้พูดคุยกันก่อนหน้านี้ (เช่น บับเบิลและการเลือก) ซึ่งโดยพื้นฐานแล้วไม่สามารถทำได้สำหรับงานจริงใดๆ การเรียงลำดับการผสานทำงานได้ดีกว่ามากในแง่ของสัญกรณ์ Big-O หากคุณไม่คุ้นเคยกับสัญลักษณ์ Big-O แสดงว่ามีประสิทธิภาพในกรณีที่แย่ที่สุดของอัลกอริทึมต่างๆ ซึ่งช่วยให้เราสามารถเปรียบเทียบอัลกอริทึมตาม Big-O ได้อย่างง่ายดาย ตัวอย่างเช่น อัลกอริธึมที่มี Big-O ของ O(1) หมายความว่ารันไทม์กรณีที่เลวร้ายที่สุดจะคงที่เมื่อจำนวนขององค์ประกอบ "n" เพิ่มขึ้น ในขณะที่อัลกอริทึมที่มีสัญลักษณ์ Big-O ของ O( n) หมายความว่ารันไทม์กรณีที่แย่ที่สุดเพิ่มขึ้นเป็นเส้นตรงเมื่อ n เพิ่มขึ้น ซึ่งหมายความว่าถ้าคุณมีอาร์เรย์ที่มี 100 องค์ประกอบและต้องเลือกระหว่างอัลกอริธึมการจัดเรียงที่เป็น O(n) และ O(1) คุณจะเลือกอัลกอริทึม O(1) เพราะ O(1) ชนะ O(100) แน่นอน อัลกอริธึมการเรียงลำดับแบบฟองและการเลือกทั้งคู่มีตัวพิมพ์ใหญ่ที่สุดของ O(n^2) สิ่งนี้ไม่มีประโยชน์มากเพราะหมายความว่าอัลกอริทึมจะทำงานช้ามากเมื่อจำนวนองค์ประกอบเพิ่มขึ้น ในทางตรงกันข้าม การเรียงลำดับการผสานจะทำงานที่ n log(n) ซึ่งหมายความว่าอัลกอริทึมจะไม่ลดทอนประสิทธิภาพมากเท่ากับฟองสบู่หรือการเรียงลำดับการเลือก

มาดูตัวอย่างในแผนภาพกัน เราเริ่มต้นด้วยอาร์เรย์ของ [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] และ 48 และ 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] .

การนำทับทิมไปใช้

ต่อไปนี้คืออัลกอริธึมการจัดเรียงแบบผสานที่เขียนด้วย 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

ยอดเยี่ยม! รหัสของเราได้นำอาร์เรย์เริ่มต้นของเรามาแบ่งครึ่ง มาดู 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

อันดับแรก เราตรวจสอบว่าอาร์เรย์ย่อยใดอาร์เรย์หนึ่งว่างหรือไม่ ถ้าเป็นเช่นนั้น เราสามารถส่งคืนอีกอันหนึ่งได้ มิฉะนั้น เนื่องจากอาร์เรย์ย่อยทั้งสองไม่ว่างเปล่า เราจึงเปรียบเทียบค่าขององค์ประกอบแรกของแต่ละอาร์เรย์ จากนั้นจึงเปลี่ยนค่าที่เปรียบเทียบเพื่อป้องกันการสร้างการวนซ้ำแบบอนันต์ ต่อไป เราใช้การเรียกซ้ำ (เพิ่มเติมในวินาทีนั้น!) ในอาร์เรย์ดั้งเดิม จนกว่าเราจะสามารถเชื่อมต่ออาร์เรย์ทั้งสองเข้าด้วยกันในที่สุด จัดเรียงอย่างดี

เพิ่มเติมอีกเล็กน้อยเกี่ยวกับการเรียกซ้ำ

หากมีบางอย่างที่ดูแปลกในโค้ดของเรา ฉันเดาว่ามันคือบรรทัดนี้:recursive = merge(left_array, right_array) เรากำลังเรียก merge วิธีการจาก ภายในตัวมันเอง . โว้ว! นี่คือสิ่งที่เราเรียกว่าการเรียกซ้ำ ซึ่งเป็นเทคนิคที่ฟังก์ชันเรียกตัวเองอย่างน้อยหนึ่งครั้งจนกว่าจะตรงตามเงื่อนไขที่ระบุ ในกรณีของเรา merge จะถูกเรียกต่อไปจนกว่าอาร์เรย์ด้านซ้ายหรือด้านขวาจะว่างเปล่า หากคุณสนใจที่จะเรียนรู้เพิ่มเติมเกี่ยวกับการเรียกซ้ำ นี่คือตัวอย่างที่อธิบายการใช้ Ruby และการเรียกซ้ำเพื่อเขียนฟังก์ชันสำหรับลำดับ Fibonacci

สรุป

ฉันหวังว่าคุณจะสนุกกับการเรียนรู้เพิ่มเติมเกี่ยวกับการเรียงลำดับการผสาน! การทำความเข้าใจวิธีการทำงานในระดับสูง ตลอดจนเหตุผลที่ว่าทำไมจึงเป็นทางเลือกที่มีประสิทธิภาพมากกว่าแบบฟองสบู่หรือการเรียงลำดับการเลือกมักจะมีประโยชน์ในการสัมภาษณ์งานหรืองานประจำวันของคุณ นอกจากนี้ยังมีรูปแบบการจัดเรียงการผสานจำนวนหนึ่งที่คุณสามารถอ่านเพิ่มเติมเกี่ยวกับมันใน Wikipedia หากคุณสนใจ เจอกันใหม่คราวหน้า ... เรียงลำดับความสุข!