Insertion Sort: การเรียงลำดับที่ง่ายและมีประสิทธิภาพ

 

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

 

อะไรคือ Insertion Sort?

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

 

การใช้อัลกอริธึม Insertion Sort

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

 

ตัวอย่างโค้ดในภาษา Objective-C

ต่อไปนี้เราจะดูโค้ดตัวอย่างการทำงานของ Insertion Sort ในภาษา Objective-C:

 #import <Foundation/Foundation.h>

void insertionSort(NSMutableArray *array) {
    NSInteger count = [array count];

    for (NSInteger i = 1; i < count; i++) {
        NSNumber *key = array[i];
        NSInteger j = i - 1;

        // Move elements of array[0..i-1], that are greater than key,
        // to one position ahead of their current position
        while (j >= 0 && [array[j] compare:key] == NSOrderedDescending) {
            array[j + 1] = array[j];
            j = j - 1;
        }
        array[j + 1] = key;
    }
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        NSMutableArray *arr = [NSMutableArray arrayWithObjects:@12, @11, @13, @5, @6, nil];
        NSLog(@"Original array: %@", arr);
        insertionSort(arr);
        NSLog(@"Sorted array: %@", arr);
    }
    return 0;
}

ในโค้ดข้างต้น เราเริ่มด้วยการเรียกใช้ `NSMutableArray` และกำหนดค่าตัวอย่างลงในอาร์เรย์นั้น หลังจากนั้นฟังก์ชัน `insertionSort` นั้นจะทำการเรียงลำดับอาร์เรย์ที่ส่งไป จากนั้นเราจะพิมพ์อาร์เรย์เดิมและอาร์เรย์ที่เรียงลำดับแล้วเพื่อยืนยันผลลัพธ์

 

Complexity Analysis

สำหรับความซับซ้อนของ Insertion Sort เราจะพิจารณาทั้งในกรณีเลวร้ายและดีที่สุด:

- กรณีเลวร้าย (Worst Case): เมื่ออาร์เรย์ที่เราต้องการเรียงนั้นเรียงย้อน (Descending Order) ค่าเวลาในการประมวลผลจะอยู่ที่ O(n²) - กรณีดีที่สุด (Best Case): เมื่ออาร์เรย์ที่เราต้องการเรียงนั้นเรียงเรียบร้อยอยู่แล้ว (Ascending Order) ค่าเวลาในการประมวลผลจะอยู่ที่ O(n) - กรณีเฉลี่ย (Average Case): มักจะอยู่ที่ O(n²) เพราะมีการเปรียบเทียบในทุก ๆ รอบทำให้ต้องวนซ้ำหลายรอบ

 

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

ข้อดี:

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

ข้อเสีย:

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

 

Use Case ในโลกจริง

การจัดเรียงข้อมูลมีสถานการณ์หลากหลายที่เกิดขึ้นในชีวิตประจำวัน เช่น:

- การจัดลำดับคะแนนสอบ: ถ้าเรามีข้อมูลของนักเรียนที่ต้องการจัดลำดับจากคะแนนสูงไปต่ำ อัลกอริธึมนี้สามารถนำมาใช้ในการจัดเรียงคะแนนได้อย่างมีประสิทธิภาพ - การจัดลำดับสินค้าในสต็อก: หากเราต้องการให้สินค้าหรือรายการในโกดังเรียงตามรหัสหรือชื่อสินค้า อัลกอริธึมนี้คือคำตอบ - การเรียงข้อมูลในอุปกรณ์พกพา: อุปกรณ์พกพาหรือ Smart device สามารถใช้ Insertion Sort ในการจัดเรียงข้อมูล เช่น เพลงในลิสต์เล่นหรือแอปพลิเคชันในโทรศัพท์

 

สรุป

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

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

 

 

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