Nội dung chính tin học 7 chân trời Bài 14: thuật toán sắp xếp

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

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

- Thuật toán sắp xếp nổi bọt: thực hiện lặp đi lặp lại việc đổi chỗ 2 số liền kề trong một dãy số nếu chúng đứng sai thứ tự.

- Mô tả thuật toán sắp xếp nổi bọt:

          + Đầu vào: Dãy chưa được sắp xếp

          + Đầu ra: Dãy được sắp xếp không giảm

(1) Chuyển phần tử nhỏ nhất về vị trí đầu tiên

          (1.1) So sánh từng phần tử của dãy với phần tử liền trước, lần lượt từ phần tử cuối cùng lên phần tử đầu tiên

          (1.2) Nếu nhỏ hơn thì đổi chỗ hai phần tử

          (1.3) Kết thúc vòng lặp, phần tử nhỏ nhất “nổi lên” vị trí đầu tiên của dãy

(2) Chuyển phần tử nhỏ thứ hai về vị trí thứ hai

          (2.1) So sánh từng phần tử của dãy với phần tử liền trước, lần lượt từ phần tử cuối cùng lên phần tử thứ hai

          (2.2) Nếu nhỏ hơn thì đổi chỗ hai phần tử

          (2.3) Kết thúc vòng, phần tử nhỏ thứ hai “nổi lên” vị trí thứ hai của dãy

(3) Thực hiện tương tự như trên với phần tử nhỏ thứ ba, thứ tư,… cho đến phần tử liền trước phần tử cuối cùng

(4) Kết thúc thuật toán, ta sẽ nhận được dãy số đã được sắp xếp theo thứ tự không giảm

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

- Thực hiện chọn phần tử nhỏ nhất trong dãy chưa được sắp xếp và đưa phần tử này về vị trí đầu tiên của dãy chưa được sắp xếp

- Lặp lại quá trình này cho đến khi dãy chưa sắp xếp chỉ còn một phần tử

- Mô phỏng lại thuật toán sắp xếp chọn:

          + Bước 1. Coi số đầu tiên của dãy số (vị trí 1) là số nhỏ nhất (MIN).

          + Bước 2. So sánh MIN với số thứ 2

          + Bước 3. So sánh MIN với số thứ 3

          + Bước 4. So sánh MIN với số thứ 4

=> Với thuật toán sắp xếp chọn, bài toán sắp xếp dãy số ban đầu cũng được chia thành những bài toán nhỏ để giải quyết. Các bài toán nhỏ là di chuyển số nhỏ nhất (hoặc lớn nhất) về vị trí đầu tiên của dãy chưa sắp xếp. Phạm vi của dãy chưa sắp xếp hẹp dần sau mỗi lần lặp