Trang chủCông nghệ thông tinThuật toán

Trang chủ

Từ điển Tri thức

Tin tức

Bài viết chọn lọc

Chương trình đào tạo

Lập trình Arduino

Trí tuệ nhân tạo

Chuyên mục

STEAM

Câu chuyện cuộc sống

Công nghệ thông tin

Tiện ích

Đồng hồ bấm giờ

Tìm kiếm dữ liệu

Thuật toán Sắp xếp Nổi bọt với Ngôn ngữ 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.

Bài toán xếp hạng trong lớp

Bây giờ ta sẽ sử dụng ngôn ngữ lập trình Python và ứng dụng thuật toán trên để sắp xếp thứ hạng của một lớp học dựa trên điểm trung bình của từng học sinh.

Chương trình trên sẽ gồm 2 phần chính:

Phần 1: Từ dòng lệnh [1] đến dòng lệnh [21] dùng để nhập dữ liệu của học sinh, gồm họ và tên, điểm Toán, điểm Văn, điểm Anh và tính điểm trung bình của học sinh đó.

Phần 2: Từ dòng lệnh [23] đến đến dòng lệnh [31] dùng để xếp hạng của học sinh, sử dụng thuật toán sắp xếp nổi bọt.

Sử dụng webcam để phát hiện khuôn mặt với Python và thư viện OpenCV >
Các bài viết mới nhất cùng chuyên mục

Sử dụng webcam để phát hiện khuôn mặt với Python và thư viện OpenCV

Bài toán tìm đường đi giữa các phòng với Thuật toán tìm kiếm theo chiều rộng và chiều sâu

Thuật toán Sắp xếp Nổi bọt với Ngôn ngữ lập trình Python

Các bài viết cùng chuyên mục

Quảng cáo

Trang chủ | Giới thiệu về Xuân Tuyến Network