tailieunhanh - Bài thuyết trình nhóm 2 đề tài: cấu trúc dữ liệu

a Khái niệm sắp xếp : Sắp xếp là một quá trình bố trí lại các phần tử của một tập đối tượng nào đó theo một thứ tự ấn định . VD :Thứ tự tăng dần hay giảm dần của một dãy số./ | Giới thiệu các thành viên trong Nhóm 4 Nhóm 4 gồm 3 thành viên : Nguyễn văn Tuyến Lê thị Xim Vũ thị Băng Thuyết trình : Vũ Thị Băng Tạo lập siled : Nguyễn Văn Tuyến Biên soạn nội dung : Lê Thị Xim Biên soạn đề cương : các thành viên trong nhóm. ®Æt vÊn ®Ò a> Khái niệm sắp xếp : Sắp xếp là một quá trình bố trí lại các phần tử của một tập đối tượng nào đó theo một thứ tự ấn định . VD :Thứ tự tăng dần hay giảm dần của một dãy số./ Yêu cầu về sắp xếp thường xuyên xuất hiện trong các ứng dụng tin học với những mục đích khác nhau. Bây giờ chúng ta xét tới một phương pháp có vai trò khá đặc biệt là do ở chỗ nó dựa trên một phép xử lý đơn giản hơn sắp xếp để thực hiện sắp xếp đó là : SẮP XẾP HÒA NHẬP II Phép hòa nhập 2 đường . 1. Khái niệm . Hòa nhập 2 đường là phép hợp nhất các bản ghi của 2 bảng đã được sắp xếp ghép thành 1 bảng có kích thước lớn hơn cũng được sắp xếp. 2> Tư tưởng : Trước tiên ta so sánh 2 khóa nhỏ nhất (hoặc lớn nhất ) của 2 bảng chọn sau đó chọn khóa nhỏ hơn (hoặc lớn | Giới thiệu các thành viên trong Nhóm 4 Nhóm 4 gồm 3 thành viên : Nguyễn văn Tuyến Lê thị Xim Vũ thị Băng Thuyết trình : Vũ Thị Băng Tạo lập siled : Nguyễn Văn Tuyến Biên soạn nội dung : Lê Thị Xim Biên soạn đề cương : các thành viên trong nhóm. ®Æt vÊn ®Ò a> Khái niệm sắp xếp : Sắp xếp là một quá trình bố trí lại các phần tử của một tập đối tượng nào đó theo một thứ tự ấn định . VD :Thứ tự tăng dần hay giảm dần của một dãy số./ Yêu cầu về sắp xếp thường xuyên xuất hiện trong các ứng dụng tin học với những mục đích khác nhau. Bây giờ chúng ta xét tới một phương pháp có vai trò khá đặc biệt là do ở chỗ nó dựa trên một phép xử lý đơn giản hơn sắp xếp để thực hiện sắp xếp đó là : SẮP XẾP HÒA NHẬP II Phép hòa nhập 2 đường . 1. Khái niệm . Hòa nhập 2 đường là phép hợp nhất các bản ghi của 2 bảng đã được sắp xếp ghép thành 1 bảng có kích thước lớn hơn cũng được sắp xếp. 2> Tư tưởng : Trước tiên ta so sánh 2 khóa nhỏ nhất (hoặc lớn nhất ) của 2 bảng chọn sau đó chọn khóa nhỏ hơn (hoặc lớn hơn ) để đưa ra miền sắp xếp ( 1 miền nhớ phụ có kích thước bằng tổng kích thước hai bảng con ) và đặt nó vào vị trí thích hợp tiếp đó khóa được chọn từ đấy bị loại ra khỏi bảng chứa nó . quá trình như vậy cứ tiếp tục cho tới khi 1 trong 2 bảng đã cạn . cuối cùng ta chỉ cần chuyển toàn bộ pần đuôi của bảng còn lại ra miền sắp xếp là xong . 3> Giải thuật : prucedure merge(x,b,m,n,z) var i,j,k :interger 1: i:=k :=b ; j :=m+1; while i =m then (zk,.zn):=(xi, ,xn) Else (zk ,zn):= (xi ,xm) 4 : return 4> Độ phức tạp của thuật toán Trong câu lệnh while ứng với 1 phép so sánh thì có 1 phép chuyển chỗ , nhưng nếu một mạch nào đó kết thúc sớm thì cả phần đuôi của mạch còn lại được chuyển sang miền sắp xếp mà không tương ứng với một phép so sánh nào vì vậy đối với phép sắp xếp này ta lại chọn phép tích cực là phép chuyển chỗ để làm căn cứ đánh giá thời gian thực hiện giải thuật