Insertion Sort: การจัดเรียงข้อมูลด้วยวิธีเรียบง่ายในภาษา Ruby

 

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

 

อะไรคือ Insertion Sort?

Insertion Sort เป็นอัลกอริธึมการจัดเรียงที่ทำงานโดยการแบ่งข้อมูลออกเป็นสองส่วน คือ ส่วนที่จัดเรียงแล้วและส่วนที่ยังไม่จัดเรียง อัลกอริธึมจะทำการเลือกแต่ละค่าจากส่วนที่ยังไม่จัดเรียงและแทรกเข้าไปในตำแหน่งที่ถูกต้องในส่วนที่จัดเรียงอยู่ จากนั้นจะทำซ้ำขั้นตอนนี้จนกว่าทุกข้อมูลจะถูกจัดเรียง

การทำงานของ Insertion Sort

1. เริ่มจากข้อมูลในรายการ โดยถือว่าสายแรกเป็นส่วนที่จัดเรียง

2. เลือกค่าถัดไปในข้อมูลที่ยังไม่จัดเรียง

3. เปรียบเทียบค่านั้นกับค่าที่ในส่วนที่จัดเรียง

4. แทรกค่านั้นในตำแหน่งที่เหมาะสม

5. ทำซ้ำจนกว่าข้อมูลทั้งหมดจะถูกจัดเรียง

 

ตัวอย่าง Code ในภาษา Ruby

ในการดูภาพรวม เรามาดูตัวอย่างโค้ดของ Insertion Sort ในภาษา Ruby กันดีกว่า:

 def insertion_sort(array)
  (1...array.length).each do |i|
    key = array[i]
    j = i - 1

    # ขยับค่าไปยังตำแหน่งที่ถูกต้อง
    while j >= 0 && array[j] > key
      array[j + 1] = array[j]
      j -= 1
    end
    array[j + 1] = key
  end
  array
end

# ทดสอบฟังก์ชัน
numbers = [5, 2, 9, 1, 5, 6]
sorted_numbers = insertion_sort(numbers)
puts "Sorted array: #{sorted_numbers}"

เมื่อเราทำการทดสอบโค้ดนี้ เราจะได้ผลลัพธ์ว่า "Sorted array: [1, 2, 5, 5, 6, 9]". โค้ดส่วนนี้อธิบายว่าเราจะเริ่มที่อาร์เรย์ที่ไม่เรียงลำดับ จากนั้นใช้ Insertion Sort ในการจัดเรียงข้อมูลให้เรียบร้อย

 

Usecase ในโลกจริง

Insertion Sort ประยุกต์ใช้งานได้ในหลายสถานการณ์ ตัวอย่างเช่น:

1. ข้อมูลขนาดเล็ก: เมื่อเรามีข้อมูลที่มีขนาดเล็ก เช่น การจัดเรียงรายการสินค้าห้าชนิด การใช้ Insertion Sort จะเป็นทางเลือกที่ดี เพราะมันทำงานได้เร็วและมีนักพัฒนาโปรแกรมที่คุ้นเคย 2. ข้อมูลที่เกือบจะเรียงลำดับ: หากข้อมูลเกือบจะเรียงลำดับอยู่แล้ว Insertion Sort จะทำงานได้เร็วมาก เพราะต้องเปรียบเทียบเพียงไม่กี่ค่าก็จะสามารถจัดเรียงได้

 

วิเคราะห์ Complexity

การวิเคราะห์ความซับซ้อนของ Insertion Sort ถือเป็นสิ่งสำคัญเวลาเลือกใช้อัลกอริธึม ข้างล่างนี้เป็นการวิเคราะห์ complexity:

- เวลาที่ดีที่สุด (Best Case): O(n) - เมื่อข้อมูลถูกจัดเรียงเรียบร้อยแล้ว - เวลาปกติ (Average Case): O(n^2) - ในกรณีทั่วไป - เวลาที่แย่ที่สุด (Worst Case): O(n^2) - เมื่อข้อมูลเรียงในทางตรงข้าม เช่น [9, 8, 7, 6,...,1] - อวกาศ (Space Complexity): O(1) - เนื่องจาก Insertion Sort ใช้หน่วยความจำเพียงพอเท่ากับอาร์เรย์ที่เราจะจัดเรียงอยู่

 

ข้อดีข้อเสียของ Insertion Sort

ข้อดี:

1. เรียบง่าย: Insertion Sort เข้าใจง่ายและเขียนโค้ดได้ไม่ยุ่งยาก 2. เร็วในข้อมูลขนาดเล็ก: มีความเร็วมากกว่าการใช้ Quick Sort หรือ Merge Sort ในกรณีที่มีข้อมูลขนาดเล็ก 3. มีการเปลี่ยนแปลงน้อย: สามารถทำงานในสถานการณ์ที่ข้อมูลเกือบจะเรียงอยู่แล้วได้อย่างรวดเร็ว

ข้อเสีย:

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

 

สSummary

Insertion Sort เป็นอัลกอริธึมการจัดเรียงที่ง่ายที่สุดและเรียนรู้ได้ไม่ยาก แม้ว่าจะไม่เหมาะสมสำหรับข้อมูลขนาดใหญ่ แต่ก็ยังคงมีประโยชน์ในโอกาสบางอย่าง หากคุณต้องการเรียนรู้เกี่ยวกับการจัดเรียงและอัลกอริธึมที่เกี่ยวข้องมากขึ้น เราขอเชิญชวนคุณมาศึกษาเพิ่มเติมที่ EPT (Expert-Programming-Tutor) เพราะที่นี่มีโปรแกรมการเรียนการสอนที่มีประสิทธิภาพ คุ้มค่า และเหมาะสมสำหรับนักเรียนทุกระดับ อย่ารอช้า มาเริ่มต้นการเขียนโปรแกรมที่ EPT กันเถอะ!

 

 

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