Viết chương trình cho phép nhập vào 1 số n, sau đó lần lượt nhập vào n giá trị a1, a2,…,an. Sắp theo thứ tự tăng dần một dãy n số a1, a2,...an nói trên. Có rất nhiều giải thuật để giải quyết bài toán này. Phần trình bày dưới đây là một phương pháp.

Giả sử ta đã nhập vào máy dãy n số a1, a2,..., an. Việc sắp xếp dãy số này trải qua (n-1) lần:

Lần 1: So sánh phần tử đầu tiên với tất cả các phần tử đứng sau phần tử đầu tiên. Nếu có phần tử nào nhỏ hơn phần tử đầu tiên thì đổi chỗ phần tử đầu tiên với phần tử nhỏ hơn đó. Sau lần 1, ta được phần tử đầu tiên là phần tử nhỏ nhất.

Lần 2: So sánh phần tử thứ 2 với tất cả các phần tử đứng sau phần tử thứ 2. Nếu có phần tử nào nhỏ hơn phần tử thứ 2 thì đổi chỗ phần tử thứ 2 với phần tử nhỏ hơn đó. Sau lần 2, ta được phần tử đầu tiên và phần tử thứ 2 là đúng vị trí của nó khi sắp xếp.
…

Lần (n-1): So sánh phần tử thứ (n-1) với phần tử đứng sau phần tử (n-1) là phần tử thứ n. Nếu phần tử thứ n nhỏ hơn phần tử thứ (n-1) thì đổi chỗ 2 phần tử này. Sau lần thứ (n-1), ta được danh sách gồm n phần tử được sắp thứ tự.

Mô tả giải thuật bằng ngôn ngữ tự nhiên:

- Bước 1: Gán i=1

- Bước 2: Gán j=i+1

- Bước 3: Nếu i <=n-1 thì thực hiện bước 4, ngược lại thực hiện bước 8

- Bước 4: Nếu j <=n thì thực hiện bước 5, ngược lại thì thực hiện bước 7.

- Bước 5: Nếu ai > aj thì hoán đổi ai và aj cho nhau (nếu không thì thôi).

- Bước 6: Tăng j lên một đơn vị và quay lại bước 4

- Bước 7: Tăng i lên một đơn vị và quay lại bước 3

- Bước 8: In dãy số a1, a2,..., an - Kết thúc.

Giải thuật + Cấu trúc dữ liệu = Chương trình

Algorithms + Data Structures = Programs