Hướng dẫn mô tả thuật toán sắp xếp tráo đổi

TIN HỌC GIÁ RAI 6:05:00 AM Tin học 10

1. Xác định bài toán - Input: Dãy A gồm N số nguyên a1, a2,..., aN. - Output: Dãy A được sắp xếp lại thành dãy không giảm. 2. Thuật toán

1. Cách liệt kê B­ước 1. Nhập N, các số hạng a1, a2,…, aN; B­ước 2. M := N; B­ước 3. Nếu M < 2 thì đưa ra dãy A đã được sắp xếp rồi kết thúc; B­ước 4. M := M – 1, i := 0; B­ước 5. i := i + 1; B­ước 6. Nếu i > M thì quay lại bước 3; B­ước 7. Nếu ai > ai+1 thì tráo đổi ai và ai+1 cho nhau; B­ước 8. Quay lại bước 5.

Related Posts

Tin học 10

Post a Comment

Sắp xếp là quá trình bố trí lại các phần tử trong một tập hợp theo một trình tự nào đó nhằm mục đích giúp quản lý và tìm kiếm các phần tử dễ dàng và nhanh chóng hơn.

Tại sao phải sắp xếp?

• Để có thể sử dụng thuật toán tìm nhị phân
• Để thực hiện thao tác nào đó được nhanh hơn

Các phương pháp sắp xếp thông dụng:

• Phương pháp Đổi chỗ trực tiếp [Interchange sort]
• Phương pháp Nổi bọt [Bubble sort]
• Phương pháp Chèn trực tiếp [Insertion sort]
• Phương pháp Chọn trực tiếp [Selection sort]

Interchange Sort

Khái niệm nghịch thế:

• Xét một mảng các số a[0], a[1], … a[n-1]
• Nếu có i a[j], thì ta gọi đó là một nghịch thế

Mảng chưa sắp xếp sẽ có nghịch thế

Mảng đã có thứ tự sẽ không chứa nghịch thế

a[0]