Trong bài học trước, chúng ta đã biết sắp xếp giúp cho việc tìm kiếm được thực hiện dễ dàng. Có những dạng thuật toán sắp xếp nào? Những dạng thuật toán sắp xếp được thực hiện như thế nào? Cùng DapAnHay tìm hiểu các kiến thức về thuật toán sắp xếp qua nội dung bài giảng của Bài 16: Thuật toán sắp xếp trong chương trình Tin học 7 Kết nối tri thức dưới đây!
- Trong cuộc sống hàng ngày, chúng ta thường xuyên phải thực việc sắp xếp các đồ vật để dễ tìm. Máy tính cũng thường xuyên phải thực hiện thuật toán sắp xếp khi người sử dụng yêu cầu.
- Ví dụ: Sắp xếp điểm trung bình của học sinh trong lớp bằng chương trình bảng tính; sắp xếp tên tệp trong thư mục; ... Có nhiều thuật toán sắp xếp khác nhau. Một trong số đó là thuật toán sắp xếp nổi bọt.
- Giả sử ta cần phải sắp xếp dãy các số 4, 2, 3, 1 để thu được dãy có thứ tự tăng dần. Thuật toán sắp xếp nổi bọt xét từng vị tri từ đầu đến cuối dãy. Tại mỗi vị trí được xét, thuật toán tìm phần tử nhỏ nhất trong những phần tử phía sau để đưa vào vị trí đó. Việc này được thực hiện bằng một vòng lặp, so sánh từng cặp phần tử cạnh nhau và hoán đổi chúng nếu số ở phía sau nhỏ hơn.
* Các bước thực hiện được mô tả trong Hình 16.2. Hình 16.3. Hình 16.4 dưới đây:
Xét vị trí đầu tiên, vòng lặp thứ nhất thực hiện như sau:
Hình 16.2. Vòng lặp thứ nhất của thuật toán nổi bọt
Xét vị trí thứ hai:
Hình 16.3. Vòng lặp thứ hai của thuật toán nổi bọt
Xét vị trí thứ ba:
Hình 16.4. Vòng lặp thứ ba của thuật toán nổi bọ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.
- 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.
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ự. |
---|
- Giống thuật toán sắp xếp nổi bọt, thuật toán sắp xếp chọn cũng xét từng vị trí và đưa phần tử nhỏ nhất trong những phần tử phía sau vào vị trí đó.
- Tuy nhiên, việc này được thực hiện bằng cách 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 phần tử phía sau nhỏ hơn.
* Các bước thực hiện được thuật toán sắp xếp chọn
Giả sử ta cần phải sắp xếp dãy các số 3, 4, 1, 5, 2 để thu được dãy có thứ tự tăng dần
3 | 4 | 1 | 5 | 2 |
Đầu vào: Dãy các phần tử chưa sắp xếp
- Vòng lặp thứ nhất:
+ Chọn phần từ đầu tiên, lần lượt so sánh nó 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ử đầu tiên của dãy.
- Vòng lặp thứ hai được thực hiện tương tự như vòng lặp trước với phần tử thứ hai.
- Vòng lặp thứ ba được thực hiện tương tự như hai vòng lặp trước với phần từ thứ ba.
- Vòng lặp thứ tư được thực hiện tương tự như những vòng lặp trước với phần tử thứ tư.
Đầu ra: Dãy các phần tử đã được sắp xếp
* 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.
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ự. |
---|
- Trong quá trình thực hiện cả hai thuật toán sắp xếp nổi bọt và sắp xếp chọn, ta đều thấy xuất hiện nhiều lần thuật toán đơn giản hơn: hoán đổi giá trị hai phần tử. Như vậy, bài toán sắp xếp đã được giải quyết dựa trên lời giải của bài toán nhỏ hơn là bài toán hoán đổi giá trị.
- Xem xét thuật toán tìm kiếm nhị ta cũng nhận thấy thuật toán tìm kiếm nhị phân thực hiện chia bài toán thành những bài toán nhó hơn. Trong đó, bài toán nhỏ hơn là một phần của bài toán ban đầu. Cụ thể, ở mỗi lần lặp thuật toán tìm kiếm nhị phân đã thu hẹp vùng tìm kiếm chỉ còn một nửa.
⇒ Để giải quyết một bài toán, chúng ta đã dựa trên lời giải của bài toán nhỏ hơn. Việc chia một bài toán thành những bài toán nhỏ hơn giúp việc giài bài toán đó dễ dàng hơn, đồng thời việc mô tả thuật toán dễ hiểu và dễ thực hiện 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. |
---|
Bài tập 1: Mô tả thuật toán sắp xếp nổi bọt bằng ngôn ngữ tự nhiên gồm có mấy bước?
Hướng dẫn giải:
Mô tả thuật toán sắp xếp nổi bọt bằng ngôn ngữ tự nhiên gồm có 4 bước.
- Bước 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.
- 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 em 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 các phần tử cuối cùng.
- Bước 4. Kết thúc nhận được dãy số đã được sắp xếp theo thứ tự từ nhỏ đến lớn.
Bài tập 2: Thuật toán sắp xếp nổi bọt sắp xếp danh sách bằng cách?
Hướng dẫn giải:
Thuật toán sắp xếp nổi bọt sắp xếp danh sách bằng cách hoán đổi nhiều lần các giá trị liền kề nếu giá trị của chúng không đúng thứ tự.
Bài tập 3: Cho dãy số a như hình dưới đây:
Sử dụng thuật toán sắp xếp chọn để sắp xếp dãy số theo thứ tự giảm dần thì sau bao nhiêu lượt đổi chỗ thì thuật toán kết thúc?
Hướng dẫn giải:
Có 5 lần đổi chổ.
Quy trình thực hiện như hình dưới đây:
Qua bài học các em cần nắm được các về:
- Giải thích được một vài thuật toán sắp xếp cơ bản.
- Biểu diễn và mô phỏng được hoạt động của thuật toán sắp xếp với bộ dữ liệu đầu vào có kích thước nhỏ.
- Nêu được ý nghĩa của việc chia một bài toán thành những bài toán nhỏ hơn.
Các em có thể hệ thống lại nội dung kiến thức đã học được thông qua bài kiểm tra Trắc nghiệm Tin học 7 Kết nối tri thức Chủ đề 5 Bài 16 cực hay có đáp án và lời giải chi tiết.
Mô tả thuật toán sắp xếp nổi bọt bằng ngôn ngữ tự nhiên gồm có mấy bước?
Thuật toán sắp xếp chọn sẽ so sánh các phần tử ở vị trí nào?
Thuật toán sắp xếp nổi bọt sắp xếp danh sách bằng cách nào?
Câu 4-10: Mời các em đăng nhập xem tiếp nội dung và thi thử Online để củng cố kiến thức về bài học này nhé!
Các em có thể xem thêm phần hướng dẫn Giải bài tập Tin học 7 Kết nối tri thức Chủ đề 5 Bài 16để giúp các em nắm vững bài học và các phương pháp giải bài tập.
Khởi động trang 78 SGK Tin học 7 Kết nối tri thức - KNTT
Hoạt động 1 trang 80 SGK Tin học 7 Kết nối tri thức - KNTT
Câu hỏi trang 80 SGK Tin học 7 Kết nối tri thức - KNTT
Hoạt động 2 trang 82 SGK Tin học 7 Kết nối tri thức - KNTT
Câu hỏi mục 2 trang 82 SGK Tin học 7 Kết nối tri thức - KNTT
Câu hỏi mục 3 trang 82 SGK Tin học 7 Kết nối tri thức - KNTT
Luyện tập 1 trang 82 SGK Tin học 7 Kết nối tri thức - KNTT
Luyện tập 2 trang 82 SGK Tin học 7 Kết nối tri thức - KNTT
Vận dụng trang 82 SGK Tin học 7 Kết nối tri thức - KNTT
Trong quá trình học tập nếu có thắc mắc hay cần trợ giúp gì thì các em hãy comment ở mục Hỏi đáp, Cộng đồng Tin học DapAnHay sẽ hỗ trợ cho các em một cách nhanh chóng!
Chúc các em học tập tốt và luôn đạt thành tích cao trong học tập!
-- Mod Tin Học 7 DapAnHay
Mô tả thuật toán sắp xếp nổi bọt bằng ngôn ngữ tự nhiên gồm có mấy bước?
Thuật toán sắp xếp chọn sẽ so sánh các phần tử ở vị trí nào?
Thuật toán sắp xếp nổi bọt sắp xếp danh sách bằng cách nào?
Cho dãy số a như hình dưới đây
Sử dụng thuật toán sắp xếp chọn để sắp xếp dãy số theo thứ tự giảm dần thì sau bao nhiêu lượt đổi chỗ thì thuật toán kết thúc?
Mô tả thuật toán sắp xếp chọn bằng ngôn ngữ tự nhiên gồm có mấy bước?
Tại sao chúng ta chia bài toán thành những bài toán nhỏ hơn?
Thuật toán sắp xếp nổi chọn xét từng vị trí phần tử từ đâu đến đâu?
Cho dãy số: 6, 4, 5, 3. Nếu sử dụng thuật toán sắp xếp nổi bọt để sắp xếp dãy tăng dần thì sau bao nhiêu vòng lặp thì thuật toán kết thúc?
Trong thuật toán sắp xếp nổi bọt kết thúc khi nào?
Cho dãy số: 15, 1, 31, 9, 78, 42. Nếu sử dụng thuật toán sắp xếp nổi bọt để sắp xếp dãy trên tăng dần thì sau bao nhiêu lượt đổi chỗ thì thuật toán kết thúc?
Có hai chất lỏng khác màu là xanh và đỏ, lần lượt được chứa trong hai chiếc cốc A và B (Hình 16.1a). Chúng ta cần đổi chỗ hai chất lỏng này, sao cho cốc A đựng chất lỏng màu đỏ, còn cốc B đựng chất lỏng màu xanh. Để thực hiện công việc này, chúng ta sử dụng thêm một chiếc cốc thứ ba (cốc C) không đựng gì. Em hãy quan sát Hình 16.1b, Hình 16. 1c, Hình 16.1d để biết cách thực hiện.
Em hãy 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. Hãy mô phỏng các bước sắp xếp bằng hình vẽ minh họa tương tự như Hình 16.2, Hình 16.3, Hình 16.4.
3 | 5 | 4 | 1 | 2 |
Thuật toán sắp xếp nổi bọt sắp xếp danh sách bằng cách
A. Chọn phần tử có giá trị bé nhất đặt vào đầu danh sách
B. Chọn phần tử có giá trị lớn nhất đặt vào đầu danh sách
C. 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ự
D. Chèn phần tử vào vị trí thích hợp để đảm bảo danh sách sắp xếp theo đúng thứ tự.
Chọn năm học sinh, mỗi học sinh viết ra tờ giấy một con số mà mình yêu thích. Các em đứng thành một hàng ngang và cầm tờ giấy có ghi con số để cả lớp có thể quan sát được.
Ví dụ:
41 | 15 | 17 | 32 | 18 |
Học sinh thứ sáu thực hiện thuật toán sắp xếp chọn để sắp xếp các con số của năm bạn theo thứ tự tăng dần
Em hãy viết vào vở cụ thể các bước của vòng lặp thứ 2, 3, 4 được mô tả trong hình 16.5.
Hình 16.5. Mô tả thuật toán sắp xếp chọn
Chọn phương án đúng. Tại sao chúng ta chia bài toán thành những bài toán nhỏ hơn?
A. Để thay đổi đầu vào của bài toán
B. Để thay đổi yêu cầu đầu ra của bài toán
C. Để bài toán dễ giải quyết
D. Để bài toán khó giải quyết hơn
Em hãy liệt kê các bước của thuật toán sắp xếp nổi bọt để sắp xếp các số 3, 2, 4, 1, 5, theo thứ tự tăng dần.
Em hãy liệt kê các bước của thuật toán sắp xếp chọn để sắp xếp các số 3, 2, 4, 1, 5 theo thứ tự tăng dần.
Em hãy ghi lại kết quả điểm học tập môn Tin học của các bạn trong tổ. Thực hiện thuật toán sắp xếp chọn hoặc sắp xếp nổi bọt để sắp xếp điểm theo thứ tự giảm dần. Dựa trên kết quả sắp xếp, hãy cho biết danh sách tên các bạn tương ứng theo kết quả sắp xếp đó.
Họ và tên
Tiêu đề câu hỏi
Nội dung câu hỏi
0 Bình luận
Để lại bình luận
Địa chỉ email của hạn sẽ không được công bố. Các trường bắt buộc được đánh dấu *