30/09/2018, 22:27
Thuật toán sắp xếp chon
//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;
}
}
Các bạn cho mình hỏi hai cách cài đặt cho thuật toán sắp xếp chọn trên, cách tốt hơn và nên sử dụng hơn.
Bài liên quan
This post was flagged by the community and is temporarily hidden.
Mình biết độ phức tạp nếu tính theo tổng số phép so sánh và hoán vị thì 2 thằng như nhau nhưng không biết trên thực tế thì thằng hoán vị nhiều hay thằng so sánh nhiều sẽ nhanh hơn và tiết kiệm thời gian hơn. Vì nếu thời gian như nhau thì thuật một tốn ít biến hơn (do đó tiết kiệm không gian bộ nhớ hơn) nhưng mà tại sao mình thấy người ta lại dạy cách hai khi cài đặt seletion sort nhỉ?
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.
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)
max=...0.5n^2 lần, như vậy có khoảng 0.5n^2 + 3n lần gán.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ứ.
ở trên có vẻ dễ hiểu hơn.
Nếu thế thì mình thấy như vầy chính xác hơn:
Cách 1: Số lần so sánh: ~0.5n^2 và Số phép gán: ~1.5n^2. (The worst case)
Cách 2: Số lần so sánh: ~(0.5n^2 + n) và Số phép gán: ~(0.5n^2 + 4n). (The worst case)
Nếu coi phép so sánh và phép gán thời gian thực hiện là như nhau thì ta có:
Time (Cách 1) - Time (Cách 2) = ~(n^2 - 5n)
Dẫu sao thì với n lớn thì cách 1 vẫn lâu hơn cách 2 —> nên cài đặt cách 2 khi n lớn.
Nhưng cách 1 hơn cách 2 nếu n nhỏ vì thời gian cài đặt nhanh hơn và tiết kiệm không gian bộ nhớ hơn (Biến phụ chisoMax). --> nên cài đặt cách 1 khi n nhỏ.
(Về thời gian gõ và hoàn thiện chúng)
Nhưng mà tại sao người ta lại phân loại thành Interchange Sort và selection sort trong khi 2 thằng này đều là thuật selection sort nhỉ?
Tiện thể bạn nào cho mình biết cách tạo khung xám cho code với tìm mãi trên diễn đàn chẳng thấy đâu.
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…
Ý mình ở đây là n nhỏ và lớn là trong 2 cách cài đặt này thôi chứ n mà lớn quá thì sẽ dùng thuật toán sắp xếp khác hiệu quả hơn.
Còn về thời gian cài đặt thì bạn thấy rõ ràng cách 1 giúp bạn gõ và hoàn thiện nó nhanh hơn cách 2.
Nếu bạn nói tới sắp xếp dữ liệu lớn như struct hay class thì vốn dĩ có thể linh hoạt hơn sử dụng thêm một mảng phụ lưu chỉ số rồi sắp xếp quả mảng phụ ấy vì việc đổi chỗ 2 class hay struct là điều không nên (Trường hợp chúng có con trỏ hoặc dữ liệu quá lớn).
Mình nghĩ thế bạn thấy thế nào tntxtnt.
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.
This post was flagged by the community and is temporarily hidden.
Như vậy mình nghĩ nên lưu tâm vấn để kích thước của cái mình sắp xếp và swap để chọn thuật sắp xếp và mẹo sắp xếp cho phù hợp và cân bằng giữa thời gian chạy và bộ nhớ sử dụng.
Nhưng dẫu sao nếu kích thước swap hay sắp xếp mà nhỏ và cái 4 byte kia là đáng kể so với nó thì cũng đáng để cân nhắc cách 1 trong 2 cách ấy chứ nhỉ.
Cũng được nhưng mình tính trung bình thì cx được rồi bạn.
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 à? ~.~
Ừm tại trước giờ mình cứ nghĩ càng tiết kiệm được bộ nhớ được thì càng tốt, vậy là chẳng sao thật cái nào dễ cài thì cài vào thôi.
This post was flagged by the community and is temporarily hidden.