×

Cài đặt thuật toán Pancake Sort trong lập trình

Avatar of admin
admin 0 Views

Thuật toán Pancake Sort là một trong những thuật toán sắp xếp thú vị và độc đáo, sử dụng ý tưởng tương tự như việc lật bánh pancake để sắp xếp các phần tử trong một dãy. Mục tiêu chính là sắp xếp các phần tử theo thứ tự tăng dần bằng cách thực hiện một loạt các thao tác lật (flip).

Nguyên lý hoạt động

Thuật toán này hoạt động dựa trên hai thao tác chính:

  1. Xác định phần tử lớn nhất chưa được sắp xếp.
  2. Di chuyển phần tử này lên đầu dãy và sau đó chuyển nó xuống vị trí chính xác thông qua các phép lật.

Các bước thực hiện

  1. Tìm phần tử lớn nhất trong dãy: Xác định phần tử lớn nhất trong dãy chưa được sắp xếp.
  2. Lật từ phần tử này đến đầu dãy: Thực hiện phép lật từ vị trí phần tử vừa tìm được lên đầu dãy. Điều này sẽ đưa phần tử này lên đầu.
  3. Lật từ đầu dãy đến vị trí đích: Tiếp tục lật từ đầu dãy đến vị trí mà phần tử lớn nhất nên được đặt. Điều này sẽ đưa phần tử lớn nhất về đúng vị trí cuối cùng của dãy chưa được sắp xếp.
  4. Lặp lại quá trình: Giảm kích thước của dãy chưa sắp xếp và tiếp tục quá trình với phần còn lại của dãy.

Ví dụ minh họa

Giả sử chúng ta có một dãy các số: [3, 2, 4, 1].

  • Bước 1: Phần tử lớn nhất trong toàn dãy là 4 tại vị trí 2.

    • Lật toàn bộ dãy từ vị trí 2 đến đầu: [4, 2, 3, 1].
    • Lật toàn bộ dãy từ đầu đến vị trí 3: [1, 3, 2, 4].

  • Bước 2: Phần tử lớn nhất trong dãy còn lại là 3 tại vị trí 1.

    • Lật toàn bộ dãy từ vị trí 1 đến đầu: [3, 1, 2].
    • Lật toàn bộ dãy từ đầu đến vị trí 2: [2, 1, 3, 4].

  • Bước 3: Cuối cùng, phần tử lớn nhất trong dãy còn lại là 2 tại vị trí 0.

    • Lật toàn bộ dãy từ vị trí 0 đến đầu: [1, 2, 3, 4].

Như vậy, sau các bước lật, dãy đã được sắp xếp.

Mã giả (Pseudocode)

Dưới đây là mã giả của thuật toán nhằm giúp hiểu rõ hơn về các bước thực hiện:

function pancakeSort(arr):
    n = length(arr)
    for i from n to 1:
        max_idx = findMaxIndex(arr, i)
        if max_idx != i-1:
            flip(arr, max_idx)
            flip(arr, i-1)
    return arr

function findMaxIndex(arr, n):
    max_idx = 0
    for i from 1 to n-1:
        if arr[i] > arr[max_idx]:
            max_idx = i
    return max_idx

function flip(arr, k):
    start = 0
    while start < k:
        swap(arr[start], arr[k])
        start = start + 1
        k = k - 1

Triển khai trong một ngôn ngữ lập trình

Dưới đây là ví dụ triển khai bằng Python:

def pancakeSort(arr):
    def flip(sub_arr, k):
        start = 0
        while start < k:
            sub_arr[start], sub_arr[k] = sub_arr[k], sub_arr[start]
            start += 1
            k -= 1

    def findMaxIndex(sub_arr, n):
        max_idx = 0
        for i in range(1, n):
            if sub_arr[i] > sub_arr[max_idx]:
                max_idx = i
        return max_idx

    n = len(arr)
    for i in range(n, 1, -1):
        max_idx = findMaxIndex(arr, i)
        if max_idx != i - 1:
            flip(arr, max_idx)
            flip(arr, i - 1)

    return arr

# Test
arr = [3, 2, 4, 1]
sorted_arr = pancakeSort(arr)
print(sorted_arr) # Output: [1, 2, 3, 4]

Kết luận

Việc cài đặt thuật toán sắp xếp bằng động tác lật bánh pancake không chỉ giúp tăng cường hiểu biết về các phương pháp sắp xếp mà còn mang lại nhiều bài học về việc sử dụng các phép toán thao tác trực tiếp trên cấu trúc dãy. Hy vọng qua bài viết này, bạn đã nắm bắt được cách cài đặt và áp dụng thuật toán pancake trong lập trình.

Comments

Bài viết liên quan