Bài 16. Thuật toán sắp xếp SVIP

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

a. Khái niệm

- Thuật toán 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:

+ Bước 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.

+ Bước 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.

+ Bước 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.

+ Bước 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.

+ Bước 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.

+ Bước 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 là 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:

+ Bước 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.

+ Bước 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.

+ Bước 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.

+ Bước 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.

+ Bước 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.

+ Bước 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.