BÀI 16: THUẬT TOÁN SẮP XẾP

1. THUẬT TOÁN SẮP XẾP NỔI BỌT

Mô tả thuật toán sắp xếp nổi bọt bằng ngôn ngữ tự nhiên:

- Bước 1. Với vị trí đầu tiên, em thực hiện một vòng lặp như sau:

+ So sánh hai phần tử đứng cạnh nhau theo thứ tự từ cuối dãy lên vị trí đầu tiên.

+ Nếu phần tử đứng sau nhỏ hơn phần tử đứng trước thì đổi chỗ chúng cho nhau

+ Cuối vòng lặp em sẽ nhận được dãy số với phần tử nhỏ nhất nổi lên vị trí đầu tiên

- Bước 2. Với vị trí thứ hai, em thực hiện một vòng lặp tương tự như trên

+ So sánh hai phần tử đứng cạnh nhau theo thứ tự từ cuối dãy lên vị trí thứ hai.

+ Nếu phần tử đứng sau nhỏ hơn phần tử đứng trước thì đổi chỗ chúng cho nhau

+ Cuối vòng lặp em sẽ nhận được dãy số với phần tử nhỏ thứ nhỉ lên lên vị trí thứ hai

- Bước 3. Tương tư như trên các vị trí thứ ba, thứ tư,… đến vị trí trước vị trí cuối cùng

- Bước 4. Kết thúc, em sẽ nhận được dãy số đã được sắp xếp theo thứ tự từ nhỏ đến lớn

2. THUẬT TOÁN SẮP XẾP CHỌN

Mô tả thuật toán sắp xếp chọn bằng ngôn ngữ tự nhiên

- Bước 1. Với vị trí đầu tiên, em thực hiện một vòng lặp như sau

+ So sánh từng phần tử (kể từ vị trí thứ hai đến vị trí cuối cùng) với phần tử tại vị trí đầu tiên

+ Nếu phần tử được xét nhỏ hơn phần tử tại vị trí đầu tiên thì hoán đổi nó với phần tử tại vị trí đầu tiên

+ Cuối vòng lặp, em sẽ nhận được dãy số với phần tử nhỏ nhất được đưa về vị trí đầu tiên

- Bước 2. Với vị trí thứ hai, em thực hiện một vòng lặp tương tự như trên

+ So sánh từng phần tử (kể từ vị trí thứ ba đến vị trí cuối cùng) với phần tử tại vị trí thứ hai

+ Nếu phần tử được xét nhỏ hơn phần tử tại vị trí thứ hai thì hoán đổi nó với phần tử tại vị trí thứ hai

+ Cuối vòng lặp, em sẽ nhận được dãy số với phần tử từ nhỏ thứ nhì được đưa về vị trí thứ hai

- Bước 3. Tương tư như trên các vị trí thứ ba, thứ tư,… đến vị trí trước vị trí cuối cùng

- Bước 4. Kết thúc, em sẽ nhận được dãy số đã được sắp xếp theo thứ tự từ nhỏ đến lớn

3. CHIA BÀI TOÁN THÀNH NHỮNG BÀI TOÁN NHỎ HƠN

- Ý nghĩa: Để giải quyết một bài toán, chúng ta đã dựa trên lời giải của bài toán nhỏ hơn. Việc chia một bài toán thành những bài toán nhỏ hơn giúp việc giải bài toán đó dễ dàng hơn, đồng thời việc mô tả thuật toán dễ hiểu và dễ thực hiện hơn