TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu và giải thuật: Sắp xếp - Nguyễn Mạnh Hiển (HKI năm 2020-2021)

Bài giảng "Cấu trúc dữ liệu và giải thuật: Sắp xếp" cung cấp cho người học các kiến thức: Sắp xếp chọn, sắp xếp nổi bọt, sắp xếp chèn, sắp xếp vun đống, sắp xếp trộn, sắp xếp nhanh. | Sắp xếp Sorting Nguyễn Mạnh Hiển hiennm@ Nội dung 1. Sắp xếp chọn 2. Sắp xếp nổi bọt 3. Sắp xếp chèn 4. Sắp xếp vun đống 5. Sắp xếp trộn 6. Sắp xếp nhanh 1. Sắp xếp chọn selection sort Sắp xếp chọn Dãy A gồm n phần tử a0 a1 an-1. Mỗi bước xét một danh sách con chưa sắp xếp unsorted sublist - USL . Có n-1 bước Bước 0 USL0 a0 a1 an-1 Bước 1 USL1 a1 an-1 Bước n-2 USLn-1 an-2 an-1 Sắp xếp chọn tiếp Mỗi bước Tìm phần tử nhỏ nhất amin trong USL. Đổi chỗ amin và phần tử đầu tiên của USL. Dịch chuyển biên trái của USL sang phải một vị trí. Ví dụ sắp xếp chọn Ban đầu 64 25 12 22 11 11 64 Sau bước 0 11 25 12 22 64 12 25 Sau bước 1 11 12 25 22 64 22 25 Sau bước 2 11 12 22 25 64 25 25 Sau bước 3 11 12 22 25 64 Danh sách con chưa sắp xếp được gạch chân Cài đặt sắp xếp chọn template void selectionSort vector amp a for int i 0 i lt - 1 i int vt i Vị trí của min for int j i 1 j lt j if a vt gt a j vt j Cập nhật vị trí của min if vt i Đổi chỗ min và phần tử đầu USL T tg a vt a vt a i a i tg Phân tích sắp xếp chọn Đếm số phép so sánh a vt gt a j . Vòng for bên trong lặp với j từ i 1 đến n-1 tức là có n-1-i phép so sánh. Vòng for bên ngoài lặp với i từ 0 đến n-2. 2 1 1 2 1 0 1 2 2 2. Sắp xếp nổi bọt bubble sort Sắp xếp nổi bọt Mỗi bước duyệt qua các phần tử a0 a1 ak. Tại mỗi phần tử ai i lt k So sánh ai với ai 1 Đổi chỗ nếu chúng chưa đúng thứ tự Sau mỗi bước phần tử lớn nhất sẽ được đặt nổi bọt xuống cuối dãy ak là max . Ví dụ sắp xếp nổi bọt Ban đầu 64 25 12 22 11 k n-1-0 Sau bước 0 25 12 22 11 64 k n-1-1 Sau bước 1 12 22 11 25 64 k n-1-2 Sau bước 2 12 11 22 25 64 k n-1-3 Sau bước 3 11 12 22 25 64 Danh sách con chưa sắp xếp được gạch chân Cài đặt sắp xếp nổi bọt template void bubbleSort vector amp a for int i 0 i lt -1 i Bước i for int j 0 j lt -1-i j if a j gt a j 1 T tg a j a j a j 1 a j 1 tg Phân tích sắp xếp nổi bọt Đếm số phép so sánh a j gt a j 1 . Vòng for bên trong lặp với j từ 0 đến n-2-i tức là có n-1-i phép so sánh. Vòng for bên .

• Cơ sở dữ liệu
• Cấu trúc dữ liệu
• Cấu trúc dữ liệu và giải thuật
• Bài giảng Cấu trúc dữ liệu
• Sắp xếp
• Sắp xếp chọn
• Sắp xếp nổi bọt
• Sắp xếp chèn
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm
• Cấu trúc dữ liệu cây đỏ đen
• Cấu trúc dữ liệu cho nút cây đỏ đen
• Phép biến đổi cây đỏ đen cân bằng
• giáo trình cấu trúc dữ liệu
• bài tập cấu trúc dữ liệu
• đề cương cấu trúc dữ liệu
• lập trình dữ liệu
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Cơ sở dữ liệu
• Quan hệ giải thuật
• Cấu trúc dữ liệu cơ bản
• Đánh giá cấu trúc dữ liệu
• Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu có cấu trúc
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Kiểu dữ liệu trừu tượng
• Kiểu dữ liệu cây
• Phân loại cây
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Ngôn ngữ lập trình
• Cấu trúc chương trình
• Cấu trúc điều khiển
• Tài liệu Cấu trúc dữ liệu
• Cấu trúc dữ liệu căn bản
• Khái niệm cấu trúc dữ liệu
• Độ phức tạp thuật toán
• tiếp cận lập trình
• thuật toán
• thuật toán trong cấu trúc dữ liệu
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp