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

Cocktail Shaker Sort · Nhóm: Sắp xếp

Cocktail Shaker Sort là nổi bọt hai chiều: quét xuôi đẩy số lớn về cuối, rồi quét ngược đẩy số nhỏ về đầu, thu hẹp dần hai biên.

Ý tưởng

Quét xuôi từ trái sang phải, đổi chỗ cặp kề nhau ngược thứ tự, số lớn nhất trôi về cuối.

Thu hẹp biên phải rồi quét ngược từ phải sang trái, số nhỏ nhất trôi về đầu.

Thu hẹp biên trái, lặp lại; nếu một lượt không đổi chỗ nào thì mảng đã sắp xong.

Vì sao đúng

So với nổi bọt một chiều, quét luân phiên giúp những số nhỏ nằm gần cuối trồi lên nhanh hơn, giảm hiện tượng con rùa lết chậm.

Mã Python

def cocktail_sort(a):
    lo, hi = 0, len(a) - 1
    while lo < hi:
        for j in range(lo, hi):
            if a[j] > a[j+1]:
                a[j], a[j+1] = a[j+1], a[j]
        hi -= 1
        for j in range(hi, lo, -1):
            if a[j-1] > a[j]:
                a[j-1], a[j] = a[j], a[j-1]
        lo += 1
    return a

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