Bài 8. Lập trình một số thuật toán sắp xếp SVIP

1. Bài toán sắp xếp

Thuật ngữ sắp xếp đề cập đến việc tổ chức lại một tập hợp dữ liệu theo một tiêu chí sắp xếp (đáp ứng tiêu cầu về cụ thể về trình tự).

⚡Ví dụ. Cho dãy số, yêu cầu sắp xếp "theo thứ tự tăng dần (giảm dần)".

- Đầu vào: Dãy n số a₀, a₁,..., a_n-1

- Đầu ra: Dãy được sắp xếp theo thứ tự tăng dần (giảm dần).

Sắp xếp tại chỗ và không tại chỗ

Sắp xếp tại chỗ khi không phải dùng thêm một dãy khác ở bên ngoài dãy ban đầu để thực hiện sắp xếp (chỉ đổi chỗ các phần tử trong dãy ban đầu).

Nếu sử dụng một dãy khác ở bên ngoài dãy ban đầu để chứa kết quả thì gọi là sắp xếp không tại chỗ.

Nghịch thế

Nếu i < j mà a_i > a_j thì cặp hai phần tử (a_i, a_j) gọi là một nghịch thế. Dãy số chưa sắp đúng thứ tự khi còn ít nhất một nghịch thế.

2. Thuật toán sắp xếp nổi bọt

Kí hiệu thể hiện thao tác đổi chỗ khi có nghịch thế.

Khi duyệt thêm một lượt nhưng không tìm thấy cặp nghịch thế nào → dùng biến logic True hoặc False lưu vết tùy theo có xảy ra đổi chỗ hay không.

3. Thuật toán sắp xếp chèn tuyến tính

Mô tả các bước của thuật toán:

Bước 0. i ← 1;

Bước 1.

if i ≥ n: kết thúc;

else: val ← a_i; k ← i - 1;

Bước 2.

if k ≥ 0:

if a_k > val: a_k+1 ← a_k; k ← k - 1; đến Bước 2;

Bước 3. a_k+1 ← val; i ← i + 1; đến Bước 1;