TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 6: Giải thuật sắp xếp

Những nội dung chính được trình bày trong chương 6 gồm có: Sắp xếp chọn (selection sort), sắp xếp chèn (insert sort), sắp xếp nổi bọt (bubble sort), sắp xếp nhanh (quick sort), sắp xếp vun đống (heap sort), sắp xếp hòa nhập (merge sort). Mời các bạn cùng tham khảo. | Chương 6 Giải thuật sắp xếp 1. Sắp xếp chọn Selection Sort 2. Sắp xếp chèn Insert Sort 3. Sắp xếp nổi bọt Bubble Sort 4. Sắp xếp nhanh Quick Sort 5. Sắp xếp vun đống Heap Sort 6. Sắp xếp hòa nhập Merge Sort Ngô Công Thắng Bài giàng CTDL amp GT - Chương 06 1. Sắp xếp chọn Selection Sort . Phương pháp Giả sử cần sắp xếp tăng dần một dãy khoá a1 a2 . an. Ý tưởng của thuật toán như sau Chọn phần tử có khoá nhỏ nhất . Đổi chỗ nó với phần tử a1. Sau đó lặp lại thao tác trên với n-1 phần tử còn lại rồi lại lặp lại như trên với n-2 phần tử còn lại . cho tới khi chỉ còn 1 phần tử. Ngô Công Thắng Bài giàng CTDL amp GT - Chương 06 . Phương pháp tiếp Ví dụ Cho dãy khoá ban đầu là 6 10 1 8 9 với n 5. i 1 1 10 6 8 9 i 2 1 6 10 8 9 i 3 1 6 8 10 9 i 4 1 6 8 9 10 Ngô Công Thắng Bài giàng CTDL amp GT - Chương 06 . Phương pháp tiếp Procedure selectionSort a n For i 1 to n-1 Do Begin 1 Tìm phần tử nhỏ nhất ở vị trí k k i For j i 1 To n Do If a j lt a k then k j 2 Đổi chỗ phần tử nhỏ nhất ở vị trí k cho vị trí i If k i then a k a i End Return Ngô Công Thắng Bài giàng CTDL amp GT - Chương 06 2. Sắp xếp chèn Insert Sort . Phương pháp Phương pháp này được những người chơi bài hay dùng. Giả sử cần sắp xếp tăng dần dãy khoá a1 a2 . an. Ý tưởng thuật toán như sau Các phần tử được chia thành dãy đích a1 . ai-1 kết quả và dãy nguồn ai . an. Bắt đầu với i 2 ở mỗi bước phần tử thứ i của dãy nguồn được lấy ra và chèn vào vị trí thích hợp trong dãy đích sao cho dãy đích vẫn tăng dần. Sau đó i tăng lên 1 và lặp lại. Ngô Công Thắng Bài giàng CTDL amp GT - Chương 06 . Phương pháp Ví dụ Cho dãy khoá 6 10 1 7 4 với n 5 dãy số có 5 phần tử . Dãy đích Dãy nguồn 6 10 1 7 4 i 2 6 10 1 7 4 i 3 1 6 10 7 4 i 4 1 6 7 10 4 i 5 1 4 6 7 10 Ngô Công Thắng Bài giàng CTDL amp GT - Chương 06 Thủ tục chèn Procedure insertSort a n 1 a 0 - 2 For i 2 to n Do Begin tg a i j i-1 While tg . Đánh giá thuật toán Trường hợp xấu nhất nếu dãy khoá sắp theo thứ tự ngược với thứ tự sắp .

• Cơ sở dữ liệu
• Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Sắp xếp chọn
• Sắp xếp chèn
• Sắp xếp nổi bọt
• 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
• 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
• Ngôn ngữ diễn đạt giải thuật
• Thiết kế và phân tích giải thuật
• Giải thuật đệ quy
• 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
• Tổng quan về giải thuật
• Kiểu dữ liệu
• Các tiêu chuẩn đánh giá dữ liệu
• phân tích thiết kế
• thiết kế hướng đối tượng
• Cách diễn đạt giải thuật
• Phân tích giải thuật
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp