30/09/2018, 19:08
Trộn mảng Giảm Dần từ 2 mảng lộn xộn. không sắp xếp
Ý tưởng:
na,nb số phần tử của A và B
i : Biến đếm
-Copy mảng A,B ban đầu sang mảng C,D.
-Tạo Mảng H[na+nb-1]
-
lặp {
1.Tìm max của A,B-> so sánh rồi sắp vào H theo thứ tự giảm dần.
VD: C[max}=2 và D[max]=3 => H[i]=D[max]; H[i+1]=C[max];
xóa c[max], d[max].
tăng i lên 2,lặp đến khi một trong hai mảng hết phần tử
-sắp tiếp phần tử của mảng còn lại vào H theo nguyên tắc chon phần tử lớn nhất, xóa phần tử lớn nhất ấy đi.
.
Ý tưởng 2: tạo một mảng bool đánh dấu phần tử đã trộn vào H theo nguyên tắc trên => không cần xóa phần tử và không cần copy sang mảng C,D.
Xin các bro cho ý kiến để tối ưu ý tưởng ạ.
EDITED:
Thuật toán trên sai bét… =)
chắc ý của ông thầy là không sắp xếp = thuật toán sắp xếp nổi bọt hay đổi chổ trực tiếp. Tại ông cho đề cho các bạn SV năm nhất trình nhập môn (có mình)
Bài liên quan
cái kiểu tìm phần tử lớn nhất ấy thì khác gì selection sort đâu. Bảo “không sắp xếp” mà trộn được thành mảng sắp xếp theo thứ tự thì làm sao được. Phải có sắp xếp ở đâu đó chứ ~.~
hơn nữa kiểu trộn trên cũng ko ổn: ví dụ mảng A là 10 11 12 13, mảng B là 1 2 3 4 thì theo cách trộn trên sẽ cho ra 13 4 12 3 11 2 10 1 => ko giảm dần
mình xin đánh gía thuật toán này 1 chút:
1, công việc copy mảng A, B sang C,D có độ phức tạp O(n)
2, tìm max A, B là O(n)
3, cái vòng lặp của bản phức tạp O(n^2)
về ý tưởng thì đây chính là selection sort, thậm chí còn không tối ưu bằng.
với bài này mình nghĩ có thể dùng merge sort vì có sẵn 2 mảng ban đầu.
còn để tối ưu thuật toán của bạn:
gộp mảng A,B thành C;
sử dụng selection sort để sắp xếp C.
Thanks pro… thông não ra rồi =))
Ý của thầy của bạn là dùng Merger Sort.
sao đen thế không biết , trường minh cũng ra bài này làm bài cuối kì :3 , ai giúp cái
Dùng merge sort ý bạn. Từ 2 mảng đã sắp xếp trộn thành 1 mảng đã sắp xếp. Mà thực ra trình độ sinh viên năm nhất ở trường mình thì không cho đề thi viết merge đâu, mình mất 1 tiếng giảng cho thằng bạn nó mới hiểu bản chất của bubble, rồi nó viết code còn sai loằng ngoằng nữa
Thực ra Selection Sort viết đúng hiểu đúng (chỉ swap N lần mới là viết đúng) còn xài được (không bằng Cycle Sort) chứ Bubble fail so với Insertion.
Bubble quá ẹ cả về tư tưởng và hiệu năng.