Đề thầy cho:
Cho dãy có n bản ghi {X(1),...,X(n) trong mỗi bản ghi đều có trường dữ liệu k nhận 1 trong 3 giá trị {1, 2, 3}
Xây dựng thuật toán thuộc O(n) để sắp xếp X thành dãy không giảm theo k.
[You must be registered and logged in to see this image.]
Lời giải của Phan Thị Hải:
Proc SX (X: Dãy);
1) i = 1; j = n;
2). WHILE i ≤ j DO
          a)WHILE ((i ≤ j) & X(i).k = 1) DO i = i + 1;
          b)WHILE ((i ≤ j) & X(i).k ≠ 1) DO j = j - 1;
          c) IF i < j THEN swap (Xi, Xj);
3) j = n;
4) WHILE i ≤ j DO
          a) WHILE ((i ≤ j) & X(i).k = 2) DO i = i + 1;
          b) WHILE ((i ≤ j) & X(i).k ≠ 2) DO j = j - 1;
          c) IF i < j THEN swap (Xi, Xj);
5) Output (X)

*Độ phức tạp O(n)

Cách giải quyết bài toán của đ/c Hồng là triệt để, nhưng tôi nghĩ rằng trong khi thi có thể mình không thể nhớ hết các cách giải để tối ưu. Tôi nghĩ rằng cách giải sau đây có thể chấp nhận được và ăn điểm, các đ/c cho ý kiến:

Procedure SapXep(X: dãy số, n: integer)
1. Khai báo các mảng A, B, C có n phần tử;
m := 1; n := 1; q := 1;
2. For i := 1 to n do
          Case X(i).k of
                    1 : A(m) = X(i); m++;
                    2 : B(n) = X(i); n++;
                    3 : C(q) = X(i); q++;
3. m --; n --; q--;
4. For i := 1 to n do
                    If i <= m then X(i) := A(i);
                    If ( i > m ) and (i <= m + n) then X(i) := B(i - m);
                    If i > m + n then X(i) : = C(i - m - n);
5. Output X;

Thuật toán này có độ phức tạp O(n). Nhưng chúng ta sử dụng tốn bộ nhớ một tí. Thực ra với thời đại máy tính hiện nay, việc sử dụng bộ nhớ không là vấn đề gì, miễn là chương trình của ta chạy luột là được. Tôi nghĩ rằng phương án này chấp nhận được và ăn điểm.

Admin: Không biết tôi sửa lại cấu trúc có đúng ý đ/c Đạt không. Khi soạn bài hoặc sửa bài viết cần chú ý:
[You must be registered and logged in to see this image.]
ForumSystem sẽ tự thay thành các dấu cách. Mỗi chữ trên bằng 1 tab.

Tôi thấy cách giải của đ/c Đạt là cũng được, độ phức tạp của thuật toán là O(n). Với cách giải này chúng ta cũng nên cần hỏi lại ý kiến của thầy Tĩnh xem thế nào.

Tôi không có ý kiến gì về cách giải của cả 2 đ/c. về cách giải của đ/c Đạt thì có thể thấy ngay độ phức tạp của thuật toán. Còn về cách giải của đ/c Hồng, đồng ý là độ phức tạp O(n) nhưng có đ/c nào đánh giá thuật toán cụ thể hơn được k?

Chỉ xét ví dụ về vòng while này nhé

2. while i <= j do
          a. while (X(i).k = 1) do i = i+1;
          b. while (X(j).k ≠ 1) do j = j-1;
          c. if i < j then swap (Xi, Xj);



- số lần đổi chỗ lớn nhất n/2 → bỏ qua câu lệnh 2c

- Số phép cộng, trừ là n

- Số phép so sánh: Đây là sự dịch chuyển tương đối của i và j lại gần nhau, để dễ hình dung, ta coi j đứng yên (j=n, i chạy từ 1 → n) (trong trường hợp j-- (của câu lệnh 2b), ta sẽ chuyển thành là i++ (của câu lệnh 2a)), rõ ràng số phép so sánh sẽ là 2n.

- Tổng cộng lại là 7n/2

@Phuong: sao lại bỏ qua 2c. Nếu có n/2 phép đổi chỗ thì trong câu lệnh 2c đã có n/2 phép so sánh và 3*n/2 phép gán rồi. Vả lại các vòng while có liên quan đến nhau, nếu chỉ xét 1 vòng while thì nói làm gì :)

1. Nếu không có điều kiện i ≤ j có thể xảy ra lỗi:
Nếu dãy X không chứa phần tử 1 sẽ dẫn đến lỗi Over Flow tức là phần tử vượt quá dãy
2. Điều này các bác nên chú ý cho các thuật toán khác nếu không sẽ bị trường hợp tương tự (Ví dụ : sắp xếp phân đoạn)
trong sách của thày cũng thiếu điều kiện này
Anh em cho ý kiến nhé!!

Bác Phương xem lại thuật toán của bác đi
- Bác nên xem lại ý kiến của em đã viết.
- Cái của Bác mà không có (i ≤ j) là đứt.

LeVanDat đã viết:Cách giải quyết bài toán của đ/c Hồng là triệt để, nhưng tôi nghĩ rằng trong khi thi có thể mình không thể nhớ hết các cách giải để tối ưu. Tôi nghĩ rằng cách giải sau đây có thể chấp nhận được và ăn điểm, các đ/c cho ý kiến:

Procedure SapXep(X: dãy số, n: integer)
1. Khai báo các mảng A, B, C có n phần tử;
m := 1; n := 1; q := 1;
2. FOR i := 1 TO n DO
CASE X(i).k OF
1 : A(m) = X(i); m++;
2 : B(n) = X(i); n++;
3 : C(q) = X(i); q++;
3. m --; n --; q--;
4. FOR i := 1 TO n DO
If i <= m then X(i) := A(i);
If ( i > m ) and (i <= m + n) then X(i) := B(i - m);
If i > m + n then X(i) : = C(i - m - n);
5. Output X;

Thuật toán này có độ phức tạp O(n). Nhưng chúng ta sử dụng tốn bộ nhớ một tí. Thực ra với thời đại máy tính hiện nay, việc sử dụng bộ nhớ không là vấn đề gì, miễn là chương trình của ta chạy luột là được. Tôi nghĩ rằng phương án này chấp nhận được và ăn điểm.

Đồng chí Đạt có cách giải khá đơn giản, dễ hiểu, hay, tuy nhiên đồng chí chú ý cách khai báo biến toàn cục với biến
cục bộ. Tôi thấy đồng chí có hai biến n trùng nhau đấy

keke, cái này mình cũng chỉ theo sách, mình cũng không lập trình nên không biết có lỗi hay không. Ngay cả sách Đỗ Xuân Lôi, trang 217 viết về thủ tục này cũng không thấy thêm điều kiện i ≤ j. Nếu mà xảy trường hợp lỗi như đ/c Son đã nói thì mình sẽ rút kinh nghiệm và lưu ý cho trường hợp này.
@Son: Nếu cái của mình đứt, sẽ nối lại. :)

He he! Đấy là em thấy thế thôi, còn đi thi người ta chắc không chặt chẽ lắm đâu.
Nhưng em nghĩ cẩn thận vẫn tốt hơn