Sắp xếp trong C++

Trong phần này chúng ta sẽ xem cách thực hiện thuật toán sắp xếp trong C++. Mảng đã sắp xếp là mảng mà các phần tử được sắp theo thứ tự như số học, bảng chữ cái, v.v. Có nhiều thuật toán sắp xếp mảng số như bubble sort, insertion sort, selection sort, merge sort, quick sort, heap sort, v.v. Chi tiết về sắp xếp mảng bằng selection sort như dưới đây.

Selection sort là phương pháp sắp xếp cho ra mảng đã sắp xếp. Nó làm bằng cách lặp lại tìm phần tử nhỏ nhất trong mảng và hoán đổi nó với phần tử ở đầu phần chưa sắp xếp.

Chương trình triển khai mảng sắp xếp bằng selection sort như sau.

Ví dụ

#include <iostream>
using namespace std;

void selectionSort(int a[], int n) {
    int i, j, min, temp;
    for (i = 0; i < n - 1; i++) {
        min = i;
        for (j = i + 1; j < n; j++)
            if (a[j] < a[min])
                min = j;
        temp = a[i];
        a[i] = a[min];
        a[min] = temp;
    }
}

int main() {
    int a[] = { 22, 91, 35, 78, 10, 8, 75, 99, 1, 67 };
    int n = sizeof(a) / sizeof(a[0]);
    int i;
    cout << "Mảng ban đầu:" << endl;
    for (i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;
    selectionSort(a, n);
    printf("\nMảng đã sắp xếp: \n");
    for (i = 0; i < n; i++)
        cout << a[i] << " ";
    return 0;
}

Kết quả

Mảng ban đầu: 22 91 35 78 10 8 75 99 1 67
Mảng đã sắp xếp: 1 8 10 22 35 67 75 78 91 99

Trong chương trình trên, selectionSort() là hàm sắp xếp mảng a[] dùng selection sort. Có hai vòng for lồng nhau. Mỗi lần lặp vòng ngoài, tìm phần tử nhỏ nhất trong phần còn lại sau i rồi hoán đổi với phần tử tại i. Lặp lại cho đến khi mảng sắp xếp xong.

Trong main(), mảng a[] được định nghĩa. Sau đó gọi selectionSort() với mảng và kích thước n. Cuối cùng in mảng đã sắp xếp.