Bài 48. Thuật toán sắp xếp chọn (Selection sort)

Chào mừng các bạn quay trở lại với blog của Nguyễn Văn Hiếu. Đây là một bài viết trong series các thuật toán sắp xếp có minh họa code sử dụng ngôn ngữ lập trình C++. Bài viết đầu tiên này Nguyễn Văn Hiếu xin giới thiệu tới các bạn thuật toán sắp xếp chọn. Nội dung bài viết bao gồm các phần sau:

• Ý tưởng của thuật toán
• Ví dụ minh họa
• Minh họa thuật toán sử dụng ngôn ngữ C++
• Đánh giá thuật toán

Lưu ý: Bài viết chỉ mô tả cho việc sắp xếp dãy số tăng dần. Việc sắp xếp dãy số giảm dần sẽ tương tự và bạn đọc tự tìm hiểu

Ý tưởng của thuật toán sắp xếp chọn

Thuật toán sắp xếp chọn sẽ sắp xếp một mảng bằng cách đi tìm phần tử có giá trị nhỏ nhất(giả sử với sắp xếp mảng tăng dần) trong đoạn đoạn chưa được sắp xếp và đổi cho phần tử nhỏ nhất đó với phần tử ở đầu đoạn chưa được sắp xếp(không phải đầu mảng). Thuật toán sẽ chia mảng làm 2 mảng con

1. Một mảng con đã được sắp xếp
2. Một mảng con chưa được sắp xếp

Tại mỗi bước lặp của thuật toán, phần tử nhỏ nhất ở mảng con chưa được sắp xếp sẽ được di chuyển về đoạn đã sắp xếp.

Ví dụ minh họa

arr[] = 62 24 15 22 1

// Tìm phần tử nhỏ nhất trong trong arr[0...4]
// và đổi chỗ nó với phần tử đầu tiên
[1] 24 15 22 62

// Tìm phần tử nhỏ nhất trong trong arr[1...4]
// và đổi chỗ nó với phần tử đầu tiên của arr[1...4]
1 [15] 24 22 62

// Tìm phần tử nhỏ nhất trong trong arr[2...4]
// và đổi chỗ nó với phần tử đầu tiên của arr[2...4]
1 15 [22] 24 62

// Tìm phần tử nhỏ nhất trong trong arr[3...4]
// và đổi chỗ nó với phần tử đầu tiên của arr[3...4]
11 12 22 [24] 62

Minh họa thuật toán sử dụng ngôn ngữ C++

// Code from https://nguyenvanhieu.vn

#include <stdio.h>

// Hàm đổi chỗ 2 số nguyên
void swap(int &xp, int &yp)
{
    int temp = xp;
    xp = yp;
    yp = temp;
}

// Hàm selection sort
void selectionSort(int arr[], int n)
{
    int i, j, min_idx;
    // Di chuyển ranh giới của mảng đã sắp xếp và chưa sắp xếp
    for (i = 0; i < n-1; i++)
    {
	// Tìm phần tử nhỏ nhất trong mảng chưa sắp xếp
	min_idx = i;
	for (j = i+1; j < n; j++)
	    if (arr[j] < arr[min_idx])
		min_idx = j;

	// Đổi chỗ phần tử nhỏ nhất với phần tử đầu tiên
        swap(arr[min_idx], arr[i]);
    }
}

/* Hàm xuất mảng */
void printArray(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", arr[i]);
    printf("n");
}


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;
}

Kết quả chạy kiểm tra

Sorted array:
11 12 22 25 64

Đánh giá thuật toán sắp xếp chọn

Độ  phức tạp thuật toán

• Trường hợp tốt: O(n^2)
• Trung bình: O(n^2)
• Trường hợp xấu: O(n^2)

Không gian bộ nhớ sử dụng: O(1)