TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu và giải thuật: Sắp xếp

Trong chương này các bạn sẽ tìm hiểu một số bài toán sắp xếp và một số thuật toán sắp xếp như: Sắp xếp chèn – insertion sort, sắp xếp lựa chọn – selection sort, sắp xếp nổi bọt – bubble sort, sắp xếp shell-sort, sắp xếp trộn – merge sort, sắp xếp nhanh – quick sort, sắp xếp vun đống – heap sort. . | Chương 5 Sắp xếp hiepnd@ Bài toán săp xêp Để tìm kiếm thông tin hiệu quả ta phải lưu giữ chúng theo một thứ tự nào đó. Cách sắp xếp sách trong thư viện Lưu trữ từ trong từ điển Sắp xếp là một trong những bài toán quan trọng trong xử lý thông tin Nhiều thuật toán đã được đề xuất. Ta chỉ xét bài toán sắp xếp trong không xét sắp xếp ngoài 3 29 2011 Nội dung Bài toán sắp xếp Một số thuật toán sắp xếp Sắp xếp chèn - insertion sort Sắp xếp lựa chọn - selection sort Sắp xếp nổi bọt - bubble sort Sắp xếp shell-sort Sắp xếp trộn - merge sort Sắp xếp nhanh - quick sort Sắp xếp vun đống - heap sort Bài toán sắp xếp Mỗi bản ghi có một khóa key ta có thể áp dụng các phép so sánh trên khóa. Sắp xếp các bản ghi bằng cách sắp xếp đối với khóa tương ứng của chúng. struct node long masoSV char hoten 30 char dỉachỉ 50 float dỉemTB 1 sắp xếp chèn New Ordered entry list Move Move Complete last entry previous Insertion entry b c d Chèn một phần tử mới vào một danh sách có thứ tự VD. Danh sách các con vật sắp theo thứ tự bảng chữ cái 3 29 2011 Sắp xếp chèn sắp xếp bằng cách chèn Bắt đầu bằng một danh sách có thứ tự rỗng Lần lượt chèn thêm các phần tử cần sắp xếp vào danh sách có thứ tự đó. Trong quá trình chèn phải đảm bảo danh sách vẫn đúng thứ tự Kết thúc ta thu được danh sách các phần tử đã được sắp xếp theo thứ tự 2 sắp xếp chèn Các phần tử cần sắp xếp hen cow cat ram ewe dog I hen I Thêm hen cow hen Thêm cow cat cow hen Thêm cat Thêm ram cat cow hen ram Sắp xếp chèn Lưu trữ bằng mảng void insert int A j int endj int value if end -l end A end value else int pos 0 i while A pos value pos for i end i pos i-- A i l A i A pos value end end l 3 29 2011 Sắp xếp chèn Hàm sắp xếp chèn các phần tử cần sắp xếp được lưu ở mảng B kết quả được lưu ở mảng A n là số phần tử void insertionsort const int B int n int A int end -l for int i 0 i n i insert A end B i

• Cơ sở dữ liệu
• Cấu trúc dữ liệu
• Thuật toán sắp xếp
• Bài toán sắp xếp
• Sắp xếp chèn
• Sắp xếp lựa 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
• Bài giảng Cấu trúc dữ liệu
• 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