DSA_1: Sắp xếp nổi bọt | Bubble sort.

Góc nhìn:

• Dưới góc nhìn của Sắp xếp nổi bọt , mảng đã sắp xếp là mảng mà trong hai phẩn tử bất kì liền kề, phần tử đứng sau luôn lớn hơn phần tử đứng trước.

Thuật toán:

• B1: Duyệt mảng từ đầu đến cuối, nếu phần tử đứng sau nhỏ hơn phần tử đứng trước thì đổi chỗ chúng.
• B2: Nếu duyệt hết một vòng mà không phải đổi chỗ bất kỳ phần tử nào ==> mảng đã sắp xếp, dừng thuật toán. Nếu không, lặp lại B1.

Code Python:

xxxxxxxxxx
def bubbleSort(arr):
        n = len(arr)
        for i in range(n):
            swap = False
            for j in range(n-1):
                if arr[j]>arr[j+1]:
                    arr[j], arr[j+1] = arr[j+1], arr[j]
                    swap = True
            if swap == False:
                return None

Độ phức tạp thuật toán:

• Best: $\Omega (n)=n$
• Average: $\Theta (n) = n^2$
• Worst: $\Omicron(n) = n^2$