Sort bằng đệ quy: Tại sao phải cần gọi lại hàm sort trong cái điều kiện if?

[davidteo]

void sort(int a[], int n)
{
	if (n == 1)return;
	else{
		sort(a, n - 1); 
		if (a[n - 1] < a[n - 2])
		{ 
			int temp = a[n - 1]; 
			a[n - 1] = a[n - 2];
			a[n - 2] = temp;
		**_**sort(a, n - 1);**_** 
		}
	}

}

sắp xếp n-1 phần tử xét phần tử cuối cùng nếu phần tử đứng trước nó thì hoán vị rồi sắp xếp lại n-1 phần tử trước đó.
Mình không hiểu tại sao phải cần gọi lại hàm sort trong cái điều kiện if.

[AI_Android]

để đảm bảo dồn được số bé nhất về phía trước.
Ví dụ: dãy 3 2 1
dãy theo thứ tự sẽ là:
2 3 1
2 1 3
1 2 3
nếu không có sort thì sẽ dừng lại khi dãy là : 2 1 3

[Gio (Gió)]

Code này bản chất là insert sort thôi. Nó sẽ sort từ đầu n=1 tới cuối. Nếu tại 1 đoạn nào đó có 1 phần tử thêm vào đoạn đã sort nhỏ hơn cuối if(a[n-1]<a[n-2])thì cần phải chèn vào và sort lại đoạn đó. Do đó mới có lệnh if ở và hàm sort trong if

[davidteo]

Đã hiểu. Thanks a…

[rogp10]

Lời gọi hàm bên ngoài if đóng vai trò của vòng lặp ngoài của insertion sort.

VD: [3, 1, 2]

sort(3) {
   sort(2) {
     sort(1) [1,3,2]|sort(1) 
   }
   [1,2,3]|sort(2) { sort(1) }
}

Mảng có 2 nghịch thế là (3, 1) và (3, 2). Mỗi lần swap giảm đi đúng 1 nghịch thế do các phần tử còn lại giữ nguyên vị trí so với a[n] và a[n-1]. Vậy số lần swap chính là số nghịch thế. Mỗi nghịch thế sinh ra O(n) lời gọi đệ quy nên code trên có độ phức tạp O(n^3) (!), hay T(n) = n + V * O(n) lời gọi.

Chính xác hơn, xét v[m] là số nghịch thế trái vị trí m, hay (i, m) i < m. Mỗi lần swap hủy bỏ một nghịch thế vị trí m, vậy T(n) = n + sigma(i=0…n-1)(v[i] * i). Như ở trên là 6 lời gọi.