ทำความเข้าใจการเรียงลำดับการแทรกใน Ruby

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

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

ทำไมต้องแคร์

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

การนำเสนอด้วยภาพ

ก่อนที่เราจะเริ่มต้นเขียนโค้ด เราขอแนะนำให้คุณดูวิดีโอต่อไปนี้ มันอธิบายการจัดเรียงแบบแทรกโดยใช้การเต้น และโดยส่วนตัวแล้ว ฉันยังไม่พอ! :)

คำแนะนำทีละขั้นตอนของโค้ด

มาดูโค้ดกันเลย!

def insertion_sort(array)
    for i in 1...(array.length)  # Step 1
        j = i # Step 2
        while j > 0 # Step 3
            if array[j-1] > array[j] # Step 4
                temp = array[j]
                array[j] = array[j-1]
                array[j-1] = temp
            else
                break
            end
            j = j - 1 # Step 5
        end
    end
    return array
end

ขั้นตอนที่ 1:

เราเริ่มต้นด้วย for วงที่ตั้งค่าตัวแปร i เป็น 1 และเพิ่มขึ้นเรื่อย ๆ จนถึง i เท่ากับความยาวของอาร์เรย์ของเรา

ขั้นตอนที่ 2:

เราสร้างตัวแปรอื่น j และเริ่มต้นด้วยค่า 1 (เนื่องจากนั่นคือสิ่งที่ i คือ)

ขั้นตอนที่ 3:

ต่อไป เรามี while . ซ้อนกันอยู่ วนที่จะดำเนินต่อไปตราบเท่าที่ j มีค่ามากกว่าศูนย์ เนื่องจากเราเริ่มต้นด้วย j เท่ากับ 1 เรารู้ว่าการดำเนินการนี้จะดำเนินการอย่างน้อยหนึ่งครั้ง

ขั้นตอนที่ 4:

if... else บล็อกอาจจะดูน่ากลัวในตอนแรก แต่ไม่ต้องกังวล มันจะสมเหตุสมผลเมื่อเราเดินผ่านมันไป (และคุณสามารถทบทวนตัวอย่างการเต้นของ YouTube ได้เสมอ!)

สำหรับ if เงื่อนไขเราตรวจสอบว่า [j-1] มีค่ามากกว่า array[j] . ตั้งแต่ j ปัจจุบันคือ 1 เราจะเปรียบเทียบ array[0] ด้วย array[1] . เรื่องนี้สมเหตุสมผลเพราะเรากำลังเปรียบเทียบสององค์ประกอบแรกของอาร์เรย์

ถ้าองค์ประกอบแรก (array[0] ) ใหญ่กว่าอันถัดไป (array[1] ) แน่นอนว่าเราต้องสลับกัน ซึ่งเป็นสิ่งที่เกิดขึ้นภายใน if บล็อก. อย่างไรก็ตาม หากค่าใน array[0] น้อยกว่าค่าใน array[1] ดีมาก! เราไม่ต้องดำเนินการใดๆ เพราะมันได้จัดเรียงไว้แล้ว ดังนั้นเราจึงกด break ใน else บล็อก

ขั้นตอนที่ 5:

จากตรงนี้ เราลดค่า j . ตอนนี้เรากลับมาที่ for วนซ้ำ และ i ตอนนี้จะเป็น 2 . ลองนึกดูว่าเราจะเปรียบเทียบ array[1] . ได้อย่างไร ด้วย array[2] สำหรับการวนซ้ำครั้งแรกภายใน while วนซ้ำแล้วเราจะผ่าน while วนซ้ำอีกครั้งเพราะว่า j . ของเรา เริ่มที่ 2 เทียบกับ 1 .

ตัวอย่างที่มีข้อมูลจริง

มาดูโค้ดนี้กันโดยใช้อาร์เรย์ตัวอย่างต่อไปนี้ [5,7,2,10,9,12]

ในการทำซ้ำครั้งแรก เราจะเปรียบเทียบ 5 และ 7 . ตั้งแต่ 5 < 7 เราแยกส่วน if/else . ออกอย่างรวดเร็ว แล้วไปต่อ

ในการทำซ้ำครั้งต่อไป เราจะเปรียบเทียบ 7 และ 2 . ตอนนี้ ค่าเหล่านี้จะต้องสลับกัน ดังนั้นเราจะมี [5, 2, 7, 10, 9, 12] . จากนั้นเราจะสลับ 2 อีกครั้งกับ 5 ลงท้ายด้วย [2, 5, 7, 10, 9, 12] .

ในการทำซ้ำครั้งต่อไปภายใน for วนซ้ำ เราจะเปรียบเทียบ 10 และ 7 -- เย้! เรียบร้อยค่ะ

ต่อไปเราจะเปรียบเทียบ 10 และ 9 และพบว่าเราต้องแลก จากนั้น 7 น้อยกว่า 9 ดังนั้นเราจึงไม่ต้องทำการสลับอื่นใด ตอนนี้เหลือ [2, 5, 7, 9, 10, 12] .

การวนซ้ำครั้งสุดท้ายพบ 12 ซึ่งมากกว่า 10 ว้าว ว้าว! เสร็จเรียบร้อยและจัดเรียง

การวิเคราะห์ประสิทธิภาพ

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

หากจัดเรียงอาร์เรย์แล้ว รหัสการจัดเรียงการแทรกจะทำงานที่ O(n) เนื่องจากจะต้องวนซ้ำ n . เท่านั้น ครั้ง หากคุณต้องการรับสิ่งนี้ ให้เพิ่ม puts i ที่ด้านบนของเมธอดและรันโปรแกรมที่ส่งผ่านอาร์เรย์ที่จัดเรียงไว้แล้ว

หากอาร์เรย์มีการเรียงลำดับย้อนกลับ รหัสการจัดเรียงการแทรกจะทำงานที่ O(n^2) คุณอาจจะนึกภาพสิ่งนี้ในหัวของคุณได้ เนื่องจากจะต้องทำการสลับติดต่อกัน มันจะกด if เงื่อนไขสำหรับทุกองค์ประกอบเดียว อ๊ะ! อีกครั้ง อย่าลังเลที่จะลองใช้สิ่งนี้โดยส่งผ่านอาร์เรย์ที่เรียงลำดับย้อนกลับและสร้างตัวแปรตัวนับที่พิมพ์ออกมา

แม้ว่ากรณีที่เลวร้ายที่สุดคือ O(n^2) ซึ่งคุณอาจจำได้เหมือนกันสำหรับการเรียงลำดับแบบฟองและการเรียงลำดับการเลือก การเรียงลำดับการแทรกมักจะดีกว่า เนื่องจากอย่างที่เราได้เห็น กรณีที่ดีที่สุดอาจเป็น O(n) ในขณะที่กรณีที่ดีที่สุดสำหรับการเรียงลำดับการเลือกคือ O(n^2) . การเรียงลำดับการแทรกยังมีการสลับน้อยกว่าการเรียงลำดับแบบฟอง ดังนั้นมันจึงชนะการต่อสู้ครั้งนี้

สรุปผล

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