Đỉnh có bậc vào và bậc ra cùng bằng 0 gọi là đỉnh cô lập. Đỉnh có bậc vào bằng 1 và bậc ra bằng 0 gọi là đỉnh treo, cung có đỉnh cuối là đỉnh treo gọi là cung treo | Chương 5: sắp xếp CHƯƠNG 5 SẮP XẾP 1 Chương 5: Sắp xếp Phương pháp chọn Phương pháp chèn Phương pháp chèn nhị phân Phương pháp nổi bọt Phương pháp sắp xếp nhanh Phương pháp vun đống 2 Bai toan sắp xếp ̀ ́ Có môt tâp n đôi tượng. Môi đôi tượng ̣ ̣ ́ ̃ ́ có nhiêu thuôc tinh, được thể hiên băng môt ̀ ̣ ́ ̣ ̀ ̣ kiêu ban ghi gôm nhiêu trường. Sắp xếp là ̉ ̉ ̀ ̀ quá trình bố trí lại các bản ghi theo một trường goi là khoa. ̣ ́ Ví dụ trong bảng danh bạ gồm các bản ghi có tên cơ quan, địa chỉ, số điện thoại. Sổ danh bạ thường được sắp xếp theo trường khóa là tên cơ quan để dễ tìm kiếm. 3 Bai toan sắp xếp ̀ ́ Sắp xếp là thao tác cần thiết hay gặp trong quá trình lưu trữ và quản lý dữ liệu. Có 2 phương pháp sắp xếp: sắp xếp trong tác động lên các bản ghi lưu trữ ở bộ nhớ trong và Sắp xếp ngoài liên quan đến tập lớn các bản ghi lưu trữ trên tệp. Chương này chỉ xét bài toán sắp xếp trong theo thứ tự tăng của khóa. Sắp xếp theo thứ tự giảm được làm hoàn toàn tương tự. 4 Phương pháp chọn Ý tưởng: Dãy khóa cần sắp xếp là k[1],k[2], , k[n]. Ở lượt thứ i (i=1,2,3, ,n-2) ta sẽ chọn trong dãy khóa k[i+1], ., k[n] khóa nhỏ nhất và đổi chỗ nó với k[i] Sau n-1 lượt khóa từ nhỏ đến lớn sẽ được sắp xếp ở các vị trí thứ 1, thứ 2, thứ n-1, thứ n. 5 Phương pháp chọn Thuật toán: void SX_chon(int *k, int n) {int i,x; for(i=1; Phương pháp chèn Ý tưởng: Dãy khóa cần xếp là k[1], k[2], , k[n]. Đầu tiên khóa k[1] chỉ có một khóa đã được sắp xếp. Xét thêm k[2],so sánh nó với k[1] để xác định chỗ chèn nó vào và ta có 2 khóa được sắp xếp. Đối với k[3] lại so sánh với k[2], k[1] và cứ như vậy đến khi xét xong k[n]. 7 Phương pháp chèn Cài đặt: Để có chỗ cho khóa mới phải dịch chuyển các khóa lùi lại sau và dùng X làm ô nhớ phụ chứa khóa đang được xét. Để khóa mới dù ở vị trí đầu tiên cũng được chèn vào giữa khóa nhỏ và lớn hơn nó, ta thêm vào khóa giả k[0]=-∞.
