Thuật toán sắp xếp chon

Module_Dk · July 23, 2016, 7:08am

//Cach mot.
int temp;
int n;
int A[100];
for (int i = 0; i < n - 1; i++) {
	for (int j = i + 1; j < n; j++) {
		if (A[i] > A[j]) {
			temp = A[i];
			A[i] = A[j];
			A[j] = temp;
		}
	}
}

// Cach hai.
int chisoMax, temp;
int n;
int A[50];
for (int i = 0; i < n - 1; i++) {
	chisoMax = i;
	for (int j = i + 1; j < n; j++) {
		if (A[j] > A[chisoMax]) {
			chisoMax = j;
		}
	}
	
       if (chisoMax != i) {
		temp = A[chisoMax];
		A[chisoMax] = A[i];
		A[i] = temp;
	}
}

Các bạn cho mình hỏi hai cách cài đặt cho thuật toán sắp xếp chọn trên, cách tốt hơn và nên sử dụng hơn.

Phong_Ky_Vo · July 23, 2016, 12:08pm

This post was flagged by the community and is temporarily hidden.

Module_Dk · July 23, 2016, 5:58pm

Mình biết độ phức tạp nếu tính theo tổng số phép so sánh và hoán vị thì 2 thằng như nhau nhưng không biết trên thực tế thì thằng hoán vị nhiều hay thằng so sánh nhiều sẽ nhanh hơn và tiết kiệm thời gian hơn. Vì nếu thời gian như nhau thì thuật một tốn ít biến hơn (do đó tiết kiệm không gian bộ nhớ hơn) nhưng mà tại sao mình thấy người ta lại dạy cách hai khi cài đặt seletion sort nhỉ?

Luu_Thanh_Vuong · July 24, 2016, 2:12am

Cái cách 1 là interchange sort còn cách 2 mới là selection sort chứ nhỉ
Cách nào nhanh hơn thì nhớ có đoạn clip so sánh giữa 2 cái sort này.

tntxtnt · July 24, 2016, 2:39am

cả 2 cách cùng là selection sort mà. Cách 2 bị xếp ngược (sửa lại đơn giản thay vì tìm chisoMax thì tìm chisoMin)

cách 1 swap tối đa 0.5n^2 lần, 1 lần swap là 3 lần gán, tổng cộng khoảng 1.5n^2 lần gán
cách 2 swap có n lần, nhưng gán max=... 0.5n^2 lần, như vậy có khoảng 0.5n^2 + 3n lần gán.
cả 2 cách vì là selection sort nên có cùng số lần so sánh

n càng lớn thì cách 1 gán càng nhiều hơn so với cách 2, ví dụ n=1000 thì cách 1 tốn tối đa 1.5 triệu phép gán, còn cách 2 chỉ tốn tối đa 503 ngàn phép gán. Chỉ cần thêm 1 biến phụ có 4 bytes mà giảm đi 1 triệu phép gán. Cách 2 tốt hơn chứ.

Ninh_Tien · July 24, 2016, 12:59am

ở trên có vẻ dễ hiểu hơn.

Module_Dk · July 24, 2016, 2:58am

Nếu thế thì mình thấy như vầy chính xác hơn:

Cách 1: Số lần so sánh: ~0.5n^2 và Số phép gán: ~1.5n^2. (The worst case)
Cách 2: Số lần so sánh: ~(0.5n^2 + n) và Số phép gán: ~(0.5n^2 + 4n). (The worst case)

Nếu coi phép so sánh và phép gán thời gian thực hiện là như nhau thì ta có:
Time (Cách 1) - Time (Cách 2) = ~(n^2 - 5n)

Dẫu sao thì với n lớn thì cách 1 vẫn lâu hơn cách 2 —> nên cài đặt cách 2 khi n lớn.
Nhưng cách 1 hơn cách 2 nếu n nhỏ vì thời gian cài đặt nhanh hơn và tiết kiệm không gian bộ nhớ hơn (Biến phụ chisoMax). --> nên cài đặt cách 1 khi n nhỏ.
(Về thời gian gõ và hoàn thiện chúng)

Nhưng mà tại sao người ta lại phân loại thành Interchange Sort và selection sort trong khi 2 thằng này đều là thuật selection sort nhỉ?

Tiện thể bạn nào cho mình biết cách tạo khung xám cho code với tìm mãi trên diễn đàn chẳng thấy đâu.

tntxtnt · July 24, 2016, 2:47am

