tailieunhanh - Giáo trình giải thuật của Nguyễn Văn Linh part 7

Giải thuật Nói chung các giải thuật đã trình bày ở trên đều có độ phức tạp là O(n2) hoặc O(nlogn). Tuy nhiên khi kiểu dữ liệu của trường khoá là một kiểu đặc biệt, việc sắp xếp có thể chỉ chiếm O(n) thời gian. Sau đây ta sẽ xét một số trường hợp. | Giải thuật Sắp xếp BINSORT Giải thuật Nói chung các giải thuật đã trình bày ở trên đều có độ phức tạp là O n2 hoặc O nlogn . Tuy nhiên khi kiểu dữ liệu của trường khoá là một kiểu đặc biệt việc sắp xếp có thể chỉ chiếm O n thời gian. Sau đây ta sẽ xét một số trường hợp. Trường hợp đơn giản Giả sử ta phải sắp xếp một mảng A gồm n phần tử có khoá là các số nguyên có giá trị khác nhau và là các giá trị từ 1 đến n. Ta sử dụng B là một mảng cùng kiểu với A và phân phối vào phần tử b j một phần tử a i mà a i .key j. Khi đó mảng B lưu trữ kết quả đã được sắp xếp của mảng A. Ví dụ 2-7 Sắp xếp mảng A gồm 10 phần tử có khoá là các số nguyên có giá trị là các số 4 7 1 2 5 8 10 9 6 và 3 Ta sử dụng mảng B có cùng kiểu với A và thực hiện việc phân phối a 1 vào b 4 vì a 1 .key 4 a 2 vào b 7 vì a 2 .key 7 a 3 vào b 1 vì a 3 .key 1 . Hình sau minh họa cho việc phân phối các phần tử của mảng a vào mảng b. Nguyên Văn Linh Trang 39 Sưu tầm bởi Giải thuật Sắp xếp Mảng a Khóa a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a 9 a 10 4 7 1 2 5 8 10 9 6 3 X - X Ỵ Khóa Mảng b 1 2 3 4 5 6 7 8 9 10 b 1 B 2 b 3 b 4 b 5 b 6 b 7 b 8 b 9 b 10 Hình 2-18 Phân phối các phân tử a i vào các bin b j Để thực hiện việc phân phối này ta chỉ cần một lệnh lặp for i 1 to n do b a i .key a i Đây cũng là lệnh chính trong chương trình sắp xếp. Lệnh này lấy O n thời gian. Các phần tử b j được gọi là các bin và phương pháp sắp xếp này được gọi là bin sort. Trường hợp tổng quát Là trường hợp có thể có nhiều phần tử có chung một giá trị khóa chẳng hạn để sắp một mảng A có n phần tử mà các giá trị khóa của chúng là các số nguyên lấy giá trị trong khoảng với m n. Trong trường hợp này ta không thể sử dụng các phần tử của mảng B làm bin được vì nếu có hai phần tử của mảng A có cùng một khoá thì không thể lưu trữ trong cùng một bin. Để giải quyết sự đụng độ này ta chuẩn bị một cấu trúc có m bin mỗi bin có thể lưu trữ nhiều hơn một phần tử. Cụ thể là bin thứ j sẽ lưu các phần tử có khóa là

• Kỹ thuật lập trình
• Kỹ thuật lập trình
• giải thuật
• hướng dẫn giải thuật
• cấu trúc dữ liệu
• lập trình
• kỹ thuật máy tính C
• kỹ thuật lập trình C
• giáo trình kỹ thuật lập trình C
• bài tập kỹ thuật lập trình C
• tài liệu kỹ thuật lập trình C
• chuyên ngành kỹ thuật lập trình
• Bài tập kỹ thuật lập trình
• Tài liệu kỹ thuật lập trình
• Bài giảng kỹ thuật lập trình
• Ưng dụng kỹ thuật lập trình
• Ngôn ngữ C
• kỹ thuật máy tính
• môn kỹ thuật lập trình
• ôn tập kỹ thuật lập trình
• cách học kỹ thuật lập trình
• kiến thức kỹ thuật lập trình
• học môn kỹ thuật lập trình
• Đề thi Kỹ thuật lập trình cơ bản
• Câu hỏi Kỹ thuật lập trình cơ bản
• Luyện thi Kỹ thuật lập trình cơ bản
• Ôn thi Kỹ thuật lập trình cơ bản
• Bài thi Kỹ thuật lập trình cơ bản
• Tài liệu Kỹ thuật lập trình cơ bản
• giáo trình kỹ thuật lập trình
• thủ thuật lập trình
• lập trình căn bản
• kỹ thuật phần mềm
• chương trình lập trình
• giáo trình lập trình
• lập trình hướng đối tượng
• tài liệu lập trình
• chuyên ngành lập trình
• tổng quan về lập trình
• Tổng quan về kỹ thuật lập trình
• Lập trình tốt
• Nguyên tắc lập trình
• Ngôn ngữ lập trình
• ngôn ngữ C++
• Kỹ thuật lập trình căn bản
• Kỹ thuật lập trình nâng cao
• Lập trình C căn bản
• Lập trình C nâng cao