รู้จักกับ Quick Sort: อัลกอริธึมที่รวดเร็วในการจัดเรียงข้อมูล

 

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

 

Quick Sort คืออะไร?

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

การทำงานของ Quick Sort:

1. เลือกค่า Pivot: ค่านี้มักเลือกเป็นค่ากลางหรือตัวแรก/ตัวสุดท้ายจากรายการ

2. จัดกลุ่มข้อมูล: นำค่าที่น้อยกว่าหรือเท่ากับไปทางซ้าย และค่าที่มากกว่าไปทางขวา

3. เรียกใช้ Quick Sort ซ้ำสำหรับทั้ง 2 กลุ่ม

4. ฐานหยุด: เมื่อกลุ่มข้อมูลมีความยาว 1 หรือไม่มีข้อมูล

 

ตัวอย่าง Code ด้วยภาษา Objective-C

มาดูตัวอย่างการใช้งาน Quick Sort ด้วย Objective-C กันดีกว่า:

 #import <Foundation/Foundation.h>

@interface QuickSort : NSObject
- (NSArray *)quickSort:(NSArray *)array;
@end

@implementation QuickSort
- (NSArray *)quickSort:(NSArray *)array {
    if ([array count] <= 1) {
        return array; // แสดงว่ากลุ่มนี้จัดเรียงแล้ว
    }

    // เลือก Pivot
    NSNumber *pivot = array[0];
    NSMutableArray *less = [NSMutableArray array];
    NSMutableArray *greater = [NSMutableArray array];

    // จัดกลุ่มข้อมูล
    for (NSUInteger i = 1; i < [array count]; i++) {
        NSNumber *number = array[i];
        if ([number compare:pivot] == NSOrderedAscending) {
            [less addObject:number];  // น้อยกว่า pivot
        } else {
            [greater addObject:number];  // มากกว่า pivot
        }
    }

    // เรียกใช้งาน Quick Sort ซ้ำ
    return [[self quickSort:less] arrayByAddingObjectsFromArray:@[pivot] arrayByAddingObjectsFromArray:[self quickSort:greater]];
}
@end

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        NSArray *array = @[@3, @6, @8, @10, @1, @2, @1];
        QuickSort *qs = [[QuickSort alloc] init];
        NSArray *sortedArray = [qs quickSort:array];

        NSLog(@"Sorted Array: %@", sortedArray);
    }
    return 0;
}

ในตัวอย่างข้างต้น เราได้สร้างคลาส `QuickSort` ซึ่งมีฟังก์ชัน `quickSort` สำหรับการเรียงลำดับ โดยใช้การเลือกค่า Pivot เป็นตัวตั้งต้น ในที่สุดเมื่อเรียกติดเครื่องบินที่จัดเรียงเสร็จสิ้น เราก็จะได้ชุดข้อมูลาที่เรียงลำดับอย่างสวยงาม

 

Use Case ในโลกจริง

1. การจัดเรียงไฟล์: ในการจัดการข้อมูลขนาดใหญ่ในระบบคลังข้อมูล คอมพิวเตอร์มักใช้ Quick Sort เพื่อจัดเรียงไฟล์ตามวันที่หรือตามชื่อได้อย่างมีประสิทธิภาพ 2. การจัดเรียงผลการค้นหา: เมื่อคุณค้นหาบางอย่างจากข้อมูลที่ใหญ่ การจัดเรียงผลลัพธ์อย่างรวดเร็วจะช่วยให้ผู้ใช้ได้ผลลัพธ์ที่ต้องการในเวลาสั้นที่สุด 3. การจัดเรียงในเกม: เกมมีรายการที่ต้องจัดเรียง เช่น คะแนนของผู้เล่น หรือระยะทางที่ผู้เล่นสามารถไปถึง หรือแม้แต่ลำดับของอาวุธใน Inventory

 

Complexity Analysis

1. Time Complexity:

- Best Case: O(n log n) — เมื่อ Pivot แบ่งข้อมูลได้อย่างสมดุล

- Average Case: O(n log n) — ในการจัดเรียงทั่วไป

- Worst Case: O(n²) — เกิดขึ้นเมื่อเลือก Pivot ไม่เหมาะสม เช่น ตัวเลขที่เรียงอยู่แล้ว

2. Space Complexity:

- O(log n) เมื่อใช้ stack ในการทำงาน

 

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

ข้อดี:

- รวดเร็ว: Quick Sort มักจะมีประสิทธิภาพเหนือกว่า Merge Sort และ Heap Sort ในการจัดเรียงข้อมูลทั่วไป - ทำงานในที่เดียว: Quick Sort สามารถจัดเรียงข้อมูลในที่เดียว (In-place sorting) โดยไม่ต้องใช้พื้นที่เพิ่มเติมมากนัก - ความคล่องตัว: อัลกอริธึมนี้สามารถประยุกต์ใช้ได้กับการจัดเรียงที่หลากหลาย

ข้อเสีย:

- Worst-case performance: Quick Sort อาจมีประสิทธิภาพต่ำเมื่อใช้กับข้อมูลที่จัดเรียงแล้วหรือตั้งกำหนดไว้ไม่เหมาะสม - ไม่เสถียร (Unstable): Quick Sort ไม่สามารถรักษาลำดับของข้อมูลที่เท่ากันได้ - ต้องเลือก Pivot:การเลือก Pivot ที่ไม่ดีจะทำให้ประสิทธิภาพลดลงถึง O(n²)

 

สรุป

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

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

 

 

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