Mô phỏng thuật toán Sắp xếp Gnome

Gnome Sort · Nhóm: Sắp xếp

Gnome Sort (sắp xếp chú lùn): đứng ở vị trí pos, nếu số hiện tại không nhỏ hơn số bên trái thì bước tới, ngược lại đổi chỗ và lùi một bước, cứ thế đi hết mảng.

Ý tưởng

Đặt con trỏ pos ở đầu; nếu pos = 0 hoặc a[pos] ≥ a[pos-1] thì bước tới (pos tăng).

Nếu a[pos] < a[pos-1] thì đổi chỗ hai phần tử và lùi lại (pos giảm) để kiểm lại.

Lặp cho tới khi pos vượt cuối mảng, khi đó dãy đã sắp xong.

Vì sao đúng

Cực kỳ gọn, chỉ một vòng lặp và một con trỏ, không cần vòng lặp lồng, giống chèn trực tiếp nhưng viết ngắn hơn.

Mã Python

def gnome_sort(a):
    n = len(a)
    pos = 0
    while pos < n:
        if pos == 0 or a[pos] >= a[pos-1]:
            pos += 1
        else:
            a[pos], a[pos-1] = a[pos-1], a[pos]
            pos -= 1
    return a

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.