Gọi đệ quy trong Merge Sort

#1

Em có thắc mắc về cách mảng được chia nhỏ để giải thuật:

void MergeSort(int a[], int left, int right)
{
	if (right > left){
		int mid; // Phan tu o giua
		mid = (left + right) / 2;
		MergeSort(a, left, mid); // Goi de quy mang con ben trai
		MergeSort(a, mid + 1, right); // Goi de quy mang con ben phai
		Merge(a, left, mid, right); // Goi ham so sanh hai mang con
	}
}

Các anh chị cho em hỏi: sau mỗi lần gọi đệ quy thì mảng con sẽ được chia như thế chi tiết như thế nào?
VD: mảng A = {3,5,1,4,7,2,44,66,33,11} ( 10 phan tur → mid = 4)
gọi MergeSort(a, left, mid) được {3,5,1,4,7} → {3,5,1} → {3,5} → 3
gọi MergeSort(a, mid + 1, right) sẽ bắt đầu chạy từ mảng nào ? phần mảng con bên phải là {2,44,66,33,11}, {4,7} của {3,5,1,4,7} là sẽ chạy kiểu gì khi mid, right đã thay đổi?[details=Summary]This text will be hidden[/details]

#2

Format code bằng cách thêm 3 dấu ` vào đầu và cuối code, như thế này:

// code

#3

Các hàm chưa xử lí sẽ được đưa vào stack. Mình không biết giải thích thế nào, nhưng mà chương trình sẽ lần lượt xử lí những hàm được gọi 1 cách đầy đủ.

Để hiểu rõ xem chương trình chạy như thế nào, bạn in ra giá trị left và right ở đầu void để tìm hiểu cách hoạt động của nó.

void MergeSort(int a[], int left, int right) {
    printf("%d %d\n", left, right);
    if (right > left) {
        // code...
    }
}
#4

Thực ra hãn hữu lắm mới phải tìm hiểu thuật toán qua code :smiley: giờ có điều kiện bạn nên tìm hiểu ý tưởng của nó “chia để trị”.

1 Like
#5

cách chia nhỏ mảng và giải thuật thì không khó hiểu, chỉ đoạn gọi đệ quy là mình không hiểu nó chạy kiểu gì thôi… chứ sao khi chia nhỏ mảng còn 1 phần tử rồi trộn thì mình hiểu rồi

#6

Thế thì bạn nên tìm hiểu về cách các hàm đệ quy hoạt động 1 cách chi tiết.

#7

Mình thấyngoài cách chạy tay còn có:

  • Vẽ tay: vẽ ngay một cái thân cây với gốc là dãy a[] ban đầu. Nhánh bên trái ứng với nửa mảng bên trái, nhánh bên phải ứng với nửa mảng bên phải. Giờ bạn đi hết nhánh bên trái cho đến khi gặp cành cụt, rồi quay đầu lại và chọn một nhánh khác. Khi cả hai nhánh đều được chọn, vẽ một bông hoa lên chỗ giao cắt, rồi quay lại chọn nhánh khác.
1 Like
#9

Mình thấy nói vầy chuẩn hơn: tới [3] thì cùng, quay đầu lại, tạt ngang qua [3, 5] rồi xuống [5]. Hai nhánh đã xong nên quay đầu lại và giờ mới dừng ở [3, 5]. Đánh dấu ở đây.

Giờ đi ngang qua [3, 5, 6] xuống [6] là hết, trở đầu dừng lại ở [3, 5, 6]; đánh dấu.

Theo ngôn ngữ của đồ thị, bạn phải thăm hết hai nhánh chính rồi mới xử lí cái gốc.

1 Like
#11

Hi Xuân Trung.
Khi bạn gọi hàm thì các biến trong hàm được khởi tạo nên các biến a, left, right trong mỗi hàm là các biến khác nhau. Tương tự với khối lệnh.

VD:

int a = 10;
{
    int a = 100;
    cout << a << endl; //In ra 100.
}
cout << a << endl; //In ra 10.
#13

Hi Xuân Trung.
Mình không rõ ý bạn lắm ???
trộn các mảng con 1 ptu từ dưới lên chứ nhỉ?

#14

#15

Hi Xuân Trung.
Do bạn gọi MergeSort (Mũi tên chia ra) hai mảng con rồi mới gọi Merge (Mũi tên gộp lại.)

#17

Hi Xuân Trung.
Bạn truyền vào left; mid và mid + 1; right mà. @_@!

P/S Chạy DEBUG xem.

1 Like
#18

thì đó… ý mình muốn hỏi là khi nó tách ra đến chỗ 38,27 thì hàm đệ quy sẽ chạy tiếp đến mảng nào để tách tiếp… và khi tách đến hết (chỗ 9, 82) thì nó sẽ có giá trị left, right → mid của mảng 9, 82 rồi truyền vô hàm merge phải ko ? nếu thế thì nó lấy left,right ở đâu để trộn bọn mảng bên trái (27, 38, 3, 43)…

#19

Hi Xuân Trung.
Bạn thử debug và xem giá trị các biến thay đổi cũng như các lệnh được gọi xem.

#20

Viết ra các stack frame (left + right + mid) cũng được. Chỉ cần nhớ mỗi lời gọi là push một stack frame và quay về là pop.

1 Like
#21

cảm ơn anh chị đã giải đáp… em đã hiểu toàn bộ cách hàm đệ quy & cách thuật toán chạy lần lượt rồi…

#22

Hi Xuân Trung.
Bạn thử giải thích lại cho mọi người làm tài liệu sau này dẫn link được không ???

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?