ทำความรู้จักกับ Quick Sort Algorithm ด้วยภาษา ABAP

 

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

 

Quick Sort คืออะไร?

Quick Sort เป็นอัลกอริทึมการจัดเรียงที่ถูกพัฒนาขึ้นโดย Tony Hoare ในปี 1960 อัลกอริทึมนี้ทำงานโดยการแบ่งข้อมูลออกเป็นสองกลุ่มตามค่าหนึ่ง ๆ ที่เรียกว่า Pivot ซึ่งช่วยให้ข้อมูลถูกจัดเรียงอย่างมีระบบ โดยมีลักษณะการทำงานที่มีประสิทธิภาพสูงเมื่อเปรียบเทียบกับอัลกอริทึมการจัดเรียงอื่น ๆ เช่น Bubble Sort หรือ Selection Sort

อัลกอริทึม Quick Sort ทำงานตามกระบวนการต่อไปนี้:

1. เลือกค่า Pivot จากชุดข้อมูล

2. แบ่งข้อมูลออกเป็นสองส่วน: ส่วนที่น้อยกว่าหรือเท่ากับ Pivot และส่วนที่มากกว่า Pivot

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

4. รวมผลลัพธ์เข้าด้วยกันเพื่อให้ได้ข้อมูลที่เรียงลำดับแล้ว

 

การใช้งาน Quick Sort ในโลกจริง

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

ตัวอย่าง Code Quick Sort ในภาษา ABAP

มาดูตัวอย่างโค้ด Quick Sort ในภาษา ABAP กัน โดยโค้ดนี้จะช่วยให้เราจัดเรียงอาร์เรย์ของตัวเลขจากน้อยไปหามาก:

 DATA: lv_array TYPE TABLE OF i WITH EMPTY KEY,
      lv_pivot TYPE i,
      lv_left_tab TYPE TABLE OF i WITH EMPTY KEY,
      lv_right_tab TYPE TABLE OF i WITH EMPTY KEY.

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

" ฟังก์ชั่น Quick Sort
FORM quick_sort USING it_array TYPE TABLE OF i.
  DATA: lv_size TYPE i,
        lv_idx TYPE i.

  lv_size = lines( it_array ).
  IF lv_size <= 1.
    EXIT.
  ENDIF.

  " เลือก Pivot
  lv_pivot = it_array[ lv_size / 2 ].

  LOOP AT it_array INTO DATA(lv_value).
    IF lv_value < lv_pivot.
      APPEND lv_value TO lv_left_tab.
    ELSEIF lv_value > lv_pivot.
      APPEND lv_value TO lv_right_tab.
    ENDIF.
  ENDLOOP.

  " เรียกใช้ Quick Sort ซ้ำ
  quick_sort( lv_left_tab ).
  quick_sort( lv_right_tab ).

  " รวมผลลัพธ์เข้าด้วยกัน
  it_array = lv_left_tab && VALUE #( lv_pivot ) && lv_right_tab.
ENDFORM.

" เรียกใช้ฟังก์ชั่น
quick_sort( lv_array ).

" แสดงผล
LOOP AT lv_array INTO DATA(lv_sorted_value).
  WRITE: / lv_sorted_value.
ENDLOOP.

ในโค้ดด้านบน ฟังก์ชัน `quick_sort` รับอาร์เรย์ของตัวเลขและทำการจัดเรียง หลังจากที่เลือกค่า Pivot จะมีการแบ่งอาร์เรย์ออกเป็นสองส่วนที่น้อยกว่าหรือมากกว่า Pivot

 

การวิเคราะห์ Complexity

การวิเคราะห์ความซับซ้อน (Complexity Analysis) ของ Quick Sort สามารถแบ่งออกเป็น 3 กรณี ได้แก่:

1. Best Case: หากข้อมูลถูกจัดเรียงอยู่แล้วหรือใกล้เคียงกัน อัลกอริทึมจะทำงานใน O(n log n) 2. Average Case: ในกรณีส่วนใหญ่ อัลกอริทึมทำงานใน O(n log n) 3. Worst Case: ในกรณีที่ข้อมูลเรียงจากน้อยไปหามากหรื่อจากมากไปหาน้อย (เช่นการเลือก Pivot ที่ไม่เหมาะสม) อาจทำให้เวลาในการทำงานขยายไปถึง O(n^2)

 

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

ข้อดี

- มีประสิทธิภาพสูงเมื่อจัดเรียงข้อมูลขนาดใหญ่

- ใช้หน่วยความจำน้อยกว่าอัลกอริธึมจัดเรียงอื่น ๆ

- สามารถทำงานได้โดยไม่ต้องสร้างอาร์เรย์ใหม่

ข้อเสีย

- หากข้อมูลมีลักษณะเฉพาะอาจเกิดความล่าช้าในเวลา O(n^2)

- ไม่ใช่อัลกอริธึมที่คงที่ (in-place) โดยจะต้องมีการจัดการหน่วยความจำเพิ่มเติมสำหรับสร้างส่วนที่แบ่งออก

 

สรุป

Quick Sort เป็นอัลกอริธึมการจัดเรียงที่มีประสิทธิภาพและสามารถประยุกต์ใช้ได้กับข้อมูลหลากหลายประเภท ทั้งยังเหมาะสำหรับผู้ที่ต้องการพัฒนาโปรแกรมจัดการข้อมูลในอุตสาหกรรมต่าง ๆ การเรียนรู้และเข้าใจการทำงานของ Quick Sort จะช่วยให้คุณสามารถเพิ่มทักษะการเขียนโปรแกรมและการวิเคราะห์ข้อมูลได้ดียิ่งขึ้น

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

 

 

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