Chương trình Python BogoSort (Permutation Sort)

Trong bài viết này, chúng ta sẽ tìm hiểu giải pháp cho bài toán sau:

Đề bài – Cho một mảng, cần sắp xếp dùng Permutation Sort (BogoSort).

BogoSort dựa trên sinh và kiểm tra (generate and test).

Hãy quan sát giải pháp trong triển khai dưới đây:

Ví dụ

import random

# sort
def bogoSort(a):
    n = len(a)
    while (is_sorted(a) == False):
        shuffle(a)

# kiểm tra
def is_sorted(a):
    n = len(a)
    for i in range(0, n-1):
        if (a[i] > a[i+1]):
            return False
    return True

# hoán vị ngẫu nhiên
def shuffle(a):
    n = len(a)
    for i in range(0, n):
        r = random.randint(0, n-1)
        a[i], a[r] = a[r], a[i]

# main
a = [1, 5, 3, 4, 8, 6, 3, 4, 5]
bogoSort(a)
print("Mảng đã sắp xếp:")
for i in range(len(a)):
    print(a[i], end=" ")

Kết quả

Mảng đã sắp xếp: 1 3 3 4 4 5 5 6 8

Kết luận

Trong bài này, chúng ta đã học cách làm chương trình Python BogoSort hoặc Permutation Sort.