Sắp xếp Array trong Python

Sắp xếp (sorting) là một trong những thao tác cơ bản và quan trọng nhất trong lập trình. Nó giúp tổ chức dữ liệu theo một thứ tự nhất định, từ đó giúp việc tìm kiếm và xử lý dữ liệu trở nên hiệu quả hơn. Trong Python, có nhiều cách để sắp xếp array, từ các phương pháp tích hợp sẵn đến các thuật toán sắp xếp phức tạp hơn. Bài viết này sẽ hướng dẫn chi tiết cách sắp xếp array trong Python, bao gồm các phương pháp sử dụng sort(), sorted(), và các thuật toán sắp xếp như Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, và Heap Sort.

Sử dụng sort() và sorted()

Python cung cấp hai phương pháp tích hợp sẵn để sắp xếp: sort() và sorted(). Cả hai đều sử dụng thuật toán Timsort, một thuật toán lai giữa Merge Sort và Insertion Sort.

sort()

Phương thức sort() sắp xếp danh sách tại chỗ, nghĩa là nó thay đổi danh sách gốc và không trả về danh sách mới.

Cú pháp:

list_name.sort(reverse=False, key=None)

• reverse: Tham số tùy chọn, nếu đặt là True, danh sách sẽ được sắp xếp theo thứ tự giảm dần.
• key: Tham số tùy chọn, một hàm có thể được sử dụng để tùy chỉnh tiêu chí sắp xếp.

Ví dụ:

numbers = [5, 1, 9, 3]
numbers.sort()
print(numbers)  # Output: [1, 3, 5, 9]

# Sắp xếp theo thứ tự giảm dần
numbers.sort(reverse=True)
print(numbers)  # Output: [9, 5, 3, 1]

sorted()

Hàm sorted() trả về một danh sách mới đã được sắp xếp, không thay đổi danh sách gốc.

Cú pháp:

sorted(iterable, reverse=False, key=None)

• iterable: Một đối tượng có thể lặp lại (như danh sách, tuple, set).
• reverse: Tham số tùy chọn, nếu đặt là True, danh sách sẽ được sắp xếp theo thứ tự giảm dần.
• key: Tham số tùy chọn, một hàm có thể được sử dụng để tùy chỉnh tiêu chí sắp xếp.

Ví dụ:

numbers = [5, 1, 9, 3]
sorted_numbers = sorted(numbers)
print(sorted_numbers)  # Output: [1, 3, 5, 9]
print(numbers)  # Output: [5, 1, 9, 3]

# Sắp xếp theo thứ tự giảm dần
sorted_numbers_desc = sorted(numbers, reverse=True)
print(sorted_numbers_desc)  # Output: [9, 5, 3, 1]

Sử dụng các thuật toán sắp xếp

Ngoài các phương pháp tích hợp sẵn, Python còn hỗ trợ nhiều thuật toán sắp xếp khác nhau. Dưới đây là một số thuật toán sắp xếp phổ biến và cách triển khai chúng trong Python.

Bubble Sort

Bubble Sort là thuật toán sắp xếp đơn giản nhất. Nó lặp qua danh sách, so sánh các phần tử liền kề và hoán đổi chúng nếu chúng không theo thứ tự mong muốn.

Cú pháp:

def bubble_sort(array):
    n = len(array)
    for i in range(n):
        for j in range(0, n-i-1):
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]
    return array

Ví dụ:

numbers = [64, 34, 25, 12, 22, 11, 90]
sorted_numbers = bubble_sort(numbers)
print(sorted_numbers)  # Output: [11, 12, 22, 25, 34, 64, 90]

Selection Sort

Selection Sort chia danh sách thành hai phần: phần đã sắp xếp và phần chưa sắp xếp. Nó liên tục chọn phần tử nhỏ nhất từ phần chưa sắp xếp và đặt nó vào vị trí cuối cùng của phần đã sắp xếp.

Cú pháp:

def selection_sort(array):
    n = len(array)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if array[j] < array[min_idx]:
                min_idx = j
        array[i], array[min_idx] = array[min_idx], array[i]
    return array

Ví dụ:

numbers = [64, 25, 12, 22, 11]
sorted_numbers = selection_sort(numbers)
print(sorted_numbers)  # Output: [11, 12, 22, 25, 64]

Insertion Sort

Insertion Sort chia danh sách thành hai phần: phần đã sắp xếp và phần chưa sắp xếp. Nó lặp qua phần chưa sắp xếp và chèn từng phần tử vào vị trí đúng trong phần đã sắp xếp.

Cú pháp:

def insertion_sort(array):
    for i in range(1, len(array)):
        key = array[i]
        j = i - 1
        while j >= 0 and key < array[j]:
            array[j + 1] = array[j]
            j -= 1
        array[j + 1] = key
    return array

