หมายเหตุ: นี่คือส่วนที่ 4 ในซีรีส์ที่ดูการนำอัลกอริทึมการจัดเรียงต่างๆ มาใช้กับ Ruby ส่วนที่ 1 สำรวจ bubble sort ส่วนที่ 2 สำรวจ selection sort และส่วนที่ 3 สำรวจ merge sort
ขณะที่เราดำเนินต่อไปสำรวจวิธีการจัดเรียงข้อมูลที่แตกต่างกัน เราเลี้ยวไปสู่ insertion sort มีหลายเหตุผลที่จะชอบ insertion sort! ขั้นแรก insertion sort เป็น stable ซึ่งหมายความว่ามันไม่เปลี่ยนลำดับสัมพัทธ์ขององค์ประกอบที่มีคีย์เท่ากัน มันยังเป็น in-place algorithm อีกด้วย หมายความว่ามันไม่สร้างอาร์เรย์ใหม่เพื่อเก็บองค์ประกอบที่จัดเรียงแล้ว สุดท้าย insertion sort เป็นอัลกอริทึมที่ค่อนข้างง่ายในการนำไปใช้ ตามที่คุณจะเห็นเร็วๆ นี้!
ทำไมต้องสนใจ (Why Care)
ยากที่จะหลีกเลี่ยงการดูเหมือนเสียงแคนบนที่ขีดข่วน ที่นี่ แต่เหมือนที่เราอภิปรายในโพสต์ก่อนหน้าทั้งหมด การเข้าใจกลไกต่างๆ ในการจัดเรียงข้อมูลและ trade-offs ของแต่ละวิธีเป็นสิ่งสำคัญ ตัวอย่างเช่น แม้ insertion sort จะไม่ค่อยมีประโยชน์สำหรับชุดข้อมูลขนาดใหญ่ (เราจะสำรวจเพิ่มเติมด้านล่าง) มันสามารถทำได้ดีและมีประสิทธิภาพสำหรับชุดข้อมูลเล็กและชุดที่ใกล้เคียงกับการจัดเรียงแล้ว คุณจะเข้าใจว่าทำไมเมื่อเราเดินผ่านการนำไปใช้งาน แน่นอน คุณจะมักใช้เมธอด built-in ที่ภาษาโปรแกรมมิ่งที่คุณเลือกให้มาสำหรับการจัดเรียง แต่สิ่งนี้อาจปรากฏเป็นคำถามสัมภาษณ์ चाहेเป็น pair-program exercise หรืออาจเกี่ยวกับ time complexity โชคดีที่เมื่อเราเสร็จสิ้นโพสต์นี้ คุณจะสามารถเขียน insertion sort และเข้าใจ time complexity ได้อย่างง่ายดาย
การแสดงภาพ (A Visual Representation)
ก่อนที่เราจะเริ่มเขียนโค้ด ขอแนะนำให้ดูวิดีโอต่อไปนี้ มันอธิบาย insertion sort โดยใช้การเต้นรำ และส่วนตัวผมเพลิดเพลินกับมันมาก! :)
การเดินผ่านโค้ดทีละขั้นตอน (Step-by-Step Walk-Through of the Code)
มาดูโค้ดกัน!
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 คือ 1)
ขั้นตอนที่ 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] แล้วเยี่ยม! เราไม่ต้องทำอะไรเพราะมันจัดเรียงแล้ว ดังนั้นเราแค่ hit break ในบล็อก else
ขั้นตอนที่ 5:
จากที่นี่ เราลดค่า j ลง ตอนนี้ เรากลับไปที่ลูป for และ i จะเป็น 2 ตอนนี้ คุณจินตนาการได้ว่าเราจะเปรียบเทียบ array[1] กับ array[2] สำหรับ iteration แรกภายในลูป while และจากนั้นเราจะผ่านลูป while อีกครั้ง เพราะ j เริ่มที่ 2 แทนที่จะเป็น 1
ตัวอย่างกับข้อมูลจริง (Example with Real Data)
มาเดินผ่านโค้ดนี้ด้วยอาร์เรย์ตัวอย่างต่อไปนี้: [5,7,2,10,9,12]
ใน iteration แรก เราจะเปรียบเทียบ 5 และ 7 เนื่องจาก 5 < 7 เรา break ออกจาก if/else อย่างรวดเร็วและไปต่อ
ใน iteration ถัดไป เราเปรียบเทียบ 7 และ 2 ตอนนี้ ค่าเหล่านี้จะต้องสลับ ดังนั้นเราจะได้ [5, 2, 7, 10, 9, 12] จากนั้น เราจะสลับ 2 อีกครั้งกับ 5 เพื่อได้ [2, 5, 7, 10, 9, 12]
ใน iteration ถัดไปภายในลูป for เราจะเปรียบเทียบ 10 และ 7 -- ยินดีด้วย! พวกมันเรียงลำดับแล้ว
ไปต่อ เราเปรียบเทียบ 10 และ 9 และพบว่าต้องสลับ แล้ว 7 น้อยกว่า 9 ดังนั้นเราจะไม่ต้องสลับเพิ่มเติม เราตอนนี้เหลือ [2, 5, 7, 9, 10, 12]
Iteration สุดท้ายพบ 12 ซึ่งมากกว่า 10 ดังนั้น โวอิลา! เราเสร็จและจัดเรียงแล้ว
การวิเคราะห์ประสิทธิภาพ (Performance Analysis)
แม้บางอัลกอริทึมการจัดเรียงที่เราดู เช่น bubble sort จะถูกนำไปใช้จริงนادرมาก แต่ insertion sort สามารถเป็นคำตอบที่สมเหตุสมผลได้ จินตนาการว่าถ้าอาร์เรย์ของเราจัดเรียงแล้ว -- insertion sort จะรันได้อย่างรวดเร็วและมีประสิทธิภาพ ในด้านตรงข้าม จะเกิดอะไรขึ้นถ้าเราต้องจัดเรียงอาร์เรย์ที่เรียงลำดับย้อนกลับ นั่นจะเป็นสถานการณ์วิกฤตสำหรับ insertion sort
หากอาร์เรย์จัดเรียงแล้ว โค้ด insertion sort จะรันที่ O(n) เนื่องจากมันจะต้องลูปผ่านแค่ n ครั้ง หากคุณต้องการยืนยัน ให้เพิ่ม puts i ที่ด้านบนของเมธอดและรันโปรแกรมโดยส่งอาร์เรย์ที่จัดเรียงแล้วเข้าไป
หากอาร์เรย์จัดเรียงย้อนกลับ โค้ด insertion sort จะรันที่ O(n^2) คุณอาจจินตนาการได้ในหัว เนื่องจากมันจะต้องทำการสลับติดต่อกัน มันจะ hit เงื่อนไข if สำหรับทุกองค์ประกอบเดี่ยว ยิกส์! อีกครั้ง รู้สึกสบายๆ ลองส่งอาร์เรย์ที่จัดเรียงย้อนกลับเข้าไปและสร้างตัวแปรนับที่พิมพ์ออกมา
แม้ worst case จะเป็น O(n^2) ซึ่ง คุณอาจจำได้ เหมือนกับ bubble sort และ selection sort insertion sort มักจะเหมาะกว่า เนื่องจาก ตามที่เราเห็น best case อาจเป็น O(n) ในขณะที่ best case สำหรับ selection sort คือ O(n^2) Insertion sort ยังมีการสลับน้อยกว่า bubble sort ดังนั้นจึงชนะในการต่อสู้นี้
สรุป (Wrap Up)
หวังว่าโพสต์นี้จะมีประโยชน์และคุณรู้สึกมั่นใจเกี่ยวกับการเข้าใจข้อดีและข้อเสียของ insertion sort รวมถึงการทำงานของอัลกอริทึม หากคุณยังต้องการเพิ่มเติม ขอแนะนำให้ดูหน้า Wikipedia ของ insertion sort
