Sắp xếp chọn¶

Đặt vấn đề¶

Với bảng điểm của lớp, làm sao để lấy ra 10 bạn có điểm số cao nhất hoặc thấp nhất?

Một cách làm đơn giản là ta sắp xếp bảng điểm trước, sau đó mới lấy ra 10 phần tử đầu tiên hoặc 10 phần tử cuối cùng tùy theo yêu cầu.

Bài toán và thuật toán sắp xếp¶

Sắp xếp dữ liệu là quá trình cơ bản và quan trọng trong xử lý dữ liệu, tạo thuận lợi cho việc tìm kiếm, truy xuất và phân tích dữ liệu.

Sắp xếp dữ liệu là quá trình tổ chức lại dữ liệu theo một trật tự có nghĩa nào đó, thường là tăng dần hoặc giảm dần.

Trong chủ đề F, ta chỉ xét bài toán đơn giản là sắp xếp mảng một chiều các số nguyên theo thứ tự không giảm, nghĩa là phần tử liền sau lớn hơn hoặc bằng phần tử liền trước, và tạm gọi là tăng dần.

Có nhiều thuật toán sắp xếp khác nhau, hầu hết trong số đó thực hiện thao tác so sánh các phần tử với nhau để xác định một phần tử sẽ đứng trước hay đứng sau một phần tử khác.

Mỗi thuật toán có ưu điểm và hạn chế riêng. Tuỳ vào loại dữ liệu và yêu cầu, ta sẽ chọn thuật toán phù hợp.

Bài học này đề cập thuật toán sắp xếp chọn.

Thuật toán sắp xếp chọn¶

Ý tưởng¶

Hãy tưởng tượng, ta cần chọn đội hình gồm những cầu thủ có phong độ tốt nhất từ những cầu thủ hiện có để thi đấu. Ta thực hiện bằng cách: chọn cầu thủ có phong độ tốt nhất, chọn cầu thủ có phong độ tốt thứ hai, chọn cầu thủ có phong độ tốt thứ ba, v.v...

Áp dụng cách trên cho mảng, nếu xem "nhỏ nhất" đồng nghĩa "tốt nhất", thì ta sẽ chọn phần tử nhỏ nhất trước, rồi chọn tiếp phần tử nhỏ nhất tiếp theo, rồi chọn tiếp phần tử nhỏ nhất tiếp theo nữa, v.v...

Như vậy, ý tưởng của thuật toán sắp xếp chọn như sau:

Ví dụ¶

Lưu đồ thuật toán¶

Trực quan hóa thuật toán¶

Chương trình minh họa¶

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# Hàm sắp xếp chọn
def selectionSort(A):
    n = len(A)

    # Duyệt mảng A từ vị trí 0 đến áp cuối
    for i in range(n - 1):
        # Tìm vị trí phần tử nhỏ nhất của mảng con tính từ i đến cuối
        min = i
        for j in range(i + 1, n): 
            if A[j] < A[min]:
                min = j

        # Hoán vị A[min] và A[i]
        A[i], A[min] = A[min], A[i]


# Chương trình chính
if __name__ == '__main__':
    array = [1, 7, 4, 0, 9, 4, 8, 8]
    print(f'Mảng gốc chưa có thứ tự: {array}')

    selectionSort(array)
    print(f'Mảng có thứ tự tăng dần: {array}')

Output:

Mảng gốc chưa có thứ tự: [1, 7, 4, 0, 9, 4, 8, 8]
Mảng có thứ tự tăng dần: [0, 1, 4, 4, 7, 8, 8, 9]

Sơ đồ tóm tắt nội dung¶

Google Colab¶

Các đoạn mã trong bài này được đặt tại Google Colab để bạn có thể thử nghiệm theo cách của riêng mình.

Some English words¶