Bubble Sortv

Tư tưởng :

Cho dãy ban đầu gồm n phần tử X1,X2,...,Xn chưa được sắp thứ tự

- Lượt 1: Xếp số thứ nhất : quét các cặp phần tử Xj từ cuối dãy về đầu

dãy nếu các cặp X[j]<X[j-1]

à phần tử nhỏ nhất sẽ ở đầu dãy à phần tử này đã được xếp .

...

- Lượt i : Quét từ cuối dãy đến phần tử thứ i ,nếu các cặp X[j]<X[j-1] thì

đổi giá trị à phần tử thứ i là phần tử được xếp .

- Thuật toán kết thúc khi xếp được n-1 phần tử .

Thủ tục :

void BubbleSort(int X[20],int n)

{

int tg;

for(int i=1;i<n;i++)

for(int j=n;j>i;j--)

if(X[j-1]>X[j])

{

tg=X[j];

X[j]=X[j-1];

X[j-1]=tg;

}

}

+ độ phức tạp của thuật toán :

Đánh giá thuật toán :

- Có n-1 lần duyệt

- Có n-1 lần so sánh trong mỗi lần duyệt

à C(n)=(n-1)*(n-1)=n2-2n+1

Bậc của C(n) là : O(n2)

Vậy thời gian thực hiện giải thuật Bubble Sort có

độ phức tạp là O(n2