CHỦ ĐỀ F^CS: GIẢI QUYẾT VẤN ĐỀ VỚI SỰ TRỢ GIÚP CỦA MÁY TÍNH

BÀI 9 LẬP TRÌNH THUẬT TOÁN SẮP XẾP NHANH

KHỞI ĐỘNG

Câu 1: Nếu cần chọn một trong hai việc sau đây, em sẽ chọn làm việc nào? Vì sao?

1. Từ mô tả thuật toán bằng liệt kê các bước, viết chương trình Python thực hiện thuật toán.
2. Từ chương trình Python thực hiện thuật toán, viết lại ngắn gọn ý tưởng chính của thuật toán.

Giải nhanh:

Chọn bước 1 → dễ nắm được các bước thực hiện và giúp bài toán có phương pháp giải chính xác hơn.

THỰC HÀNH

Nhiệm vụ 1: Viết chương trình thực hiện sắp xếp nhanh một dãy số và chạy thử kiểm tra.

a) Dựa trên mã lệnh thuật toán cho trong Hình 3 trang 128.

b) Dựa trên mã lệnh thuật toán cho trong Hình 5 trang 129.

Giải nhanh:

a) Dựa trên mã lệnh thuật toán cho trong Hình 3.

b) Dựa trên mã lệnh thuật toán cho trong Hình 5.

Nhiệm vụ 2: Bổ sung thêm các câu lệnh in kết quả trung gian vào các chương trình nói trên để có thể quan sát diễn biến từng bước thực hiện sắp xếp nhanh một dãy số.

Giải nhanh:

Câu lệnh in ra màn hình: print(".....")

Các bước thực hiện: Phân tích bài toán, độ phức tạp thuật toán

VẬN DỤNG

Câu 1: Em hãy thực hiện các công việc sau:

a) Sửa lại thủ tục phân đoạn để có hàm quickSort_ down sắp xếp theo thứ tự giảm dần.

Gợi ý. Sửa đối phép so sánh trong câu lệnh 1f a[3] <= pivot: thành 1f a[3]} >= pivot:

b) Tiếp tục sửa lại để có hàm quickSort_tuple down sắp xếp danh sách

các cặp. ví dụ (tên học sinh, điểm môn học) theo điệm môn học giảm dần.

Gợi ý: Sửa đổi đầu vào thành danh sách các cặp (tên học sinh, điểm môn học) và thực hiện so sánh theo điểm môn học.

Giải nhanh:

a) Gợi ý

void swap(int *a,int *b){

int temp=*a;

*a=*b;

*b=temp;

}

void bubblesort(int arr[],int n){

for(int i=0; i<n-1; i++){

for(int j=0; j<n-i-1; j++){

if(arr[j]>arr[j+1]){

swap(&arr[j],&arr[j+1]);

}

}

}

}

b) Gợi ý

void quickSort(int a[], int l, int r){

int p = a[(l+r)/2];

int i = l, j = r;

while (i < j){

while (a[i] < p){

i++;

}

while (a[j] > p){

j--;

}

if (i <= j){

int temp = a[i];

a[i] = a[j];

a[j] = temp;

i++;

j--;

}

}

if (i < r){

quickSort(a, i, r);

}

if (l < j){

quickSort(a, l, j);

}

}

CÂU HỎI TỰ KIỂM TRA

Câu 1: Em hãy giải thích tại sao lại nói thuật toán sắp xếp nhanh (QuickSort) theo chiến lược “chia để trị”.

Giải nhanh:

Vì thuật toán sắp xếp nhanh phân chia dãy số cần sắp xếp thành các phần nhỏ hơn, sau đó sắp xếp từng phần đó và kết hợp các phần đã sắp xếp lại thành dãy số đã được sắp xếp.

Câu 2: Theo em thì diễn biến từng bước sắp xếp nhanh một dãy số cụ thể dùng phân đoạn Lomuto sẽ giống hay sẽ khác với dùng phân đoạn Hoare?

Giải nhanh:

Diễn biến từng bước sắp xếp nhanh một dãy số cụ thể dùng phân đoạn Lomuto sẽ khác với dùng phân đoạn Hoare. Sự khác biệt là ở việc chọn pivot, cách phân đoạn và cách sắp xếp các phần tử.