Tìm kiếm theo tiêu đề

Tìm kiếm Google

Quảng cáo

Quảng cáo

Quảng cáo

Hướng dẫn sử dụng thư viện

Hỗ trợ kĩ thuật

Liên hệ quảng cáo

  • (04) 66 745 632
  • 0166 286 0000
  • contact@bachkim.vn

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

Nhấn vào đây để tải về
Báo tài liệu có sai sót
Nhắn tin cho tác giả
(Tài liệu chưa được thẩm định)
Nguồn:
Người gửi: Bùi Văn Hùng
Ngày gửi: 19h:37' 13-04-2017
Dung lượng: 321.0 KB
Số lượt tải: 3
Số lượt thích: 0 người
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;
 
Gửi ý kiến