Lý thuyết SVIP

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

a. Khái niệm

- Nổi bọt là thuật toán sắp xếp được thực hiện bằng cách hoán đổi nhiều lần các phần tử liền kề nếu giá trị của chúng không đúng thứ tự.

b. Mô tả thuật toán bằng ngôn ngữ tự nhiên

Sắp xếp dãy số theo thứ tự tăng bằng thuật toán sắp xếp nổi bọt.

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

• 1.1. So sánh hai phần tử đứng cạnh nhau theo thứ tự từ cuối dãy lên phần tử đầu tiên.
• 1.2. Nếu phần tử đứng sau nhỏ hơn phần tử đứng trước thì đổi chỗ chúng cho nhau.
• 1.3. Cuối vòng lặp 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 phần tử thứ hai, thực hiện một vòng lặp tương tự như trên.

• 2.1. So sánh hai phần tử đứng cạnh nhau theo thứ tự từ cuối dãy ngược lên phần tử thứ hai.
• 2.2. Nếu phần tử đứng sau nhỏ hơn phần tử đứng trước thì đổi chỗ chúng cho nhau.
• 2.3. Cuối vòng lặp sẽ nhận được dãy số với phần tử nhỏ thứ nhì nổi lên vị trí thứ hai.

Bước 3. Tương tự như trên với các phần tử thứ ba, thứ tư,... đến phần tử trước phần tử cuối cùng.

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

c. Ví dụ

Các bước thực hiện thuật toán sắp xếp nổi bọt để sắp xếp 5 số sau đây theo thứ tự tăng dần. 

Bước 1. Xét vị trí đầu tiên, vòng lặp thứ nhất thực hiện như sau:

Bước 2. Xét vị trí thứ hai, vòng lặp thứ hai thực hiện như sau:

Bước 3. Xét vị trí thứ ba, vòng lặp thứ ba thực hiện như sau:

2. Thuật toán sắp xếp chọn

a. Khái niệm

- Thuật toán sắp xếp chọn xét từng vị trí từ đầu đến cuối dãy, so sánh trực tiếp phần tử ở vị trí được xét với những phần tử ở phía sau nó và hoán đổi nếu chúng chưa đúng thứ tự.

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

Sắp xếp dãy số theo thứ tự từ nhỏ đến lớn bằng thuật toán sắp xếp chọn.

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

• 1.1. So sánh từng phần tử (kể từ phần tử thứ hai đến phần tử cuối cùng) với phần tử đầu tiên.
• 1.2. Nếu phần tử được xét nhỏ hơn phần tử đầu tiên thì hoán đổi nó với phần tử đầu tiên.
• 1.3. Cuối vòng lặp, 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 phần tử thứ hai, thực hiện một vòng lặp tương tự như trên.

• 2.1. So sánh từng phần tử (kể từ phần tử thứ ba đến phần tử cuối cùng với phần tử thứ hai.
• 2.2. Nếu phần tử được xét nhỏ hơn phần tử thứ hai thì hoán đổi nó với phần tử thứ hai.
• 2.3. Cuối vòng lặp, sẽ nhận được dãy số với phần tử nhỏ thứ nhì được đưa về vị trí thứ hai.

Bước 3. Tương tự như trên với các phần tử thứ ba, thứ tư,... đến phần tử trước phần tử cuối cùng.

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

c. Ví dụ

Các bước thực hiện thuật toán sắp xếp chọn để sắp xếp 5 số sau đây để thu được dãy có thứ tự tăng dần.

Bước 1. Vòng lặp thứ nhất

- Xét vị trí đầu tiên, lần lượt so sánh phần tử tại vị trí đó với các phần tử còn lại phía sau.

- Nếu gặp phần tử nhỏ hơn thì hoán đổi phần tử này với phần tử tại vị trí đầu tiên của dãy.

- Kết thúc vòng lặp thứ nhất, phần tử nhỏ nhất được đưa về vị trí đầu tiên.

Bước 2. Vòng lặp thứ hai

Chọn phần tử thứ hai (số 4), lần lượt so sánh nó với các phần tử còn lại phía sau.

Bước 3. Vòng lặp thứ ba

Chọn phần tử thứ ba (số 4), lần lượt so sánh nó với các phần tử còn lại phía sau.

Bước 4. Vòng lặp thứ tư

Chọn phần tử thứ tư (số 5), lần lượt so sánh nó với các phần tử còn lại phía sau.

3. Chia bài toán thành những bài toán nhỏ hơn

- Chia một bài toán thành những bài toán nhỏ hơn giúp thuật toán dễ hiểu và dễ thực hiện hơn.