Chương trình C++ triển khai thuật toán Selection Sort (Sắp xếp chọn)

Trong kỹ thuật sắp xếp chọn (Selection Sort), danh sách được chia thành hai phần. Một phần tất cả các phần tử đã được sắp xếp, phần còn lại các mục chưa sắp xếp. Ban đầu chúng ta lấy dữ liệu lớn nhất hoặc nhỏ nhất từ mảng. Sau khi lấy được dữ liệu (giả sử là nhỏ nhất), chúng ta đặt nó ở đầu danh sách bằng cách thay thế dữ liệu ở vị trí đầu tiên bằng dữ liệu nhỏ nhất. Sau khi thực hiện, mảng đang xét trở nên nhỏ hơn. Vậy kỹ thuật sắp xếp này được thực hiện.

Độ phức tạp của kỹ thuật Selection Sort

• Độ phức tạp thời gian: O(n²)
• Độ phức tạp không gian: O(1)

Đầu vào — Danh sách chưa sắp xếp: 5 9 7 23 78 20
Đầu ra — Mảng sau khi sắp xếp: 5 7 9 20 23 78

Thuật toán

selectionSort(array, size)

Đầu vào: Mảng dữ liệu, và tổng số phần tử trong mảng

Đầu ra: Mảng đã sắp xếp

Bắt đầu
    for i := 0 đến size-2 // tìm minimum từ vị trí i đến size
        iMin := i
        for j := i+1 đến size - 1
            if array[j] < array[iMin] thì
                iMin := j
        hoán đổi array[i] với array[iMin]
Kết thúc

Mã ví dụ

#include <iostream>
using namespace std;

void swapping(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

void display(int *array, int size) {
    for(int i = 0; i < size; i++)
        cout << array[i] << " ";
    cout << endl;
}

void selectionSort(int *array, int size) {
    int i, j, imin;
    for(i = 0; i < size-1; i++) {
        imin = i;
        for(j = i+1; j < size; j++)
            if(array[j] < array[imin])
                imin = j;
        swap(array[i], array[imin]);
    }
}

int main() {
    int n;
    cout << "Nhập số lượng phần tử: ";
    cin >> n;
    int arr[n];
    cout << "Nhập các phần tử:" << endl;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << "Mảng trước khi sắp xếp: ";
    display(arr, n);
    selectionSort(arr, n);
    cout << "Mảng sau khi sắp xếp: ";
    display(arr, n);
}

Kết quả đầu ra

Nhập số lượng phần tử: 6
Nhập các phần tử: 5 9 7 23 78 20
Mảng trước khi sắp xếp: 5 9 7 23 78 20
Mảng sau khi sắp xếp: 5 7 9 20 23 78