Nội dung chính tin học 11 theo định hướng khoa học máy tính cánh diều Chủ đề F(CS) Bài 8: Lập trình một số thuật toán sắp xếp

BÀI 8. LẬP TRÌNH MỘT SỐ THUẬT TOÁN SẮP XẾP

1. BÀI TOÁN SẮP XẾP

- Trong tin học, thuật ngữ sắp xếp đề cấp đến việc tổ chức lại một tập hợp dữ liệu theo một tiêu chí sắp xếp, tức là đáp ứng một yêu cầu cụ thể về trình tự.

- Yêu cầu sắp xếp cần chỉ rõ cách so sánh hai mục dữ liệu để quyết định thứ tự.

Ví dụ: Bài toán sắp xếp đơn giản và minh họa bằng sắp xếp dãy số.

- Đầu vào: Dãy n số a₀, a₁ ,..., a_{n – 1}.

- Đầu ra: Dãy được sắp xếp theo thứ tự tăng dần (không giảm).

Sắp xếp tại chỗ và không tại chỗ

- Một thuật toán không dùng thêm một dãy khác ở bên ngoài dãy ban đầu để thực hiện sắp xếp được gọi là sắp xếp tại chỗ.

- Nếu thuật toán sử dụng một dãy khác ở bên ngoài dãy ban đầu để chứa kết quả thì gọi là sắp xếp không tại chỗ.

Nghịch thế

- Nếu i < j mà a_i > a_j thì cặp hai phần tử (a_i, a_j) gọi là một nghịch thế.

- Một thuật toán sắp xếp dựa trên ý tưởng giảm dần và tiến đến triệt tiêu các nghịch thế trong dãy.

2. THUẬT TOÁN SẮP XẾP NỔI BỌT (BUBBLE SORT)

- Ý tưởng sắp xếp nổi bọt (Bubble Sort):

+ Xét lần lượt các cặp phần tử liên tiếp: nếu a_i > a_i+1 thì đổi chỗ [a_i, a_i+1].

+ Lặp lại cho đến khi triệt tiêu hết các cặp nghịch thế.

+ Có thể chứng minh sau vòng lặp 1 thì số lớn nhất trong dãy sẽ được chuyển đến vị trí cuối dãy, tức là phần tử a[n – 1] đã ở đúng vị trí. Như vậy vòng lặp 2 chỉ cần rà soát nghịch thế và đổi chỗ đến vị trí n – 2.

- Sau vòng lặp i thì phần tử a[n – i – 1] đã ở đúng vị trí.

- Mã giả của thuật toán sắp xếp nổi bọt:

3. THUẬT TOÁN SẮP XẾP CHÈN TUYẾN TÍNH (INSERTION SORT)

Ý tưởng sắp xếp chèn tuyến tính:

- Vì dãy con a₀ chỉ có một phần tử, nên dãy con này có thứ tự.

- Lặp lại việc chèn a_i với 1 ≤ i < n như sau:

Xét dãy con a₀,..., a_{i – 1} đã có thứ tự, ta chèn a_i vào dãy con này sao cho dãy con sau khi chèn sẽ có thứ tự.

Mô tả thuật toán chèn tuyến tính:

Mô tả các bước của thuật toán như sau:

Bước 0. i ← 1;

Bước 1.

      if i ≥ n: kết thúc;

     else: val ← a_i; k ← i – 1;

Bước 2.

     if k ≥ 0:

           if a_k > val: a_{k + 1} ← a_k; k ← k – 1; đến Bước 2;

Bước 3. a_{k + 1} ← val; i ← i + 1; đến Bước 1;

Để “chèn a_i vào đúng chỗ của nó” trong dãy a₀, a₁ ,..., a_{i – 1} cần:

a) Tìm được chỗ đúng thứ tự của a_i: Cho k đi từ i – 1 qua trái cho đến khi a_k ≤ a_i hoặc k = – 1.

b) Lấy a_i ra khỏi dãy; dịch chuyển dãy a_{k + 1} ,..., a_{i – 1} sang phải một vị trí để có chỗ trống tại a_{k + 1}; đưa a_i vào chỗ trống đó.

Mã giả thuật toán sắp xếp chèn tuyến tính

Thuật toán sắp xếp chèn tuyến tính kết hợp làm đồng thời hai việc a) và b) theo cách dịch chuyển dần từng bước sang trái, từ vị trí i tới vị trí k + 1.

- Vòng lặp for bên ngoài kiểm soát việc thực hiện đúng n – 1 bước.

- Vòng lặp while lồng bên trong thực hiện đồng thời cùng

4. THỰC HÀNH

Nhiệm vụ 1.

a) Số lần lặp của vòng lặp bên trong với bước i sẽ không quá i.

b) Vòng lặp ngoài của thuật toán được thực hiện đúng n – 1 lần như đã nhận xét trong bài học.

c) Ước lượng độ phức tạp thời gian của thuật toán sắp xếp chèn tuyến tính là O(n²) vì không vượt quá tổng 1 + 2 + … + n – 1.

Nhiệm vụ 2. Tham khảo chương trình sau:

def sxNoibot(a):

    n = len(a)

    for i in range(n):

        CoDoiCho = False

        for k in range(n-1-i):

            if a[j] > a[j+1]:

                CoDoiCho = True

                a[j], a[j+1] = a[j+1], a[j]

        if (not CoDoiCho):

            return

Nhiệm vụ 3. Tham khảo chương trình sau:

def sxChen(a): # chèn tuyến tính

    n = len(a)

    for i in range(1,n):

       val = a[i]

       j, i = i, i+1

       # dịch dần từng bước, tìm vị trí để chèn

       while(j>0) and (a[j-1] > val):

           a[j] = a[j-1]

           j = j - 1

    a[j] = val

=> Kết luận:

- Thuật toán sắp xếp nổi bọt có hai vòng lặp lồng nhau; vòng lặp trong thực hiện đổi chỗ một lượt các cặp phần tử là nghịch thế, vòng lặp ngoài kiểm tra điều kiện “không xảy ra đổi chỗ”.

- Việc tìm vị trí chèn đúng chỗ trong thuật toán sắp xếp chèn có thể thực hiện bằng cách dịch dần từng bước.