Đang chuẩn bị liên kết để tải về tài liệu:
Giáo trình CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT - Chương 3

Chương 3: KỸ THUẬT SẮP XẾP (SORTING) 3.1. Khái quát về sắp xếp Để thuận tiện và giảm thiểu thời gian thao tác mà đặc biệt là để tìm kiếm dữ liệu dễ dàng và nhanh chóng, thông thường trước khi thao tác thì dữ liệu trên mảng, trên tập tin đã có thứ tự. Do vậy, thao tác sắp xếp dữ liệu là một trong những thao tác cần thiết và thường gặp trong quá trình lưu trữ, quản lý dữ liệu. Thứ tự xuất hiện dữ liệu có thể là thứ tự tăng (không giảm dần) hoặc thứ tự giảm. | ỹiá ÙU Cấu Ttú Dũ Liệu vù ỹiùi 7huật Chương 3 KỸ THUẬT SAP XEP SORTING 3.1. Khái quát về sắp xếp Để thuận tiện và giảm thiểu thời gian thao tác mà đặc biệt là để tìm kiếm dữ liệu dễ dàng và nhanh chóng thông thường trữờc khi thao tác thì dữ liệu trển màng trển tập tin đà cô thữ tự. Do vày thao tàc sàp xểp dữ liểu là mót trong những thao tàc càn thiểt và thữờng gap trong quà trình lữu trữ quàn ly dữ liểu. Thữ tư xuất hiển dữ liểu co thể là thứ tự tang khong giam dàn hoàc thữ tự giam khong tàng dàn . Trong pham vi chữờng này chúng ta sể thữc hiển viểc sàp xểp dữ liểu thểo thữ tự tàng. Viểc sàp xểp dữ liểu thểo thứ tữ giam hoàn toàn tữờng tự. Co rat nhiểu thuàt toàn sàp xểp song chung ta co thể phàn chia càc thuàt toàn sàp xểp thành hai nhom chính càn cứ vào vị trí lữu trữ cua dữ liểu trong mày tính đo là - Càc giai thuàt sàp xểp thữ tự nội sap xểp thữ tù trển dãy màng - Càc giai thuàt sàp xểp thữ tự ngoại sàp xểp thứ tự trển tàp tin filể . Cũng nhữ trong chữờng trữờc chung ta già sữ ràng moi phàn tử dữ liểu đữờc xểm xểt co mọt thành phàn khoa Kểy để nhàn diển co kiểu dữ liểu là T nào đo càc thành phàn con lai la thong tin Info liển quan đển phàn tử dữ liểu đo. Nhữ vày moi phàn tử dữ liểu co càu truc dữ liểu nhữ sau typểdểf struct DàtaElểmểnt T Kểy InfoTypể Info DataType Trong chữờng này noi riểng và tài liểu này noi chung càc thuàt toàn sàp xểp cua chung ta là sàp xểp sao cho càc phàn tử dữ liểu co thu tự tàng thểo thành phàn khoa Kểy nhàn diển. Để đờn giàn chung ta già sử ràng moi phàn tử dữ liểu chỉ là thành phàn khoa nhàn diển. 3.2. Các giải thuát sáp xếp nội Sáp xếp trên dáy máng Ở đày toàn bo dữ liểu càn sàp xểp đữờc đữa vào trong bo nhờ trong RAM . Do vày so phàn tử dữ liểu khong lờn làm do giời han cua bo nhờ trong tuy nhiển toc đo sàp xểp tữờng đoi nhanh. Càc giai thuàt sàp xểp nOi bao gồm càc nhom sau - Sàp xểp bàng phữờng phàp đểm counting sort - Sap xểp bàng phữờng phàp đo i cho ểxchangể sort - Sap xểp bang phữờng phap chon lựa sểlểction sort - Sap xểp .