Hoán đổi và chia nhỏ bài toán

**Hoán đổi** hai giá trị là làm cho mỗi vị trí nhận giá trị ban đầu của vị trí kia. Giả sử A giữ 12, B giữ 7. Sau hoán đổi, A cần giữ 7 và B giữ 12, không làm mất một trong hai số. Nếu cho A nhận 7 trước mà chưa giữ số 12 ở đâu, thì cả A và B đều giữ 7; số 12 ban đầu ở A không còn để đưa sang B. Ta dùng một chỗ lưu tạm T: | Bước | A | B | T | |---|---|---|---| | Ban đầu | 12 | 7 | Trống | | Giữ A vào T | 12 | 7 | 12 | | Cho A nhận B | 7 | 7 | 12 | | Cho B nhận T | 7 | 12 | 12 | Chỗ lưu tạm giúp giữ giá trị 12 trong lúc A được thay bằng 7. Khi dùng thẻ giấy, có thể đổi vị trí hai thẻ trực tiếp; bảng trên giải thích cách giữ dữ liệu khi phải thay giá trị lần lượt.

Một bài toán có thể được giải bằng cách kết hợp lời giải của những bài toán nhỏ hơn. Chia nhỏ giúp mỗi phần dễ hiểu, dễ thực hiện và dễ kiểm tra, đồng thời vẫn giữ yêu cầu đầu ra của bài toán ban đầu. Trong sắp xếp, một việc nhỏ là hoán đổi đúng hai giá trị. Việc lớn hơn quyết định so sánh những phần tử nào, khi nào đổi và lặp đến đâu. Chỉ biết đổi hai giá trị chưa đủ để sắp xếp cả dãy; cần tổ chức các bước theo thuật toán. Trong tìm kiếm nhị phân, sau một lần so sánh, bài toán tìm trên toàn vùng được thu thành bài toán tìm trên một vùng nhỏ hơn. Vẫn tìm cùng giá trị cần tìm, không đổi sang một yêu cầu khác. Thực hành với hai thẻ 12 và 7, ghi ba bước dùng chỗ tạm rồi đối chiếu đầu ra 7, 12. Sau đó dùng các thẻ của dãy 9, 4, 7, 2, 6 để thực hiện các phép so sánh và hoán đổi ở hai bài sắp xếp tiếp theo.