Lý thuyết thuật toán sắp xếp - Tin học 07
Lý thuyết thuật toán sắp xếp
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: 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.
(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.
(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
(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, 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
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 toán 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, sẽ 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, sẽ nhận được dãy số với phần 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, 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
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