ทำความรู้จักกับ Insertion Sort ในภาษา ABAP

 

การจัดเรียงข้อมูล (Sorting) เป็นหนึ่งในกระบวนการพื้นฐานที่ใช้กันอย่างแพร่หลายในศาสตร์ด้านการประมวลผลข้อมูล ซึ่งการจัดเรียงข้อมูลช่วยให้เราสามารถค้นหาข้อมูลได้เร็วขึ้น ทำให้การทำงานต่างๆ เป็นระเบียบและมีประสิทธิภาพมากยิ่งขึ้น ในบทความนี้เราจะมาทำความรู้จักกับ “Insertion Sort” ซึ่งเป็นหนึ่งในอัลกอริธึมการจัดเรียงข้อมูลที่ง่ายและเข้าใจได้ไม่ยาก

 

Insertion Sort คืออะไร?

Insertion Sort เป็นอัลกอริธึมการจัดเรียงข้อมูลที่ทำงานโดยวิธีการแบ่งข้อมูลออกเป็นสองส่วน คือ ส่วนที่จัดเรียงแล้ว (Sorted) และส่วนที่ยังไม่ได้จัดเรียง (Unsorted) โดยจะนำข้อมูลจากส่วนที่ยังไม่ได้จัดเรียงมาเปรียบเทียบและแทรกเข้ากับข้อมูลที่จัดเรียงแล้วอย่างเหมาะสม อัลกอริธึมนี้ทำงานในลักษณะ “การเรียงเรียงข้อมูลแบบทีละหนึ่ง” ซึ่งมีความเหมาะสมในการใช้งานในกรณีที่ข้อมูลมีจำนวนน้อยหรือในกรณีที่ข้อมูลใกล้เคียงกันอยู่แล้ว

 

ขั้นตอนการทำงานของ Insertion Sort

1. เริ่มจากสมมุติว่าข้อมูลในอาเรย์มี N องค์กร

2. เทียบค่าข้อมูลจากตำแหน่งแรกของอาเรย์ พร้อมทั้งทำการตรวจสอบค่าการเรียงลำดับ

3. ถ้าค่าที่ต้องการแทรกเล็กกว่าค่าที่เร็วสุดในส่วนที่จัดเรียงแล้ว ก็ทำการแทรกค่าเข้าไปในตำแหน่งที่เหมาะสม

4. ทำซ้ำขั้นตอนที่ 2 จนกระทั่งข้อมูลทั้งหมดในอาเรย์เรียงลำดับเสร็จสิ้น

 

โค้ดตัวอย่าง Insertion Sort ในภาษา ABAP

เรามาดูตัวอย่างโค้ดการทำงานของ Insertion Sort ในภาษา ABAP กันเถอะค่ะ:

 DATA: lt_numbers TYPE TABLE OF i,
      lv_number  TYPE i,
      lv_index   TYPE i.

" ข้อมูลที่เราต้องการจัดเรียง
lt_numbers = VALUE #( 9 7 5 11 3 12 2 1 ).

" เริ่มทำการจัดเรียงข้อมูลด้วย Insertion Sort
LOOP AT lt_numbers INTO lv_number FROM 2.
  lv_index = sy-tabix - 1.

  WHILE lv_index > 0 AND lt_numbers[ lv_index ] > lv_number.
    " เลื่อนข้อมูลในส่วนที่จัดเรียง
    lt_numbers[ lv_index + 1 ] = lt_numbers[ lv_index ].
    lv_index = lv_index - 1.
  ENDWHILE.

  " แทรกค่าที่ต้องการลงในตำแหน่งที่ถูกต้อง
  lt_numbers[ lv_index + 1 ] = lv_number.
ENDLOOP.

" แสดงผลลัพธ์
LOOP AT lt_numbers INTO lv_number.
  WRITE: / lv_number.
ENDLOOP.

 

Use Case ของ Insertion Sort ในโลกจริง

Insertion Sort มีการใช้งานจริงในหลายกรณี ตัวอย่างคือ:

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

 

วิเคราะห์ Complexity ของ Insertion Sort

- Time Complexity:

- กรณีที่ดีที่สุด (Best Case): O(n) - เมื่อข้อมูลที่มีอยู่ถูกจัดเรียงแล้ว

- กรณีเฉลี่ย (Average Case): O(n^2)

- กรณีที่เลวร้ายที่สุด (Worst Case): O(n^2) - เมื่อข้อมูลเรียงในลำดับที่ตรงกันข้าม

- Space Complexity: O(1) สำหรับ Insertion Sort มีการใช้งานหน่วยความจำคงที่ ซึ่งหมายความว่าอัลกอริธึมนี้ไม่ต้องการพื้นที่เพิ่มในระหว่างการทำงาน

 

ข้อดีและข้อเสียของ Insertion Sort

ข้อดี

:

1. ง่ายต่อการเข้าใจและเขียนโค้ด

2. ใช้งานได้ดีในข้อมูลที่มีขนาดเล็ก

3. ทำการจัดเรียงแบบ in-place ไม่ต้องใช้หน่วยความจำเพิ่มเติม

ข้อเสีย

:

1. ประสิทธิภาพในการจัดเรียงไม่ดีเมื่อมีข้อมูลจำนวนมาก เพราะจะต้องมีการเปรียบเทียบและย้ายข้อมูลบ่อย ๆ

2. กรณีที่เลวร้ายที่สุดจะทำให้การทำงานช้าลง

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

 

 

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