Sắp xếp là một kỹ năng quan trọng mà mọi lập trình viên' class='hover-show-link replace-link-1536'>kỹ sư phần mềm và lập trình viên cần có. Đó không chỉ là để hoàn thành các cuộc phỏng vấn mà còn để hiểu và làm việc hiệu quả trong lập trình . Có nhiều thuật toán sắp xếp khác nhau, và việc thiết kế thuật toán có thể ảnh hưởng đến độ phức tạp, tốc độ và hiệu quả của chương trình.
Hãy cùng khám phá 5 thuật toán sắp xếp hàng đầu và cách triển khai chúng bằng mã Python.
Bubble Sort
Thuật toán Bubble sort (sắp xếp nổi bọt) thường được dạy trong các khóa học nhập môn khoa học máy tính vì nó dễ hiểu và rõ ràng. Bubble sort duyệt qua danh sách và so sánh các cặp phần tử liền kề. Nếu chúng không đúng thứ tự, các phần tử sẽ được hoán đổi. Quá trình này được lặp lại cho đến khi danh sách được sắp xếp. Độ phức tạp của Bubble sort là O(n²) vì nó lặp lại qua toàn bộ danh sách.
Dưới đây là mã Python cho thuật toán sắp xếp nổi bọt:
def bubble_sort(arr): n = len(arr) for i in range(n - 1): for j in range(n - i - 1): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] return arrSelection Sort
Thuật toán Selection sort (sắp xếp chọn) cũng đơn giản nhưng thường hoạt động tốt hơn Bubble sort. Nếu bạn phải chọn giữa hai thuật toán này, tốt nhất hãy chọn Sắp xếp chọn. Với Selection sort, chúng ta chia danh sách đầu vào thành hai phần: danh sách các phần tử đã được sắp xếp và danh sách các phần tử còn lại chưa được sắp xếp. Đầu tiên, chúng ta tìm phần tử nhỏ nhất trong danh sách chưa được sắp xếp và đặt nó vào cuối danh sách đã sắp xếp. Tiếp tục quá trình này cho đến khi danh sách được sắp xếp hoàn toàn.
Dưới đây là mã Python cho thuật toán sắp xếp chọn:
def selection_sort(arr): n = len(arr) for i in range(n): min_idx = i for j in range(i + 1, n): if arr[j] arr[min_idx]: min_idx = j arr[i], arr[min_idx] = arr[min_idx], arr[i] return arrInsertion Sort
Thuật toán Insertion sort (sắp xếp chèn) nhanh hơn và đơn giản hơn Bubble sort và Selection sort. Đây là cách mà nhiều người sắp xếp bài khi chơi trò chơi bài. Thuật toán này lặp lại việc loại bỏ một phần tử khỏi mảng và đặt phần tử đó vào vị trí phù hợp trong mảng đã được sắp xếp. Quá trình này diễn ra cho đến khi không còn phần tử nào cần sắp xếp.
Dưới đây là mã Python cho thuật toán sắp xếp chèn:
def insertion_sort(arr): n = len(arr) for i in range(1, n): key = arr[i] j = i - 1 while j >= 0 and arr[j] > key: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key return arrMerge Sort
Thuật toán Merge sort (sắp xếp trộn) là một ví dụ hoàn hảo về "chia để trị". Nó sử dụng hai bước chính:
-
Chia danh sách chưa được sắp xếp thành các danh sách con, mỗi danh sách con chứa một phần tử chưa được sắp xếp. Tiến trình này tiếp tục cho đến khi có N danh sách con, trong đó mỗi danh sách con có 1 phần tử.
-
Trộn (ghi đè) các danh sách con với nhau để tạo ra các danh sách con mới đã sắp xếp, 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 đã sắp xếp.
Dưới đây là mã Python cho thuật toán sắp xếp trộn:
def merge_sort(arr): if len(arr) = 1: return arr mid = len(arr) // 2 left = arr[:mid] right = arr[mid:] left = merge_sort(left) right = merge_sort(right) return merge(left, right) def merge(left, right): result = [] while len(left) > 0 and len(right) > 0: if left[0] right[0]: result.append(left[0]) left = left[1:] else: result.append(right[0]) right = right[1:] result.extend(left) result.extend(right) return resultQuick Sort
Thuật toán Quick sort (sắp xếp nhanh) cũng là một ví dụ về "chia để trị" giống Merge sort. Mặc dù phức tạp hơn một chút, Quick sort thường thực hiện nhanh hơn Merge sort và ít khi đạt đến độ phức tạp O(n²) trong trường hợp xấu nhất. Quick sort bao gồm ba bước chính:
-
Chọn một phần tử gọi là pivot từ mảng.
-
Di chuyển tất cả các phần tử nhỏ hơn pivot sang trái của pivot, di chuyển tất cả các phần tử lớn hơn pivot sang phải của pivot. Quá trình này được gọi là phân đoạn (partition operation).
-
Áp dụng đệ quy cho các mảng con nhỏ hơn và lớn hơn pivot cuối cùng.
Dưới đây là mã Python cho thuật toán Quick sort:
def quicksort(arr): if len(arr) = 1: return arr pivot = arr[len(arr) // 2] left = [x for x in arr if x pivot] middle = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot] return quicksort(left) + middle + quicksort(right)Những thuật toán sắp xếp này là những công cụ mạnh mẽ mà mọi lập trình viên nên nắm vững. Bằng cách hiểu cách các thuật toán này hoạt động và triển khai chúng bằng mã Python, bạn có thể cải thiện khả năng lập trình của mình và xây dựng các chương trình hiệu quả hơn.
Bài viết của tác giả George Seif được đăng trên Medium.
Ảnh minh họa: brilliant.org