PP sắp xếp nổi bọt

PHƯƠNG PHÁP SẮP XẾP NỔI BỌT

Sinh viên thực hiện: Bùi Văn Hùng
1. Ý TƯỞNG THUẬT TOÁN
Giả sử cần sắp xếp dãy gồm n phần tử a[1..n].
Đi từ trái sang phải mảng A. nếu gặp 2 phần tử kề nhau mà ngược thứ tự sắp xếp (Khóa của phần tử trước lớn hơn khóa của phần tử sau) thì đổi chỗ chúng cho nhau. Kết thúc bước đầu tiên A[n], ta được có giá trị lớn nhất trong dãy. Còn các phần tử nhỏ hơn sẽ được “nổi” dần lên trên.
Lặp lại quá trình trên với các đoạn đầu a[1..i] với I chạy giảm từ n xuống đến 2, ta sẽ nhận được toàn bộ dãy a[1..n] được sắp xếp.
Procedure BUBBLE_SORT(Var A:MT, n:integer)
Var i,j:Integer;
Begin
For i:=n downto 2 do
For j:=1 to i-1 do
If A[j] > A[j+1] then SWAP(A[i],A[j+1]);
End;
2. THỦ TỤC
SẮP XẾP NỔI BỌT (BUBBLE SORT)
8
15
3
10
5
9
i
Cho dãy khóa sắp xếp: 8 15 3 10 5 9
Có thể biểu diễn quá trình trên như sau:
3. VÍ DỤ
Phép toán tích cực: Phép toán so sánh
ở lần lặp thứ i, phép so sánh được thực hiện (i-1) lần.
ta có:
4. ĐỘ PHỨC TẠP

Nhận xét:
Trường hợp tại bước thứ i, các phần tử đều nằm đúng thứ tự thì ta có thể dừng thuật toán luôn.
Vậy ta có thể cải tiến thủ tục trên bằng cách thêm vào một biến kiểm tra kiểu Boolean, biến này sẽ nhận giá trị True nếu dãy đã sắp xếp đúng thứ tự và nhận giá trị False trong trường hợp ngược lại.
Procedure BUBBLE_SORT(Var A:MT; n:integer);
Var i,j: Integer;
kt:Boolean;
Begin
i:=n;
Kt:=False;
While (i>=2) and (not kt) do
Begin
Kt:=True;
For j:=1 to i-1 do
If A[j] > A[j+1] then
Begin
SWAP(A[i],A[j+1]);
Kt:=False;
End;
Dec(i);
End;
End;