really? Tiết kiệm 4 byte cũng tính là 1 ưu điểm à? Nếu 1 phần tử có thể ko phải là số nguyên, mà là 1 struct 100 byte thì sao? 1 mảng 10 phần tử cũng là 1000 byte rồi. Save 4 byte để sắp xếp 1000 byte thì tiết kiệm được chỗ nào… Rồi struct 1000 byte? struct 10k byte? 4 byte ở đây chả có nghĩa lý gì cả.

với lại n nhỏ n lớn thì trong 2 cách sắp xếp này chả liên quan gì tới tốc độ cách nào nhanh hơn cả. Làm sao biết n nhỏ thì cách 1 chạy nhanh hơn cách 2?? n nhỏ thì liên quan gì tới tốc độ cài đặt thuật toán…

Module_Dk · July 24, 2016, 2:59am

Ý mình ở đây là n nhỏ và lớn là trong 2 cách cài đặt này thôi chứ n mà lớn quá thì sẽ dùng thuật toán sắp xếp khác hiệu quả hơn.

Còn về thời gian cài đặt thì bạn thấy rõ ràng cách 1 giúp bạn gõ và hoàn thiện nó nhanh hơn cách 2.

Nếu bạn nói tới sắp xếp dữ liệu lớn như struct hay class thì vốn dĩ có thể linh hoạt hơn sử dụng thêm một mảng phụ lưu chỉ số rồi sắp xếp quả mảng phụ ấy vì việc đổi chỗ 2 class hay struct là điều không nên (Trường hợp chúng có con trỏ hoặc dữ liệu quá lớn).

Mình nghĩ thế bạn thấy thế nào tntxtnt.

tntxtnt · July 24, 2016, 3:05am

mảng phụ lưu chỉ số thì lại lòi ra vấn đề lớn nữa: O(n) bộ nhớ để sắp xếp. Nếu phần tử lớn thì người ta có xài con trỏ hết đó, swap con trỏ là được rồi, ko phải swap 100 byte đó đâu. Ví dụ chuỗi nếu xài cấp phát động char* s1 = new char[100] cho swap với char* s2 = new char[100], thì ko cần phải copy 100 ký tự từ s1 sang s2 và ngược lại, mà chỉ cần swap con trỏ s1 với s2 là được rồi.

Ý mình khi nói struct 100 byte có nghĩa là mảng truyền vào thực tế đã chiếm 1 lượng lớn bộ nhớ rồi, 4 byte thêm cho chisoMax chả có nghĩa gì cả. Thậm chí thêm 100 byte cũng chả có nghĩa lý gì, vì nó là O(1), nghĩa là khi n tăng thì số 100 ko có tăng theo. Còn thêm 4*n byte như cách tạo mảng phụ lưu chỉ số thì cái đó là ngốn O(n) bộ nhớ, rất tệ, n càng lớn thì ngốn bộ nhớ càng nhiều.

Phong_Ky_Vo · July 24, 2016, 3:13am

This post was flagged by the community and is temporarily hidden.

Module_Dk · July 24, 2016, 3:16am

Như vậy mình nghĩ nên lưu tâm vấn để kích thước của cái mình sắp xếp và swap để chọn thuật sắp xếp và mẹo sắp xếp cho phù hợp và cân bằng giữa thời gian chạy và bộ nhớ sử dụng.

Nhưng dẫu sao nếu kích thước swap hay sắp xếp mà nhỏ và cái 4 byte kia là đáng kể so với nó thì cũng đáng để cân nhắc cách 1 trong 2 cách ấy chứ nhỉ.

Module_Dk · July 24, 2016, 3:17am

Cũng được nhưng mình tính trung bình thì cx được rồi bạn.

tntxtnt · July 24, 2016, 3:25am

ko có đáng kể đâu. 4 byte chả có nghĩa lý gì, máy dỏm máy mới gì cũng vậy. Nỗi trong cách 1 cũng xài 2 int i, j là 8 byte rồi, cách 2 xài 12 byte thì hơn bao nhiêu? Dung lượng bộ nhớ tới GB, thêm 4 byte chết gì ai ~.~ Chừng nào dung lượng bộ nhớ là 8 byte thì mới có vấn đề, ko xài 12 byte được. Mà 8 byte thì sắp xếp cái gì.

đang troll 4 byte là đáng kể đáng cân nhắc đấy à? ~.~

Module_Dk · July 24, 2016, 3:31am

Ừm tại trước giờ mình cứ nghĩ càng tiết kiệm được bộ nhớ được thì càng tốt, vậy là chẳng sao thật cái nào dễ cài thì cài vào thôi.

Phong_Ky_Vo · July 24, 2016, 3:39am

This post was flagged by the community and is temporarily hidden.