Ví dụ:

numbers = [12, 11, 13, 5, 6]
sorted_numbers = insertion_sort(numbers)
print(sorted_numbers)  # Output: [5, 6, 11, 12, 13]

Merge Sort

Merge Sort là một thuật toán sắp xếp chia để trị. Nó chia danh sách thành hai nửa, sắp xếp từng nửa và sau đó hợp nhất chúng lại.

Cú pháp:

def merge_sort(array):
    if len(array) > 1:
        mid = len(array) // 2
        left_half = array[:mid]
        right_half = array[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                array[k] = left_half[i]
                i += 1
            else:
                array[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            array[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            array[k] = right_half[j]
            j += 1
            k += 1
    return array

Ví dụ:

numbers = [38, 27, 43, 3, 9, 82, 10]
sorted_numbers = merge_sort(numbers)
print(sorted_numbers)  # Output: [3, 9, 10, 27, 38, 43, 82]

Quick Sort

Quick Sort cũng là một thuật toán sắp xếp chia để trị. Nó chọn một phần tử làm pivot và phân chia danh sách thành hai phần: phần nhỏ hơn pivot và phần lớn hơn pivot.

Cú pháp:

def quick_sort(array):
    if len(array) <= 1:
        return array
    else:
        pivot = array[len(array) // 2]
        left = [x for x in array if x < pivot]
        middle = [x for x in array if x == pivot]
        right = [x for x in array if x > pivot]
        return quick_sort(left) + middle + quick_sort(right)

Ví dụ:

numbers = [10, 7, 8, 9, 1, 5]
sorted_numbers = quick_sort(numbers)
print(sorted_numbers)  # Output: [1, 5, 7, 8, 9, 10]

Heap Sort

Heap Sort sử dụng cấu trúc dữ liệu heap để sắp xếp. Nó xây dựng một heap từ danh sách và sau đó liên tục trích xuất phần tử lớn nhất từ heap và đặt nó vào vị trí cuối cùng của danh sách đã sắp xếp.

Cú pháp:

def heapify(array, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2

    if l < n and array[i] < array[l]:
        largest = l

    if r < n and array[largest] < array[r]:
        largest = r

    if largest != i:
        array[i], array[largest] = array[largest], array[i]
        heapify(array, n, largest)

def heap_sort(array):
    n = len(array)

    for i in range(n // 2 - 1, -1, -1):
        heapify(array, n, i)

    for i in range(n-1, 0, -1):
        array[i], array[0] = array[0], array[i]
        heapify(array, i, 0)
    return array

Ví dụ:

numbers = [12, 11, 13, 5, 6, 7]
sorted_numbers = heap_sort(numbers)
print(sorted_numbers)  # Output: [5, 6, 7, 11, 12, 13]

Sử dụng NumPy để sắp xếp array

NumPy là một thư viện mạnh mẽ cho tính toán khoa học trong Python. Nó cung cấp phương thức numpy.sort() để sắp xếp array.

Cú pháp

numpy.sort(array, axis=-1, kind=None, order=None)

• array: Array cần sắp xếp.
• axis: Trục dọc theo đó các phần tử sẽ được sắp xếp. Mặc định là -1 (sắp xếp theo trục cuối cùng).
• kind: Thuật toán sắp xếp. Các giá trị có thể là 'quicksort', 'mergesort', 'heapsort', 'stable'.
• order: Khi array là một array có các trường được định nghĩa, tham số này chỉ định các trường nào sẽ được so sánh đầu tiên, thứ hai, v.v.

Ví dụ

import numpy as np

# Tạo một array numpy các số nguyên
numbers = np.array([3, 2, 0, 1])

# Sắp xếp array
sorted_numbers = np.sort(numbers)
print(sorted_numbers)  # Output: [0, 1, 2, 3]

# Sắp xếp array 2D
array_2d = np.array([[3, 2, 4], [5, 0, 1]])
sorted_array_2d = np.sort(array_2d, axis=1)
print(sorted_array_2d)
# Output:
# [[2 3 4]
#  [0 1 5]]

Kết luận

Trong Python, có nhiều cách để sắp xếp array, từ các phương pháp tích hợp sẵn như sort() và sorted() đến các thuật toán sắp xếp phức tạp như Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, và Heap Sort. Mỗi phương pháp có ưu điểm và nhược điểm riêng, và việc lựa chọn phương pháp nào phụ thuộc vào yêu cầu cụ thể của bài toán. Hy vọng bài viết này đã giúp bạn hiểu rõ hơn về cách sắp xếp array trong Python và cách sử dụng các phương pháp khác nhau để đạt được mục tiêu của bạn.