Tìm hiểu 5 thuật toán sắp xếp hàng đầu với Python code

Sắp xếp là một kỹ năng mà mọi kỹ sư phần mềm và lập trình viên cần nắm vững. Không chỉ để vượt qua các cuộc phỏng vấn mà còn là sự hiểu biết để làm tốt công việc lập trình. Các thuật toán sắp xếp khác nhau cho thấy cách thiết kế thuật toán có thể có ảnh hưởng mạnh mẽ đến độ phức tạp, tốc độ và hiệu quả của chương trình.

Hãy cùng xem 5 thuật toán sắp xếp hàng đầu và xem cách chúng ta có thể triển khai chúng bằng Python.

Bubble Sort

Bubble sort (sắp xếp nổi bọt) là cách thường được dạy trong các lớp nhập môn khoa học máy tính vì nó thể hiện rõ ràng cách sắp xếp hoạt động đồng thời là thuật toán đơn giản và dễ hiểu. Bubble sort duyệt qua danh sách và so sánh các cặp phần tử liền kề. Các phần tử được hoán đổi nếu chúng không đúng thứ tự. Việc chuyển qua phần chưa được sắp xếp của danh sách được lặp lại cho đến khi danh sách được sắp xếp. Vì bubble sort lặp đi lặp lại qua phần không được sắp xếp của danh sách, nên nó có độ phức tạp trong trường hợp xấu nhất là O (n²).

Thuật toán sắp xếp nổi bọt, bubble sort, với Python code:

Selection sort

Selection sort (Sắp xếp chọn) cũng khá đơn giản nhưng thường hoạt động tốt hơn bubble sort. Nếu bạn đang chọn giữa hai thuật toán thì tốt nhất nên chọn sắp xếp chọn. Với selection sort, chúng ta chia danh sách / mảng đầu vào của thành hai phần: danh sách con các mục đã được sắp xếp và danh sách con các mục còn lại sẽ được sắp xếp tạo nên phần còn lại của danh sách. Đầu tiên chúng ta tìm phần tử nhỏ nhất trong danh sách con chưa được sắp xếp và đặt nó ở cuối danh sách con đã sắp xếp. Theo cách đó, chúng ta liên tục lấy phần tử chưa được sắp xếp nhỏ nhất và đặt nó theo thứ tự được sắp xếp trong danh sách con được sắp xếp. Quá trình này tiếp tục lặp đi lặp lại cho đến khi danh sách được sắp xếp đầy đủ.

Thuật toán sắp xếp chọn, selection sort, được minh họa trong Python

Insertion sort

Insertion sort (Sắp xếp chèn) vừa nhanh hơn và được cho là đơn giản hơn cả sắp xếp nổi bọt và sắp xếp chọn. Thật hài hước, đó là cách nhiều người sắp xếp các quân bài của họ khi chơi một trò chơi bài. Trên mỗi lần lặp vòng lặp, sắp xếp chèn loại bỏ một phần tử khỏi mảng. Sau đó, nó tìm vị trí mà phần tử đó thuộc về một mảng được sắp xếp khác và chèn nó vào đó. Nó lặp lại quá trình này cho đến khi không còn yếu tố đầu vào nào.

Giải thuật Insertion sort với Python code:

Merge Sort

Merge sort (sắp xếp trộn) là một ví dụ hoàn hảo về thuật toán chia để trị (Divide and Conquer algorithm). Nó đơn giản sử dụng 2 bước chính của một thuật toán:

(1) Liên tục chia danh sách chưa được sắp xếp cho đến khi bạn có N danh sách con, trong đó mỗi danh sách con có 1 phần tử “chưa được sắp xếp” và N là số phần tử trong mảng ban đầu.

(2) Liên tục trộn tức là chinh phục (trị) các danh sách con với nhau 2 cùng một lúc để tạo ra các danh sách con được sắp xếp mới cho đến khi tất cả các phần tử đã được hợp nhất hoàn toàn thành một mảng được sắp xếp duy nhất.

Thuật toán sắp xếp trộn với Python code:

Quick sort

Quick sort (sắp xếp nhanh) cũng là một thuật toán chia để trị giống như sắp xếp trộn. Mặc dù phức tạp hơn một chút nhưng theo các triển khai tiêu chuẩn hầu hết nó thực hiện nhanh hơn đáng kể so với sắp xếp trộn và hiếm khi đạt đến độ phức tạp trong trường hợp xấu nhất là O (n²). Sắp xếp nhanh có 3 bước chính:

(1) Đầu tiên chúng ta chọn một phần tử mà chúng ta sẽ gọi là pivot từ mảng.

(2) Di chuyển tất cả các phần tử nhỏ hơn pivot quay sang trái của pivot; di chuyển tất cả các phần tử lớn hơn pivot sang bên phải của pivot. Đây được gọi là hoạt động phân đoạn (partition operation).

(3) Áp dụng đệ quy 2 bước trên riêng biệt cho từng mảng con của các phần tử có giá trị nhỏ hơn và lớn hơn pivot cuối cùng.