Insertion Sort: การเลือกใช้ Algorithm เพื่อจัดเรียงข้อมูลใน COBOL

 

 

แนะนำตัว Algorithm Insertion Sort

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

การทำงานของ Insertion Sort สามารถสรุปได้ในขั้นตอนหัวใจหลักเหล่านี้:

1. เริ่มต้นจากข้อมูลชุดแรกที่ถือว่าเรียงแล้ว

2. เปรียบเทียบข้อมูลถัดไปและนำไปเพิ่มในลำดับที่ถูกต้อง โดยทำการเลื่อนค่าต่างๆ ที่มีค่ามากกว่าออกไป

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

Use Case ของ Insertion Sort

Insertion Sort ถูกนำมาใช้ในหลายสถานการณ์ โดยเฉพาะเมื่อจำนวนข้อมูลมีจำนวนน้อย หรือในกรณีที่ข้อมูลมีการจัดเรียงในลำดับคร่าวๆ อยู่แล้ว อาทิเช่น การจัดเรียงข้อมูลในฟอร์มออนไลน์ที่มีการรับข้อมูลแบบ множинаที่มีไม่มากนัก Inclusion Sort จึงเหมาะกับการจัดระเบียบข้อมูลในสถานการณ์เหล่านี้

 

ตัวอย่าง Code ภาษา COBOL

มาดูกันที่ตัวอย่างโค้ดที่แสดงการใช้ Insertion Sort ในภาษา COBOL:

        IDENTIFICATION DIVISION.
       PROGRAM-ID. InsertionSort.
       ENVIRONMENT DIVISION.
       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01  NUMBERS   PIC 9(5) OCCURS 10.
       01  I         PIC 9.
       01  J         PIC 9.
       01  TEMP      PIC 9(5).
       01  COUNT     PIC 9(2) VALUE 10.

       PROCEDURE DIVISION.
           MOVE 5 TO NUMBERS(1)
           MOVE 2 TO NUMBERS(2)
           MOVE 9 TO NUMBERS(3)
           MOVE 1 TO NUMBERS(4)
           MOVE 4 TO NUMBERS(5)
           MOVE 7 TO NUMBERS(6)
           MOVE 6 TO NUMBERS(7)
           MOVE 3 TO NUMBERS(8)
           MOVE 10 TO NUMBERS(9)
           MOVE 8 TO NUMBERS(10)

           PERFORM VARYING I FROM 2 BY 1 UNTIL I > COUNT
               MOVE NUMBERS(I) TO TEMP
               MOVE I TO J
               PERFORM UNTIL J = 1 OR NUMBERS(J-1) <= TEMP
                   MOVE NUMBERS(J-1) TO NUMBERS(J)
                   SUBTRACT 1 FROM J
               END-PERFORM
               MOVE TEMP TO NUMBERS(J)
           END-PERFORM.

           DISPLAY "Sorted Numbers:".
           PERFORM VARYING I FROM 1 BY 1 UNTIL I > COUNT
               DISPLAY NUMBERS(I)
           END-PERFORM.

           STOP RUN.

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

 

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

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

- เวลาที่ดีที่สุด (Best Case): O(n) ค่าจะเกิดขึ้นเมื่อข้อมูลเรียงอยู่แล้ว - เวลาเฉลี่ย (Average Case): O(n²) ในกรณีทั่วไป - เวลาที่เลวร้ายที่สุด (Worst Case): O(n²) เมื่อข้อมูลอยู่ในลำดับที่เรียงไม่ดีสุดๆ

ในทางปฏิบัติ Insertion Sort มักจะทำงานได้ดีเมื่อข้อมูลมีลำดับที่อยู่ในตำแหน่งค่อนข้างดีอยู่แล้ว

 

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

ข้อดี

1. ความง่าย: เข้าใจหลักการทำงานได้ง่าย 2. ประสิทธิภาพ: มีประสิทธิภาพในข้อมูลขนาดเล็กหรือเกือบเรียงลำดับ 3. ไม่ใช้พื้นที่มาก: ทำงานโดยไม่ต้องใช้พื้นที่เพิ่มเติม ซึ่งทำให้ประหยัดหน่วยความจำได้ดี 4. Stable Sort: เก็บตำแหน่งของค่าสำหรับค่าเดิมได้ ทำให้ไม่สูญเสียข้อมูล

ข้อเสีย

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

 

สรุป

ด้วยความเรียบง่ายและฟังก์ชันของ Insertion Sort ถึงแม้มันไม่สามารถใช้งานได้ดีสำหรับข้อมูลที่มีขนาดใหญ่ แต่ด้วยการใช้งานที่ตรงจุดและเข้าใจได้ง่ายมันจึงยังมีบทบาทสำคัญในด้านการจัดระบบข้อมูล ทั้งในธุรกิจและการศึกษา

หากคุณมีความสนใจในการเรียนรู้เพิ่มเติมเกี่ยวกับการเขียนโปรแกรมและการใช้ Algorithm ต่าง ๆ ในการพัฒนาซอฟต์แวร์หรือโซลูชั่นข้อมูลต่างๆ อย่าลืมที่จะเข้าร่วมเรียนกับ EPT (Expert-Programming-Tutor) ที่เรามีการสอนอย่างครบถ้วนและมีผู้เชี่ยวชาญคอยช่วยเหลือคุณในทุกขั้นตอนของการเรียนรู้!

 

 

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