Lập trình
Thuât toán “Sắp xếp nổi bọt” trong lập trình Python
Trong cuộc sống hằng ngày, chúng ta thường xuyên gặp bài toán sắp xếp các dữ liệu theo một trật tự nhất định: từ nhỏ đến lớn hoặc từ lớn đến nhỏ. Trong bài viết này, chúng ta sẽ cùng tìm hiểu một thuật toán (algorithm) sắp xếp thông dụng, đó là Thuật toán sắp xếp nổi bọt. Ta cũng sẽ làm một ví dụ đơn giản sử dụng ngôn ngữ lập trình Python để xếp hạng thi đua của một lớp học.
Thuật toán Sắp xếp nổi bọt trong lập trình Python là gì?
Thuật toán này (tiếng Anh: Bubble Sort) là một thuật toán sắp xếp đơn giản, với thao tác cơ bản là so sánh hai phần tử kề nhau, nếu chúng chưa đứng đúng thứ tự thì đổi chỗ cho nhau. Sắp xếp nổi bọt còn có tên là sắp xếp bằng so sánh trực tiếp. Nó sử dụng phép so sánh các phần tử nên là một giải thuật sắp xếp kiểu so sánh.
Cách thức thực hiện của thuật toán Sắp xếp
Giả sử dãy cần sắp xếp có n phần tử. Khi tiến hành từ đầu dãy đến cuối, ta so sánh hai phần tử đầu, nếu phần tử đứng trước lớn hơn phần tử đứng sau thì đổi chỗ chúng cho nhau. Tiếp tục làm như vậy với cặp phần tử thứ hai và thứ ba và tiếp tục cho đến cuối dãy, nghĩa là so sánh (và đổi chỗ nếu cần) phần tử thứ n-1 với phần tử thứ n. Sau bước này phần tử cuối cùng chính là phần tử lớn nhất của dãy.
Sau đó, quay lại so sánh (và đổi chố nếu cần) hai phần tử đầu cho đến khi gặp phần tử thứ n-2… Nếu trong một lần duyệt, mà không phải đổi chỗ bất cứ cặp phần tử nào thì dãy đã được sắp xếp xong. Do đó có thể dùng một cờ để kiểm soát việc này.
Để hiểu rõ hơn, ta hãy cùng xem ví dụ sau:
– Giả sử ta cần sắp xếp dãy số sau: [5 2 4 3 9] theo thứ tự từ nhỏ đến lớn, thuật toán sẽ thực hiện như sau:
– Lần lặp đầu tiên: [5 2 4 3 9], ta so sánh 2 phần tử đầu tiên, và tiến hành đổi chỗ 2 phần tử này do 5 > 2 ® [2 5 4 3 9]
Tương tự, ta thực hiện: [2 5 4 3 9] → [2 4 5 3 9] ® [2 4 3 5 9]
Trong lần lặp thứ nhất, có thao tác đổi chỗ nên ta thực hiện lần lặp thứ hai
– Lần lặp thứ hai: [2 4 3 5 9] → [2 4 3 5 9] → [2 3 4 5 9] → [2 3 4 5 9].
– Lần lặp thứ ba: [2 3 4 5 9] → [2 3 4 5 9] ® [2 3 4 5 9] → [2 3 4 5 9]. Trong vòng lặp này, không có thao tác đổi chỗ nên dừng sắp xếp.
Thụât toán “Sắp xếp nổi bọt” trong lập trình Python
Trong cuộc sống hằng ngày, chúng ta thường xuyên gặp bài toán sắp xếp các dữ liệu theo một trật tự nhất định: từ nhỏ đến lớn hoặc từ lớn đến nhỏ. Trong bài viết này, chúng ta sẽ cùng tìm hiểu một thuật toán (algorithm) sắp xếp thông dụng, đó là Thuật toán sắp xếp nổi bọt. Ta cũng sẽ làm một ví dụ đơn giản sử dụng ngôn ngữ lập trình Python để xếp hạng thi đua của một lớp học.
Thuật toán Sắp xếp nổi bọt trong lập trình Python là gì?
Thuật toán này (tiếng Anh: Bubble Sort) là một thuật toán sắp xếp đơn giản, với thao tác cơ bản là so sánh hai phần tử kề nhau, nếu chúng chưa đứng đúng thứ tự thì đổi chỗ cho nhau. Sắp xếp nổi bọt còn có tên là sắp xếp bằng so sánh trực tiếp. Nó sử dụng phép so sánh các phần tử nên là một giải thuật sắp xếp kiểu so sánh.
Cách thức thực hiện của thuật toán Sắp xếp
Giả sử dãy cần sắp xếp có n phần tử. Khi tiến hành từ đầu dãy đến cuối, ta so sánh hai phần tử đầu, nếu phần tử đứng trước lớn hơn phần tử đứng sau thì đổi chỗ chúng cho nhau. Tiếp tục làm như vậy với cặp phần tử thứ hai và thứ ba và tiếp tục cho đến cuối dãy, nghĩa là so sánh (và đổi chỗ nếu cần) phần tử thứ n-1 với phần tử thứ n. Sau bước này phần tử cuối cùng chính là phần tử lớn nhất của dãy.
Sau đó, quay lại so sánh (và đổi chố nếu cần) hai phần tử đầu cho đến khi gặp phần tử thứ n-2… Nếu trong một lần duyệt, mà không phải đổi chỗ bất cứ cặp phần tử nào thì dãy đã được sắp xếp xong. Do đó có thể dùng một cờ để kiểm soát việc này.
Để hiểu rõ hơn, ta hãy cùng xem ví dụ sau:
– Giả sử ta cần sắp xếp dãy số sau: [5 2 4 3 9] theo thứ tự từ nhỏ đến lớn, thuật toán sẽ thực hiện như sau:
– Lần lặp đầu tiên: [5 2 4 3 9], ta so sánh 2 phần tử đầu tiên, và tiến hành đổi chỗ 2 phần tử này do 5 > 2 ® [2 5 4 3 9]
Tương tự, ta thực hiện: [2 5 4 3 9] → [2 4 5 3 9] ® [2 4 3 5 9]
Trong lần lặp thứ nhất, có thao tác đổi chỗ nên ta thực hiện lần lặp thứ hai
– Lần lặp thứ hai: [2 4 3 5 9] → [2 4 3 5 9] → [2 3 4 5 9] → [2 3 4 5 9].
– Lần lặp thứ ba: [2 3 4 5 9] → [2 3 4 5 9] ® [2 3 4 5 9] → [2 3 4 5 9]. Trong vòng lặp này, không có thao tác đổi chỗ nên dừng sắp xếp.
» Tin mới nhất:
- ĐỐI TƯỢNG RESPONSE TRONG ASP.NET (18/11/2024)
- Đảo Danh Sách Liên Kết bằng đệ quy (12/11/2024)
- Sự khác nhau ở Kế Thừa giữa Java và C# khi dùng đa hình (23/10/2024)
- Sử dụng FormView kết hợp SqlDataSource để tạo trang quản lý chủng loại hàng hóa (18/10/2024)
- Phân Tich lớp (14/10/2024)
» Các tin khác:
- Hướng Dẫn Sử Dụng Thư Viện "Requests" trong Python (17/12/2020)
- Thêm dữ liệu vào file đã có trong java (08/12/2020)
- Đọc File bằng Scanner (08/12/2020)
- Hàm kiểm tra một số có phải là số FIBONACCI hay không (25/11/2020)
- Hàm in dãy FIBONACCI (25/11/2020)
- Bài 02 - Thủy vân số trên ảnh tĩnh - các kỹ thuật kỹ vân số (18/11/2020)
- Bài 01 - Thủy vân số trên ảnh tĩnh - Tổng quan (18/11/2020)
- Lọc thông tin chi tiết sản phẩm trong ASP.net (18/11/2020)
- Lọc thông tin theo loại (18/11/2020)
- Hàm tìm thông tin trên tập tin (18/11/2020)
