Soạn Tin học 11 Cánh Diều Bài 9: Lập trình thuật toán sắp xếp nhanh (trang 127, 130)

Hướng dẫn Soạn Tin học 11 Cánh Diều Bài 9: Lập trình thuật toán sắp xếp nhanh (trang 127, 130) ngắn gọn, hay nhất theo chương trình Sách mới.

Bài 9: Lập trình thuật toán sắp xếp nhanh

Lý thuyết Tin học 11 Cánh Diều Bài 9: Lập trình thuật toán sắp xếp nhanh

Sơ đồ tư duy Tin học 11 Cánh Diều Bài 9 Chủ đề FCs: Lập trình thuật toán sắp xếp nhanh

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

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);

}

}

2. 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:

- Nói thuật toán sắp xếp nhanh (QuickSort) theo chiến lược “chia để trị” vì thuật toán này được 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ụ thể:

+ Thuật toán QuickSort chia dãy số cần sắp xếp thành hai phần dựa trên một phần tử gọi là pivot. Tất cả các phần tử lớn hơn pivot được đưa về bên phải, còn các phần tử nhỏ hơn pivot được đưa về bên trái pivot. Sau đó, áp dụng thuật toán đệ quy cho từng phần của dãy cho đến khi phần con chỉ còn một phần tử. Cuối cùng, các phần được sắp xếp lại với nhau để tạo ra dãy số đã sắp xếp. 

3. 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:

- 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 này ở ở phương phương pháp phân đoạn Lomuto và phân đoạn Hoare trong thuật toán QuickSort (bao gồm việc chọn pivot, cách phân đoạn và cách sắp xếp các phần tử).

>>> Xem toàn bộ: Soạn Tin 11 Cánh diều

-------------------------------------

Trên đây Toploigiai đã cùng các bạn Soạn Tin học 11 Cánh Diều Bài 9: Lập trình thuật toán sắp xếp nhanh trong bộ SGK Cánh Diều theo chương trình sách mới. Chúng tôi hi vọng các bạn đã có kiến thức hữu ích khi đọc bài viết này. Click vào trang chủ Toploigiai để tham khảo và chuẩn bị bài cho năm học mới nhé. Chúc các bạn học tốt!