Ôn tập kiến thức Tin học 11 định hướng Khoa học máy tính Cánh diều bài 9: Lập trình thuật toán sắp xếp nhanh

[toc:ul]

1. LƯỢC ĐỒ PHÂN ĐOẠN TRONG SẮP XẾP NHANH

Thuật toán sắp xếp nhanh (Quick Sort)

- Thuật toán theo chiến lược chia để trị, lặp lại nhiều lần việc phân đoạn dãy đầu vào thành hai đoạn con.

Lược đồ phân đoạn dãy số

- Lấy giá trị của một phần từ trong dãy làm pivot (giá trị chốt). Giá trị pivot có thể là bất cứ phần tử nào trong dãy. 

- Kết quả phân đoạn: 

+ Đoạn con ở nửa dãy bên trái chỉ gồm các phần tử nhỏ hơn hay bằng pivot.

+ Đoạn con ở nửa dãy bên phải chỉ gồm các phần tử lớn hơn hay bằng pivot.

+ Phần tử làm pivot được chuyển đến vị trí phân tách hai đoạn.

Hình 1. Kết quả phân đoạn: đoạn trái = {i|lo ≤ i ≤ p – 1}, đoạn phải = {j|p + 1 ≤ i ≤ hi}

- Hàm thực hiện phân đoạn cần trả về vị trí phân tách dãy thành hai đoạn con vì sau đó sẽ sắp xếp chỉ trong nội bộ hai đoạn con.

2. THUẬT TOÁN SẮP XẾP NHANH ÁP DỤNG PHÂN ĐOẠN LOMUTO

- Mã giả của thuật toán Lomuto phân đoạn dãy số a, trong đó:

lo là chỉ số đầu mút trái

hi là chỉ số đầu mút phải

- Ý tưởng của thuật toán Lomuto: Chọn pivot là giá trị phần tử đứng cuối dãy số. 

+ Duy trì chỉ số i ở vị trí phân tách;

+ Duyệt dãy số bằng một chỉ số j khác và đảo giá trị các phần tử sao cho các phần tử từ vị trí i – 1 về đầu mút trái nhỏ hơn hay bằng pivot; các phần tử từ vị trí i + 1 đến j lớn hơn pivot, riêng phần tử ở vị trí i đúng bằng pivot.

- Mã lệnh Python thực hiện sắp xếp nhanh bằng phân đoạn Lomuto:

3. THUẬT TOÁN SẮP XẾP NHANH ÁP DỤNG PHÂN ĐOẠN HOARE

Lược đồ phân đoạn Hoare

- Ý tưởng của thuật toán: 

+ Đổi chỗ nhảy qua điểm phân tách (pivot), rà soát từ hai phía, trái và phải, cùng tiến dần từng bước vào giữa.

+ Tạm dừng khi phát hiện phần tử vi phạm yêu cầu phân đoạn ở mỗi phía và đổi chỗ chúng cho nhau.

+ Rà soát từ hai điểm tạm dừng đi vào giữa cho đến khi gặp nhau thì kết thúc việc phân đoạn.

+ Điểm gặp nhau là vị trí phân tách dãy thành hai đoạn con.

- Mã giả của thuật toán sắp xếp nanh áp dụng phân đoạn Hoare:

- Mã lệnh Python của thuật toán phân đoạn dãy số a, xuất phát với pivot là đầu dãy.

4. THỰC HÀNH

Nhiệm vụ 1: 

def phandoanLomuto(a, lo, hi):

    i = (lo-1)                       #i là vị trí phân tách

    pivot = a[hi]

    for j in range(lo,hi ):          #Duyệt dãy a[lo...hi]

        if a[j] <= pivot:            #Phần tử a[j] <= pivot

            i = i+1                  #Tăng i lên

            a[i], a[j] = a[j], a[i]     #Đảo giá trị a[i], a[j]

    a[i+1], a[hi] = a[hi], a[i+1]      #Đảo giá trị a[i+1], a[hi]

    return (i+1)                     #Hết vòng lặp, i là vị trí phân đoạn

                                     #a[i] = pivot

def quickSort(a, lo, hi):

    if lo < hi:

        p = phandoanLomuto(a, lo, hi #p là vị trí phân tách

                                     #a[p] đã ở đúng chỗ

        quickSort(a, lo, p-1)        #Sắp xếp đoạn bên trái

        quickSort(a, p+1, hi)        #Sắp xếp đoạn bên phải

data = [8, 7, 2, 1, 0, 9, 6]

print("Dãy ban đầu a:")

print(data)

size = len(data)

quickSort(data, 0, size - 1)

print('Dãy được sắp xếp:')

print(data)

Nhiệm vụ 2:

def partitionHoare(a, lo, hi):

    pivot = a[lo]

    i, j = lo, hi

    phanDoan = True

    while phanDoan:              #Đang phân đoạn

        #i qua phải đến khi a[i] >= pivot

        while a[i] < pivot:

            i = i + 1

        #j qua trái đến khi a[j] <= pivot

        while a[j] > pivot:

            j = j - 1

        if i < j:                   #i chưa gặp j   

        #Hoán đổi a[i] với a[j]

            a[i], a[j] = a[j], a[i]

            i = i + 1               # i qua phải

            j = j - 1               #j qua trái

        else:

            phanDoan = False        #Kết thúc phân đoạn

    return j

def quickSortHoare(a, lo, hi):

    if lo < hi:

        p = partitionHoare(a, lo, hi)

        quickSortHoare(a, lo, p)

        quickSortHoare(a, p+1, hi)

data = [8, 7, 2, 1, 0, 9, 6]

print("Dãy ban đầu a:")

print(data)

size = len(data)

quickSortHoare(data, 0, size - 1)

print('Dãy được sắp xếp:')

print(data)