ĐỀ TÀI: Trình bày thuật toán sắp xếp Radixsort

Khái niệm sắp xếp dường như đã gắn liền với xã hội loài người từ thuở ban đầu của nền văn minh. Nó đơn giản thể hiện trong việc sắp hàng, trong việc phân công công việc,… Ngày nay, trong một thế giới mà khoa học công nghệ mỗi ngày phát triển như vũ bão và nhu cầu khai thác, tìm kiếm thông tin của con người ngày càng cao thì việc nâng cao tính hiệu quả của các giải thuật sắp xếp cũng ngày càng trở nên quan trọng....
Nội dung trích xuất từ tài liệu:
ĐỀ TÀI: Trình bày thuật toán sắp xếp Radixsort BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG CAO ĐẲNG CN & KD VIỆT TIẾN KHOA MÁY TÍNHMôn: Cấu trúc dữ liệu & giải thuật ĐỀ TÀI: Trình bày thuật toán sắp xếp Radixsort Giảng viên hướng dẫn : Trịnh Đức Tính Sinh viên thực hiện : Nguyễn Đình Hải Quân Lớp : C10T1 MSSV : 100157 Đà Nẵng, Ngày 25 tháng 1 năm 2013Báo Cáo Môn Học: CTDL> SVTH: Nguyễn Đình Hải Quân MỤC LỤC Sinh viên thực hiện : Nguyễn Đình Hải Quân.............................................1 MSSV : 100157..................................................................................................................1 Đà Nẵng, Ngày 25 tháng 1 năm 2013..........................................................................................1 LỜI NÓI ĐẦU...............................................................................................................................3 PHẦN I LÝ THUYẾT & THUẬT TOÁN VỀ RADIX SORT ......................................................................................................................................................4 1.Giới thiệu về Radix Sort.........................................................................................................4 2.Mô phỏng qui trình.................................................................................................................4 3. Thuật toán sắp xếp Radix sort.............................................................................................4 5. Ðánh giá độ phức tạp giải thuật...........................................................................................7 PHẦN II.........................................................................................................................................8 CHƯƠNG TRÌNH MINH HOẠ TRỰC QUAN RADIX SORT ......................................................................................................................................................8 a.Viết mã.................................................................................................................................10 2. Chương trình minh hoạ bằng C++......................................................................................14 III. Kết Luận Với những kiến thức đã học, với sự giúp đỡ tận tình của các anh chị trên diễn đàn cộng đồng C việt, cùng giáo viên bộ môn em đã thu thập được những kinh nghiệm hết sức quý báu.....18 Trang 2Báo Cáo Môn Học: CTDL> SVTH: Nguyễn Đình Hải Quân LỜI NÓI ĐẦU Khái niệm sắp xếp dường như đã gắn liền với xã hội loài người từ thuở ban đầucủa nền văn minh. Nó đơn giản thể hiện trong việc sắp hàng, trong việc phân công côngviệc,… Ngày nay, trong một thế giới mà khoa học công nghệ mỗi ngày phát triển nhưvũ bão và nhu cầu khai thác, tìm kiếm thông tin của con người ngày càng cao thì vi ệcnâng cao tính hiệu quả của các giải thuật sắp xếp cũng ngày càng trở nên quan trọng. Trong hầu hết các hệ lưu trữ, quản lý dữ liệu thao tác tìm kiếm là thao tác cơ bảnđể khai thác thông tin. Để việc tìm kiếm trở nên hiệu quả và nhanh chóng thì dữ liệutrong hệ thống cần được tổ chức theo một trật tự nào đó và điều này đòi hỏi chúng taphải xây dựng những giải thuật sắp xếp thích hợp. Bài báo cáo này nhằm mục đích giới thiệu về Radix Sort, một giải thuật s ắp xếpđặc biệt vì nó gần giống cách sắp xếp theo lô của mà chúng ta vẫn hay làm trong cuộcsống hằng ngày. Hy vọng nhận được những nhận xét và đánh giá chân thành từ thầy và các bạn. Trang 3Báo Cáo Môn Học: CTDL> SVTH: Nguyễn Đình Hải Quân PHẦN I LÝ THUYẾT & THUẬT TOÁN VỀ RADIX SORT1.Giới thiệu về Radix Sort - Radix Sort là một thuật toán sắp xếp tiếp cận theo một hướng hoàn toàn khác so với các thuật toán khác. Nếu như trong các thuật toán khác, cơ sở để sắp xếp luôn là việc so sánh giá trị của 2 phần tử thì Radix sort lại dựa trên nguyên tắc phân loại th ư của bưu điện. Nó không hề quan tâm đến việc so sánh giá trị của phần tử và bản thân việc phân loại và trình tự phân loại sẽ tạo ra thứ tự cho các phần tử. - Ta biết rằng, để chuyển một khối lượng thư lớn đến tay người nhận ở nhiềuđịa phương khác nhau, bưư điện thường tổ chức một hệ thống phân loại thư phân cấp.Trước tiên, các thư đến cùng một tỉnh, thành phố sẽ được sắp chung vào một lô để gửiđến tỉnh thành tương ứng. Bưu điện các tỉnh thành này lại thực hiện công việc tươngtự. Các thư đến cùng một quận, huyện sẽ được xếp vào chung mộ ...