Banner-baigiang-1090_logo1
Banner-baigiang-1090_logo2

MUỐN TẮT QUẢNG CÁO?

Thư mục

Quảng cáo

Thống kê

  • truy cập   (chi tiết)
    trong hôm nay
  • lượt xem
    trong hôm nay
  • thành viên
  • 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

    ViOLET Chào mừng năm học mới

    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: 2
    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