Mô phỏng các thuật toán sắp xếp bằng Python

Các thuật toán sắp xếp

Bạn có thể sử dụng Python để mô phỏng các thuật toán sắp xếp hiện nay. Một vài thuật toán sắp xếp phổ biến bao gồm:

1. Sắp xếp nổi bọt (Bubble sort):

def bubbleSort(arr):
    n = len(arr)
 
    # Lặp qua tất cả các phần tử trong mảng
    for i in range(n):
 
        # Lặp qua tất cả các phần tử trong mảng
        for j in range(0, n-i-1):
 
            # Nếu phần tử cuối cùng lớn hơn phần tử trước đó, thì hoán vị
            if arr[j] > arr[j+1] :
                arr[j], arr[j+1] = arr[j+1], arr[j]
 
    return arr

2. Sắp xếp chọn (Selection sort):

def selectionSort(arr):
    n = len(arr)
 
    # Lặp qua tất cả các phần tử trong mảng
    for i in range(n):
 
        # Tìm phần tử nhỏ nhất trong mảng
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
 
        # Hoán vị phần tử nhỏ nhất với phần tử đầu tiên
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
 
    return arr

3. Sắp xếp chèn (Insertion sort):

def insertionSort(arr):
    n = len(arr)
    # Lặp qua tất cả các phần tử trong mảng
    for i in range(1, n):

        key = arr[i]

        # Di chuyển tất cả các phần tử của mảng lớn hơn key về sau 1 vị trí
        j = i-1
        while j >= 0 and key < arr[j] :
                arr[j + 1] = arr[j]
                j -= 1
        arr[j + 1] = key

    return arr

4. Sắp xếp nhanh (Quick sort):

def quickSort(arr, low, high):
    if low < high:
 
        # Chọn phần tử giữa làm pivot
        pivot = partition(arr, low, high)
 
        # Sắp xếp bên trái và bên phải của pivot
        quickSort(arr, low, pivot-1)
        quickSort(arr, pivot+1, high)
    return arr

5. Sắp xếp Shell (Shell sort):

def shellSort(arr):
    n = len(arr)
    gap = n//2
 
    # Lặp đến khi gap = 0
    while gap > 0:
 
        # Lặp qua tất cả các phần tử trong mảng
        for i in range(gap, n):
 
            # Lấy giá trị phần tử đang xét
            temp = arr[i]
 
            # So sánh với tất cả các phần tử trước nó
            j = i
            while  j >= gap and arr[j-gap] >temp:
                arr[j] = arr[j-gap]
                j -= gap
 
            # Gán giá trị vừa tìm được vào vị trí đúng
            arr[j] = temp
        gap //= 2
 
    return arr

Chú ý: Các thuật toán trên đều có thể có những biến thiệu trong thời gian và không gian, tùy vào dữ liệu và cách thức sắp xếp.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *