Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Bài giảng Cấu trúc dữ liệu và giải thuật: Giải thuật sắp xếp nổi bọt, chèn, chọn gồm các nội dung chính sau giới thiệu về giải thuật sắp xếp nổi bọt, chèn, chọn; bài toán sắp xếp; các thuật toán sắp xếp đơn giản; các bước thuật toán; cài đặt thuật toán bubble sort. Mời các bạn cùng tham khảo! | 2 KHOA CÔNG NGHỆ THÔNG TIN 3 KHOA CÔNG NGHỆ THÔNG TIN 34 3 4 8 a 0 a 1 là cặp nghịch thế 4 KHOA CÔNG NGHỆ THÔNG TIN 5 KHOA CÔNG NGHỆ THÔNG TIN 6 KHOA CÔNG NGHỆ THÔNG TIN 7 KHOA CÔNG NGHỆ THÔNG TIN Cho 1 dãy các phần tử như sau 5 1 6 2 4 3 Lượt 1 Lượt 2 Lượt 3 5 1 6 2 4 3 1 5 2 4 3 6 1 2 4 3 5 6 1 5 6 2 4 3 1 2 5 4 3 6 1 2 3 4 5 6 1 5 2 6 4 3 1 2 4 5 3 6 1 2 3 4 5 6 1 5 2 4 6 3 1 2 4 3 5 6 1 2 3 4 5 6 1 5 2 4 3 6 1 2 4 3 5 6 1 2 3 4 5 6 8 KHOA CÔNG NGHỆ THÔNG TIN Input Dãy các đối tượng Các số chưa sắp xếp A 0 A 1 A n-1 . Output Dãy các đối tượng đã được sắp xếp Các số tăng dần A 0 A 1 A n-1 Actions void BubbleSort int a int n int i j for i 0 i lt n-1 i for j i j gt n-1 j if a j lt a j1 nếu sai vị trí thì đổi chỗ Swap a j a j 1 End 9 KHOA CÔNG NGHỆ THÔNG TIN Giải thuật Nổi bọt - Bubble Sort B.1 Gán i 0 B.2 Gán j 0 danh sách có n phần tử a0 a1 a2 an-1 B.3 Nếu A j gt A j 1 thì Hoán đối chỗ giữa A j và A j 1 B.4 Nếu j lt n i 1 -Đúng thì j j 1 và quay lui bước 3 -Sai thì chuyển sang bước 5 B.5 Nếu i lt n 1 -Đúng thì i i 1 và quay lui bước 2 -Sai thì dừng Kết Thúc. 10 KHOA CÔNG NGHỆ THÔNG TIN Bài tập 1 Áp dụng giải thuật sắp xếp Nổi bọt Bubble Sort. Cho Mảng A 19 13 6 B.1 i 0 B.2 j 0 B.3 nếu A j gt A j 1 A 0 gt A 1 19 gt 13 thì Hoán đổi giữa 19 và 13 13 19 6 B.4 nếu j lt n-i-1 0 lt 2-0-1 Đúng thì j j 1 0 1 1 và quay lui B.3 B.3 nếu A j gt A j 1 A 1 gt A 2 19 gt 6 thì Hoán đổi giữa 19 và 6 13 6 19 B.4 nếu j lt n-i-1 1 lt 2-0-1 Sai thì chuyển sang B.5 - Giải thuật Nổi bọt - Bubble Sort B.5 nếu i lt n-1 0 lt 1 Đúng thì i i 1 0 1 1 và quay lại B.2 B.1 Gán i 0 B.2 j 0 i 1 B.2 Gán j 0 B.3 nếu A 0 gt A 1 13 gt 6 thì Hoán đổi giữa 13 và 6 B.3 Nếu A j gt A j 1 thì Hoán đối chỗ giữa A j và A j 1 B.4 Nếu j lt n i 1 6 13 19 -Đúng thì j j 1 và quay lui bước 3 B.4 Nếu j lt n i 1 0 lt 0 Sai thì chuyển sang B.5 -Sai thì chuyển sang bước 5 B.5 Nếu i lt n 1 1 lt 1 Sai thì Dừng Kết thúc. B.5 Nếu i lt n 1 Vậy mảng được sắp xếp là -Đúng thì i i 1 và quay lui bước 2 6 13 19 . -Sai thì dừng .