Thuật toán sắp xếp chọn (Selection Sort) trong C

Selection Sort tìm phần tử nhỏ nhất trong mảng và đưa về vị trí đầu. Tiếp tục với phần còn lại cho đến khi sắp xếp xong.

Quy trình

• Chọn phần tử nhỏ nhất trong danh sách, đặt ở vị trí đầu.
• Lặp lại cho phần còn lại cho đến khi toàn bộ đã sắp xếp.

Ví dụ minh họa (mảng: 30 50 40 10 20)

Lượt 1: Tìm min = 10, hoán đổi với a[0] → 10 50 40 30 20

Lượt 2: Tìm min từ a[1] = 20, hoán đổi với a[1] → 10 20 40 30 50

Lượt 3: Tìm min từ a[2] = 30, hoán đổi với a[2] → 10 20 30 40 50

Lượt 4: Chỉ còn 40 và 50, đã đúng thứ tự.

Thuật toán (pseudocode)

for i = 0 to n-2:
    sm = i
    for j = i+1 to n-1:
        if a[j] < a[sm]: sm = j
    swap(a[i], a[sm])

Chương trình C

#include <stdio.h>
int main() {
    int a[50], n, i, j, t, sm;
    printf("Nhap so phan tu: ");
    scanf("%d", &n);
    printf("Nhap cac phan tu: ");
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);
    for (i = 0; i < n-1; i++) {
        sm = i;
        for (j = i+1; j < n; j++)
            if (a[j] < a[sm]) sm = j;
        t = a[i];
        a[i] = a[sm];
        a[sm] = t;
    }
    printf("Mang sau sap xep: ");
    for (i = 0; i < n; i++)
        printf("%d ", a[i]);
    return 0;
}

Kết quả

Nhap so phan tu: 4
Nhap cac phan tu: 45 12 37 68
Mang sau sap xep: 12 37 45 68