Insertion Sort in C++

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

อัลกอริทึมของ Insertion Sort คืออะไร?

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

การใช้งานในภาษา C++

ต่อไปนี้คือตัวอย่างโค้ดการเขียน Insertion Sort ในภาษา C++:

#include 
using namespace std;

// ฟังก์ชันการจัดเรียงข้อมูลแบบ Insertion Sort
void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        // ย้ายข้อมูลที่มากกว่า key ไปอยู่ทางขวาทีละตำแหน่ง
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

// ฟังก์ชันหลัก
int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);

    insertionSort(arr, n);

    // พิมพ์ผลลัพธ์หลังจากจัดเรียง
    cout << "Sorted array: \n";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}

Usecase ในโลกจริง

ในโลกจริง Insertion Sort นั้นกำเรียบงานเหมาะกับกับชุดข้อมูลที่มีขนาดเล็กหรือชุดข้อมูลที่เกือบจะเรียงลำดับอยู่แล้ว เช่น การจัดลำดับอันดับนักเรียนที่มีจำนวนไม่มากหรือจัดเรียงหนังสือในห้องสมุดย่อยที่มีชั้นเดียว

Complexity และข้อดีข้อเสีย

Complexity:

- ความซับซ้อนเวลา (Time Complexity) ในการจัดเรียงข้อมูลด้วย Insertion Sort ในกรณีเลวร้ายที่สุด (Worst case) คือ `O(n^2)`, สำหรับชุดข้อมูลที่มีจำนวน n ส่วนที่ดีที่สุด (Best case) เมื่อข้อมูลเรียงลำดับอยู่แล้วเป็น `O(n)`

- ความซับซ้อนในเรื่องของพื้นที่ (Space Complexity) คือ `O(1)` เนื่องจากไม่ต้องการพื้นที่เพิ่มเติมในการจัดเรียงนอกจากโครงสร้างข้อมูลที่มีอยู่

ข้อดีข้อเสีย:

ข้อดี:

- ง่ายต่อการเข้าใจและการเขียนโปรแกรม

- ไม่ต้องการเมมโมรีเพิ่ม (In-place sorting)

- เหมาะกับชุดข้อมูลที่ขนาดเล็ก

- เมื่อชุดข้อมูลเรียงลำดับอยู่แล้ว มีประสิทธิภาพดีเยี่ยม

ข้อเสีย:

- มีประสิทธิภาพไม่ดีเมื่อชุดข้อมูลมีขนาดใหญ่

- ความซับซ้อนเวลาเป็นกำลังสองทำให้ไม่เหมาะกับจำนวนข้อมูลที่มาก

Insertion Sort สามารถเรียนรู้และทำความเข้าใจได้ไม่ยากสำหรับมือใหม่ หากคุณมีความสนใจในการเขียนโค้ดหรืออยากพัฒนาแอปพลิเคชั่นของตนเอง ไม่ว่าจะด้วยภาษา C++ หรือภาษาอื่น EPT มีหลักสูตรและผู้เชี่ยวชาญที่พร้อมแนะนำและช่วยเหลือคุณในทุกขั้นตอน ศึกษาการเขียนโปรแกรม แก้ไขปัญหา และพัฒนาทักษะของคุณไปอีกขั้นได้ที่ EPT วันนี้!

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