Hỏi bài tập sắp xếp

[fingtogo]

Ừm hồi xưa đi học gặp bài này khó mà chưa có cách giải chuẩn, ở trên đây có nhiều cao thủ em post lên hỏi, mong mọi người cùng bàn luận. Khuyến cáo trước là cái này ý tưởng thì cũng có nhiều nhưng mà nếu ai có ý tưởng thì... thử lập trình đã nhá, vì nó khó thật đó!
Đề: "Cho một mảng n phần tử (nhập vào hay lấy từ file cũng được), chỉ có phép đổi chỗ hai phần tử khác nhau trong mảng. Hãy sắp xếp lại mảng theo thứ tự tăng dần sao cho số bước đổi chỗ là ít nhất.
Input: array.int
dóng: n
n dòng tiếp mỗi dòng một số (số nguyên thôi cho đỡ dữ liệu)
Output: array.out
dòng 1: số bước đổi chỗ
các dòng tiếp là các bước đổi chỗ: gồm hai số thứ tự cách nhau một dấu cách
vídu;
vào:
3
2
2
1
ra
1
1 3

Mọi người cùng vào bàn luận nha!

[scooby]

Bàn luận cái gì? Đây là bài sắp xếp cơ bản.

Nếu dữ liệu bạn có gì đặc biệt thì mới đáng nói, còn nếu không cứ áp dụng các thuật toán cơ bản.

[fingtogo]

Bàn luận cái gì? Đây là bài sắp xếp cơ bản.

Nếu dữ liệu bạn có gì đặc biệt thì mới đáng nói, còn nếu không cứ áp dụng các thuật toán cơ bản.

Đọc kĩ đề đi bạn!
Đề không chỉ yêu cầu sắp xếp, mà sắp xếp sao cho số bước đổi chỗ là ít nhất đó, chứ không thì post nên đây làm gì?
Mời mọi người cho ý kiến!

[scooby]

Cái này là kiến thức cơ bản. Một thuật toán sx nhanh/chậm hơn thuật toán sx khác chính là tính dựa trên số lần so sánh và số lần đổi chỗ. Giở bất cứ quyển sách giải thuật nào ra bạn sẽ thấy các con số đi kèm với từng giải thuật. Quick Sort luôn có số lần đổi chỗ là ít nhất (nhanh nhất).

Nếu dữ liệu của bạn chẳng có qui luật gì đặc biệt thì chỉ cần áp dụng thuật toán cơ bản là đủ. Phần lớn sách giải thuật cũng có đủ lý luận tại sao lại như vậy.

[_River_]

Chắc bác đó mới "phát minh" ra giải thuật nào mới nên tí tửng hỏi thử đấy!

[quynhlan]

Ừm hồi xưa đi học gặp bài này khó mà chưa có cách giải chuẩn, ở trên đây có nhiều cao thủ em post lên hỏi, mong mọi người cùng bàn luận. Khuyến cáo trước là cái này ý tưởng thì cũng có nhiều nhưng mà nếu ai có ý tưởng thì... thử lập trình đã nhá, vì nó khó thật đó!
Đề: "Cho một mảng n phần tử (nhập vào hay lấy từ file cũng được), chỉ có phép đổi chỗ hai phần tử khác nhau trong mảng. Hãy sắp xếp lại mảng theo thứ tự tăng dần sao cho số bước đổi chỗ là ít nhất.
Input: array.int
dóng: n
n dòng tiếp mỗi dòng một số (số nguyên thôi cho đỡ dữ liệu)
Output: array.out
dòng 1: số bước đổi chỗ
các dòng tiếp là các bước đổi chỗ: gồm hai số thứ tự cách nhau một dấu cách
vídu;
vào:
3
2
2
1
ra
1
1 3

Mọi người cùng vào bàn luận nha!

QL nghĩ trước hết nên tìm cách giải cho 1 trường hợp riêng: mảng là hoán vị các giá trị của khoảng 1..N (hoặc 0..N-1). Có thể dựng hoán vị này bằng cách dựng dần từng chu trình của nó, trong đó chu trình độ dài K được thực hiện bằng K-1 hoán vị cặp phần tử. Kết quả sẽ là chuỗi có không quá N-1 hoán vị cặp phần tử. Nhưng QL không rõ chuỗi này có phải là chuỗi ngắn nhất hay không.

