Bài 23. Thuật toán sắp xếp
Bài học lí giải vì sao cần sắp xếp dữ liệu, rồi giới thiệu một thuật toán sắp xếp đơn giản, dễ hình dung: sắp xếp nổi bọt, cùng cách cài đặt cụ thể bằng Python.
- Cánh DiềuTin học 11 (Khoa học máy tính) - Chủ đề F(CS) · Bài 8. Lập trình một số thuật toán sắp xếptr. 122
- Kết nối tri thứcTin học 11 (Khoa học máy tính) - Bài 21. Các thuật toán sắp xếp đơn giảntr. 99–103
Bắt đầu bằng một hình dung
Hãy tưởng tượng một hàng người đứng lộn xộn trước khi chụp ảnh tập thể, và có người muốn xếp lại cả hàng theo thứ tự chiều cao tăng dần, từ thấp đến cao. Người này không thể nhấc bổng tất cả mọi người lên rồi đặt đúng vị trí ngay lập tức; cách làm đơn giản nhất là đi dọc hàng, mỗi lần nhìn hai người đứng cạnh nhau. Nếu người đứng trước cao hơn người đứng sau, hai người đó đổi chỗ cho nhau. Đi hết một lượt từ đầu hàng đến cuối hàng như vậy, rồi quay lại đi thêm lượt nữa, cứ thế lặp lại nhiều lần, cho đến khi không còn cặp nào đứng sai thứ tự - lúc đó cả hàng đã được xếp đúng theo chiều cao.
Trong Tin học, cách sắp xếp một dãy dữ liệu bằng việc so sánh và đổi chỗ từng cặp phần tử đứng liền kề nhau như vậy chính là ý tưởng của một trong những thuật toán sắp xếp cơ bản nhất: sắp xếp nổi bọt.
Nội dung bài học
- Vì sao cần sắp xếp dữ liệu?
- Ý tưởng của thuật toán sắp xếp nổi bọt
Tóm tắt lý thuyết cần nhớ
- Sắp xếp dữ liệu giúp tra cứu và so sánh dễ dàng hơn, đồng thời là điều kiện cần để nhiều thuật toán khác - như tìm kiếm nhị phân - hoạt động đúng.
- Sắp xếp nổi bọt lặp lại việc so sánh và đổi chỗ hai phần tử liền kề khi chúng sai thứ tự, qua nhiều lượt duyệt liên tiếp.
- Cài đặt bằng Python cần hai vòng lặp lồng nhau: vòng ngoài đếm lượt duyệt, vòng trong so sánh - đổi chỗ từng cặp bằng cú pháp
a[j], a[j + 1] = a[j + 1], a[j]. - Sau mỗi lượt duyệt, phần tử lớn nhất trong đoạn chưa chắc chắn đúng vị trí sẽ được đưa về đúng chỗ cuối cùng; với dãy có
nphần tử, cần tối đan - 1lượt để chắc chắn sắp xếp xong.
Thuật ngữ tiếng Anh trong bài
| Tiếng Anh | Đọc là | Nghĩa |
|---|---|---|
| sort | xọt | sắp xếp Xếp các phần tử theo thứ tự tăng hoặc giảm - như xếp các bạn trong lớp theo chiều cao từ thấp đến cao. |
| algorithm | AL-gô-rít-thầm | thuật toán Các bước làm một việc theo đúng thứ tự để ra kết quả - như công thức pha mì gói: đổ nước sôi, chờ 3 phút, rồi ăn. |
Câu hỏi trắc nghiệm có đáp án
Mấy câu mẫu để bạn tự kiểm tra ngay. Trong ứng dụng, bài này có đủ 25 câu, chấm điểm tự động và giải thích từng câu sai.
- Để có thể áp dụng thuật toán tìm kiếm nhị phân, vốn chỉ cho kết quả đúng trên dãy đã sắp xếp
- Để dãy dữ liệu chiếm ít dung lượng lưu trữ hơn, vì các giá trị gần nhau sẽ được gộp lại
- Để chương trình không còn cần dùng vòng lặp khi xử lí dãy dữ liệu đã được sắp xếp sẵn
- Để dữ liệu tự động được sao lưu an toàn hơn sau mỗi lần thay đổi thứ tự các phần tử
- Xoá phần tử đứng sau khỏi dãy
- Chèn thêm một phần tử mới vào giữa hai phần tử đó
- Đổi chỗ hai phần tử đó cho nhau
- Dừng thuật toán ngay lập tức vì dãy không thể sắp xếp được
a[j], a[j + 1] = a[j + 1], a[j] có tác dụng gì?- Tính tổng của hai phần tử
a[j]vàa[j + 1] - Đổi chỗ giá trị của hai phần tử liền kề
a[j]vàa[j + 1] - So sánh xem
a[j]có bằnga[j + 1]hay không - Xoá phần tử
a[j]ra khỏi danh sácha
a[j], a[j + 1] = a[j + 1], a[j] là cách Python gán giá trị chéo cho hai phần tử của danh sách cùng một lúc, tức đổi chỗ giá trị của a[j] và a[j + 1] mà không cần dùng biến trung gian. Đây không phải là phép tính tổng, phép so sánh hay thao tác xoá phần tử.- a)Một dãy dữ liệu đã được sắp xếp thường giúp việc tra cứu, so sánh và trình bày trở nên thuận tiện hơn so với một dãy còn lộn xộn.Đúng
- b)Thuật toán tìm kiếm nhị phân cho kết quả đúng trên mọi dãy, kể cả dãy chưa được sắp xếp, nên không cần sắp xếp trước khi dùng.Sai
- c)Sắp xếp một dãy chỉ có tác dụng trình bày danh sách cho gọn gàng, chứ không phải là điều kiện cần cho hoạt động của các thuật toán khác.Sai
- d)Sắp xếp không nhất thiết phải theo thứ tự tăng dần; ta hoàn toàn có thể sắp xếp một dãy theo thứ tự giảm dần tuỳ theo nhu cầu.Đúng
- (a) Đúng - dãy đã sắp xếp giúp tìm giá trị, so sánh lớn nhỏ và theo dõi danh sách dễ hơn hẳn dãy chưa có trật tự.
- (b) Sai - tìm kiếm nhị phân liên tục thu hẹp phạm vi dựa trên so sánh với phần tử ở giữa, điều này chỉ có ý nghĩa khi dãy đã tăng (hoặc giảm) dần; áp lên dãy lộn xộn sẽ cho kết quả không đáng tin.
- (c) Sai - ngoài việc trình bày gọn gàng, sắp xếp còn là bước chuẩn bị bắt buộc để nhiều thuật toán khác (như tìm kiếm nhị phân) chạy đúng.
- (d) Đúng - thứ tự tăng dần chỉ là quy ước phổ biến; ta có thể sắp xếp giảm dần bằng cách đảo lại điều kiện so sánh.
Thử ngay: minh hoạ từng bước
Bấm từng bước để tự xem cơ chế hoạt động, hoặc bấm “Tự chạy” cho nó tiến mỗi giây một lần. Đổi được dữ liệu đầu vào - không cần đăng nhập.
Học trọn bài này trong ứng dụng
Bài giảng đầy đủ, 25 câu luyện tập chấm tự động, thi thử đúng cấu trúc đề tốt nghiệp (24 trắc nghiệm + 4 Đúng/Sai), bài thực hành máy tự chấm và gia sư AI giải thích chỗ sai.
Phần học miễn phí, không cần tạo tài khoản.
Bài liên quan - Lập trình, Thuật toán & CTDL (KHMT)
Cùng mạch kiến thức với bài này, học nối tiếp cho chắc phần lí thuyết.