17/12/2020 04:29:06 PM

Lập trình

Thuật Toán “Sắp Xếp Nổi Bọt” Trong Python

 

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:

» Các tin khác:

Hôm nay, ngày

14/05/2024

Tuần học:

41

Sinh viên tiêu biểu

Số lượt truy cập: 8355506