Hướng dẫn giải nhanh 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

KHỞI ĐỘNG

Câu hỏi: 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.

Trả lời:

Nếu mục tiêu của em là thực hiện một thuật toán cụ thể và xây dựng một chương trình Python thực hiện nó, thì em nên chọn làm việc này. Viết chương trình Python từ mô tả thuật toán sẽ giúp em nắm vững cách thực hiện thuật toán, hiểu rõ logic và cách hoạt động của nó. Điều này có ích khi em cần phải thực hiện thuật toán trong thực tế và muốn kiểm tra chính xác cách mà thuật toán hoạt động.

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.

Trả lời:

a) Viết chương trình thực hiện sắp xếp nhanh một dãy số dựa trên mã lệnh thuật toán cho trong Hình 3 và chạy thử kiểm tra.

b) Viết chương trình thực hiện sắp xếp nhanh một dãy số dựa trên mã lệnh thuật toán cho trong Hình 5 và chạy thử kiểm tra.

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ố.

Trả lời:

- Câu lệnh bổ sung: 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.

Trả lời:

a) Gợi ý 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:

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 ý 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:

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ị”.

Trả lời:

- Thuật toán QuickSort thực hiện việc sắp xếp dãy số bằng cách áp dụng chiến lược "chia để trị", tức là nó tách dãy số ban đầu thành các phần nhỏ hơn, sau đó sắp xếp từng phần này, và sau cùng kết hợp các phần đã sắp xếp để tạo ra dãy số đã được sắp xếp.

- Cụ thể, thuật toán QuickSort chia dãy số ban đầu thành hai phần dựa trên một phần tử gọi là pivot. Các phần tử nhỏ hơn pivot được di chuyển vào bên trái pivot, trong khi các phần tử lớn hơn pivot được đưa vào bên phải pivot. Tiếp theo, thuật toán được áp dụng đệ quy lên từng phần con của dãy số này cho đến khi các phần con chỉ chứa một phần tử duy nhất. Cuối cùng, các phần đã sắp xếp lại được kết hợp với nhau để tạo ra dãy số đã được sắp xếp.

- Chiến lược "chia để trị" của QuickSort giúp giải quyết các vấn đề lớn bằng cách chia chúng thành các vấn đề nhỏ hơn, giúp tối ưu hóa quá trình sắp xếp và làm cho thuật toán trở nên hiệu quả hơn.

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?

Trả lời:

- Quá trình thực hiện thuật toán QuickSort trên một dãy số cụ thể sử dụng phân đoạn Lomuto sẽ có sự khác biệt so với việc sử dụng phân đoạn Hoare. Sự khác biệt này xuất phát từ việc lựa chọn pivot, cách thực hiện phân đoạn và cách sắp xếp các phần tử trong thuật toán QuickSort.

- Cụ thể, phương pháp phân đoạn Lomuto sẽ lựa chọn pivot là phần tử cuối cùng của mảng, sau đó thực hiện phân đoạn dãy số dựa trên pivot và đưa pivot về giữa hai phân đoạn tạo ra. Sau đó, thuật toán QuickSort được áp dụng đệ quy lên hai phân đoạn bên trái và bên phải của pivot. Trong khi đó, phương pháp phân đoạn Hoare sẽ lựa chọn pivot là phần tử ở giữa của mảng, sau đó sử dụng hai con trỏ xuất phát từ đầu và cuối mảng để di chuyển và phân đoạn dãy số theo pivot. Điều quan trọng là phần tử bên trái pivot phải lớn hơn pivot và phần tử bên phải pivot phải nhỏ hơn pivot. Sau đó, pivot được đưa vào vị trí mới và thuật toán QuickSort tiếp tục thực hiện trên hai phân đoạn bên trái và bên phải của pivot.