เรียนรู้การเรียงลำดับด้วย Quick Sort ในภาษา COBOL

 

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

 

Quick Sort คืออะไร?

Quick Sort เป็นอัลกอริธึมการเรียงลำดับแบบแบ่งและพิชิต (Divide and Conquer) ที่ประกอบด้วยขั้นตอนหลักๆ สามขั้นตอนคือ:

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

การใช้งาน Quick Sort

Quick Sort เป็นอัลกอริธึมที่สามารถใช้ในการเรียงลำดับข้อมูลจำนวนมากตั้งแต่ข้อมูลตัวเลขจนถึงข้อมูลแบบข้อความ ในแอปพลิเคชันจริง เราอาจใช้ Quick Sort ในระบบจัดการฐานข้อมูล เพื่อเรียงลำดับข้อมูลตามที่เราต้องการ เช่น การจัดอันดับผลิตภัณฑ์ใน E-commerce หรือการจัดเรียงรายชื่อลูกค้า

 

ตัวอย่างโค้ด Quick Sort ใน COBOL

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

        IDENTIFICATION DIVISION.
       PROGRAM-ID. QuickSortExample.

       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01  Numbers         PIC 9(3) OCCURS 10 TIMES VALUE 0.
       01  LowIndex        PIC 9(2) VALUE 1.
       01  HighIndex       PIC 9(2) VALUE 10.
       01  Pivot           PIC 9(3).
       01  I               PIC 9(2).
       01  J               PIC 9(2).
       01  Temp            PIC 9(3).

       PROCEDURE DIVISION.
           MOVE 45 TO Numbers(1).
           MOVE 23 TO Numbers(2).
           MOVE 67 TO Numbers(3).
           MOVE 12 TO Numbers(4).
           MOVE 78 TO Numbers(5).
           MOVE 34 TO Numbers(6).
           MOVE 56 TO Numbers(7).
           MOVE 89 TO Numbers(8).
           MOVE 90 TO Numbers(9).
           MOVE 3 TO Numbers(10).

           PERFORM QuickSort USING LowIndex HighIndex.
           DISPLAY "Sorted Numbers: ".
           PERFORM VARYING I FROM 1 BY 1 UNTIL I > 10
               DISPLAY Numbers(I)
           END-PERFORM.

           STOP RUN.

       QuickSort SECTION.
       LINKAGE SECTION.
       01  Low     PIC 9(2).
       01  High    PIC 9(2).

       PROCEDURE DIVISION USING Low High.
           IF Low < High
               MOVE Numbers(Low) TO Pivot
               MOVE Low TO I
               MOVE High TO J

               PERFORM UNTIL I > J
                   PERFORM UNTIL Numbers(I) >= Pivot OR I > High
                       ADD 1 TO I
                   END-PERFORM
                   PERFORM UNTIL Numbers(J) <= Pivot OR J < Low
                       SUBTRACT 1 FROM J
                   END-PERFORM

                   IF I < J
                       MOVE Numbers(I) TO Temp
                       MOVE Numbers(J) TO Numbers(I)
                       MOVE Temp TO Numbers(J)
                   END-IF
               END-PERFORM

               PERFORM QuickSort USING Low J
               PERFORM QuickSort USING I High
           END-IF.

 

Complexity ของ Quick Sort

Time Complexity

สำหรับ Quick Sort ขึ้นอยู่กับการเลือก Pivot: - Best Case: O(n log n) – เกิดขึ้นเมื่อ Pivot แบ่งข้อมูลออกเป็นสองส่วนที่มีขนาดใกล้เคียงกัน - Average Case: O(n log n) - Worst Case: O(n²) – เกิดขึ้นเมื่อ Pivot ที่เลือกนำไปสู่การจัดเรียงที่ไม่ดี เช่น ข้อมูลเรียงอยู่แล้วหรือมีลักษณะเป็น sorted arrays

Space Complexity:

O(log n) เพราะ Quick Sort ใช้การเรียกฟังก์ชันในสแตก

 

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

ข้อดี

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

ข้อเสีย

1. Worst Case Performance: เมื่อข้อมูลเกือบเรียงอยู่แล้วจะทำให้ประสิทธิภาพแย่ลง สามารถพิจารณาใช้ Randomized Quick Sort หรือลำดับการเลือก Pivot ที่แตกต่างกัน 2. ไม่ Stable Sort: Quick Sort ไม่สามารถรักษาอันดับของข้อมูลที่มีค่าเท่ากันได้

 

สรุป

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

เบื้องต้นเราหวังว่าบทความนี้จะช่วยให้คุณเข้าใจเกี่ยวกับ Quick Sort ในการเขียนโปรแกรม COBOL และสามารถนำไปประยุกต์ใช้ในโครงการจริงของคุณได้!

 

 

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