[Mỗi ngày 1 thuật toán] Thuật toán sắp xếp chọn – Selection Sort

1. Ý tưởng

Ý tưởng của thuật toán sắp xếp chọn (selection sort) là:

1. Tìm phần tử nhỏ nhất trong mảng chưa được sắp xếp.
2. Hoán đổi phần tử nhỏ nhất với phần tử đầu tiên của mảng chưa được sắp xếp.
3. Di chuyển con trỏ đến phần tử tiếp theo của mảng chưa được sắp xếp.
4. Lặp lại các bước 1-3 cho đến khi toàn bộ mảng được sắp xếp.

Cụ thể, thuật toán sẽ thực hiện như sau:

1. Tìm phần tử nhỏ nhất trong mảng.
2. Hoán đổi phần tử nhỏ nhất với phần tử đầu tiên của mảng.
3. Lặp lại các bước trên với phần còn lại của mảng, bắt đầu từ phần tử thứ hai.
4. Tiếp tục lặp lại cho đến khi toàn bộ mảng được sắp xếp.

2. Ví dụ, cho mảng [5, 2, 4, 6, 1, 3]:

1. Tìm phần tử nhỏ nhất trong mảng là 1, hoán đổi 1 với 5 => [1, 2, 4, 6, 5, 3].
2. Tìm phần tử nhỏ nhất trong mảng [2, 4, 6, 5, 3] là 2, hoán đổi 2 với 2 => [1, 2, 4, 6, 5, 3].
3. Tìm phần tử nhỏ nhất trong mảng [4, 6, 5, 3] là 3, hoán đổi 3 với 4 => [1, 2, 3, 6, 5, 4].
4. Tìm phần tử nhỏ nhất trong mảng [6, 5, 4] là 4, hoán đổi 4 với 6 => [1, 2, 3, 4, 5, 6].
5. Mảng đã được sắp xếp.

3. Hình minh họa

4. Pseudo code

5. Mã nguồn trong Java

6. Mã nguồn trong PHP

7. Mã nguồn trong Python