[fingtogo]

Chắc bác đó mới "phát minh" ra giải thuật nào mới nên tí tửng hỏi thử đấy!

Ài, đây không phải là bài toán sắp xếp, vì nếu thế thì có khoảng chục thuật toán rồi mà ai cũng được học cả!
Đã nói là dùng số lần đổi chỗ ít nhất rồi mà, các bác lại không chịu đọc kĩ, vì dùng số lần đổi chỗ ít nhất nên dùng các thuật toán cơ bản làm sao kiểm soát nổi các test khác nhau?
QS trong bài này gần như là cách tệ nhất!
Ý nói ở đây là thuật toán (ah có lẽ giải thuật thì đúng hơn) in ra số lần đổi chỗ ít nhất thỏa mãn thôi chứ không phải quan tâm tới thời gian chạy chương trình là tối ưu.

@Ql: Bạn có thể nói rõ hơn không, hay là bạn đưa ra một test nhỏ là rõ ý nhất!

PS: Ngày xưa đi học, thầy (là giáo sư DHQG về dạy một tuần) đưa ra đề nhưng không đưa ra cách giải, test của thầy lớn, thầy tổng hợp tất cả các bài làm của học sinh lại, với mỗi test thì lấy bài tối ưu nhất của học sinh trong từng test đó coi như đáp án chuẩn, nhưng như thế thì không đúng!

[quynhlan]

@Ql: Bạn có thể nói rõ hơn không, hay là bạn đưa ra một test nhỏ là rõ ý nhất!

QL cũng mới chỉ có ý tưởng chứ chưa có thuật toán. Nói rõ hơn như thế này:

Ví dụ. Gọi A(0) là giá trị ban đầu (chưa sắp thứ tự) của mảng, A(7) là giá trị cuối cùng (đã sắp thứ tự) của mảng.

A(7):  0 1 2 3 4 5 6 7 8 9
A(0):  2 9 3 4 6 5 7 8 0 1

Ta thấy A(0) thực chất là một hoán vị có 3 chu trình:

5 -> 5
(5 biến thành 5)

1 -> 9 -> 1
(1 biến thành 9, 9 biến thành 1)

0 -> 2 -> 3 -> 4 -> 6 -> 7 -> 8 -> 0
(0 biến thành 2, 2 biến thành 3,..., 8 biến thành 0)

Chu trình thứ nhất có độ dài 1 và được thực hiện mà không cần hoán vị cặp phần tử nào. Chu trình thứ hai có độ dài 2 và được thực hiện bằng 1 hoán vị cặp phần tử (1 và 9). Chu trình thứ ba có độ dài 7 và được thực hiện bằng 6 hoán vị cặp phần tử. Tổng cộng ta cần 0 + 1 + 6 = 7 hoán vị cặp phần tử để dựng được A(0) từ A(7), hay dựng A(7) từ A(0).

[scooby]

Thế nào rồi? Mấy bác này định phát minh lại bánh xe mà bỏ bẵng topic này rồi à?

[quynhlan]

Thế nào rồi? Mấy bác này định phát minh lại bánh xe mà bỏ bẵng topic này rồi à?

Có thể bạn ấy giải quyết xong rồi, cũng có thể chưa xong. Có thể vấn đề chỉ là cái bánh xe đối với người này nhưng là phát minh đối với người khác. Phát minh lại bánh xe cũng chả làm sao cả, nó vẫn có ích.

Cái này là kiến thức cơ bản. Một thuật toán sx nhanh/chậm hơn thuật toán sx khác chính là tính dựa trên số lần so sánh và số lần đổi chỗ. Giở bất cứ quyển sách giải thuật nào ra bạn sẽ thấy các con số đi kèm với từng giải thuật. Quick Sort luôn có số lần đổi chỗ là ít nhất (nhanh nhất).

Đây không phải là bài toán sắp xếp. QuickSort không phải là nhanh nhất trong các thuật toán sắp xếp chỉ so sánh, và trong các thuật toán sắp xếp nói chung thì lại càng tệ hơn. Rõ ràng là bạn không hiểu bài toán này, và bạn cũng thiếu kiến thức căn bản về các thuật toán căn bản. Vậy đừng nhận định nữa.