Selection Sort in C

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

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

Algorithm นี้ทำงานแบ่งออกเป็น 2 ส่วนหลักๆ คือ "sorted list" และ "unsorted list" ในตอนเริ่มต้น sorted list จะว่างเปล่า และ unsorted list จะมีข้อมูลทั้งหมดที่จะต้องการจัดเรียง เมื่อทำการเรียกใช้งาน, Selection Sort จะค้นหาข้อมูลที่ต้องการ (น้อยสุดหรือมากสุด) จาก unsorted list, ย้ายข้อมูลนั้นไปยัง sorted list พร้อมกับสลับตำแหน่งกับข้อมูลที่อยู่ในตำแหน่งแรกของ unsorted list จากนั้นก็ทำซ้ำกระบวนการจนกว่าข้อมูลทั้งหมดจะถูกจัดเรียงเรียบร้อย

ต่อมาให้เรามารู้จักกับตัวอย่างโค้ดการทำงานของ Selection Sort ด้วยภาษา C:

#include 

void selectionSort(int arr[], int n) {
    int i, j, min_idx, temp;

    // ย้ายเข้าไปยังแต่ละข้อมูลใน unsorted list
    for (i = 0; i < n-1; i++) {
        // หา index ของข้อมูลที่น้อยที่สุดใน unsorted list
        min_idx = i;
        for (j = i+1; j < n; j++)
            if (arr[j] < arr[min_idx])
                min_idx = j;

        // สลับข้อมูลเพื่อนำข้อมูลที่น้อยที่สุดไปไว้ที่ตำแหน่งที่ถูกต้องใน sorted list
        temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

/* ฟังก์ชันในการแสดงผล array */
void printArray(int arr[], int size) {
    int i;
    for (i=0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

/* ฟังก์ชันหลักที่ใช้ในการทดสอบ Selection Sort */
int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    selectionSort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

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

การวิเคราะห์ความซับซ้อนของ Selection Sort เป็น `O(n^2)` ในทุกกรณี เพราะว่ามันค้นหารายการที่น้อยที่สุดใน unsorted list แล้วทำการสลับตำแหน่ง การใช้ nested loops (ลูปซ้อน) ทำให้ความเร็วในการประมวลผลเป็นไปแบบ quadratically สำหรับข้อมูลทุกขนาด

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

ข้อดี:

1. เรียบง่ายและง่ายต่อการเข้าใจและปรับใช้

2. ประสิทธิภาพไม่ขึ้นกับการจัดเรียงข้อมูลเริ่มต้น

3. ไม่ต้องการการกินพื้นที่เมมโมรี่เพิ่มเติมในระหว่างการจัดเรียง (in-place sorting)

ข้อเสีย:

1. ความเร็วในการประมวลผลไม่เร็ว (ประสิทธิภาพ) เนื่องจากมีความซับซ้อน `O(n^2)`

2. ไม่เหมาะกับข้อมูลที่มีขนาดใหญ่

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

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