Lý thuyết Tin học 7 Kết nối tri thức Bài 16: Thuật toán sắp xếp
Haylamdo biên soạn và sưu tầm tóm tắt lý thuyết Tin học lớp 7 Bài 16: Thuật toán sắp xếp sách Kết nối tri thức hay nhất, ngắn gọn sẽ giúp học sinh nắm vững kiến thức trọng tâm, ôn luyện để học tốt môn Tin học 7.
Lý thuyết Tin học 7 Kết nối tri thức Bài 16: Thuật toán sắp xếp
1. Thuật toán sắp xếp nổi bọt
- 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ự.
- Mô tả thuật toán sắp xếp nổi bọt bằng ngôn ngữ tự nhiên:
1. Với phần tử đầu tiên, thực hiện 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 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.
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 em sẽ nhận được dãy số với phần tử nhỏ thứ nhì nổi lên vị trí thứ hai.
3. Tương tự như trên với các phần tử thứ ba, thứ tư,… đến các phần tử cuối cùng.
4. Kết thúc 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
- 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ự.
- 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 ngữ sắp xếp chọn.
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 nhận được dãy số với phần tử nhỏ nhất được đưa về vị trí đầu tiên.
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 nhận được dãy số với phần tử từ nhỏ thứ nhì được đưa về vị trí thứ hai.
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.
4. Kết thúc 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
- 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.