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

Chia sẻ: Nguyen Tuyen | Ngày: | Loại File: PPT | Số trang:16

Thêm vào BST

Báo xấu

85
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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ố.../..

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài thuyết trình nhóm 2 đề tài: cấu trúc dữ liệu

Giới thiệu các thành viên trong Gi 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 ®Ò ®Æt 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
II Phép hòa nhập 2 đường . II 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 : 3> prucedure merge(x,b,m,n,z) var i,j,k :interger 1: i:=k :=b ; j :=m+1; 1: while i =< m and j =< n do while if x[i] =< x[i] then begin begin z[k] :=x[i]; z[k] i:=i+1 i:=i+1 end; end; else else begin begin z[k]:=x[i] z[k]:=x[i] j:=j+1 j:=j+1 end. end. K:=k+1 K:=k+1 3: if i>m then (zk,...zn):=(xi,…,xn) 3: Else (zk…,zn):= (xi…,xm) Else 4 : return return
4> Độ phức tạp của thuật toán 4> Trong câu lệnh while ứng với 1 phép so sánh thì có Trong 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 .
5> Áp Dụng 5> Cho 2 bảng đã sắp xếp Bảng 1 : 10 20 25 30 Bảng 2 : 05 40 50 Ta có quá trình hòa nhập sẽ như sau : Lượt 1: 10,20,25,30 05  40,50 05 so sánh 2 khóa nhỏ nhất của 2 bảng con là : 05,10 =>>> chọn 05 đưa ra miền sắp xếp
+ Lượt 2 : 20,25,30 05,10  40,50 so sánh 2 khóa nhỏ nhất tiếp theo của 2 bảng so con là : 10 la 40 con =>> chọn 10 đưa ra miền sắp xếp =>> + Lượt 3 : 25,30 05,10,20  40,50 so sánh 2 khóa nhỏ nhất tiếp của 2 bảng con là: so 20,40 =>> chọn 20 đưa ra miền sắp xếp
+ Lượt 4 : 30 05,10,20,25  40,50 05,10,20,25 So sánh 2 khóa nhỏ nhất tiếp theo của 2 bảng con là : 25 và 40 25 =>> chọn 25 đưa ra màn sắp xếp + Lượt 5 : 05,10,20,25,30  40,50 05,10,20,25,30 So sánh 2 khóa nhỏ nhất tiếp theo của 2 bảng con là : là 30 và 40 30
+ Lượt 6 05,10,20,25,30,40,50 05,10,20,25,30,40,50 vì bảng 1 đã cạn nên ta chuyển toàn bộ phần đuôi của bảng 2 ra miền sắp xếp ; kết thúc quá trình sắp xếp .
III sắp xếp hòa nhập 2 đường trục tiếp III 1> Tư tưởng 1> Mỗi bảng ghi có thể coi la một mạch có độ dài bằng 1 nếu hòa nhập 2 bảng như vậy ta sẽ chọn 1 mạch mới co độ dài 2 . lại hòa nhập 2 mạch có độ dài 2 ta được một mạch có độ dài 4 và cứ như thế cuối cùng ta sẽ được một mạch có độ dài n , tức là bảng đã được sắp xếp hoàn toàn 2> Giải thuật procedure MPASS(x,y,n,e) var i:interger (1) i:=1; (2) while i =< n-2l-1 do begin begin call merge (x,i,i+l-1,i+2l-1,Y); i:= i+2l end. (3) if i+1-1< n then call merge(X,i,j+1-1,n,y) else (Yi,....Yn):= (Xi,...Xn) (4) reture (4)
procedure straight-msort(X,n); procedure var l: integer; var (1)l:=1 (1)l:= (2) while l < n do begin begin call MPASS(X,Y,n,l); call l:=l+1; l:=l+1; call MPASS(Y,X,n,l); call l:=l+1; l:=l+ end. end. (3) reture
Áp dụng Áp • B1 : ban đầu ta coi mỗi bản ghi là một mạch có độ dài 1 [20] [10] [05] [25] [ 30] [50] [40] B2 : hòa nhập 2 bảng như vậy ta có 1 mạch mới có độ dài 2. [10 20] [05 25] [30 50] [40] B3: lại hòa nhập 2 mạch có độ dài 2 ta được mạch có độ dài là 4 . [05 10 20 25] [30 40 50] B4 : hòa nhập 2 bảng có độ dài là 44 được mạch mới [05 10 20 25 30 40 50]
4> Độ phức tạp 4> Ta thấy ở lượt sắp xếp nào thì toàn bộ các khóa (bản ghi )cũng được chuyển sang bảng mới (từ X sang Y hoặc từ Y sang X )như vậy chi phí thời gian cho một lượt có cấp O(n) .lượt gọi MPASS trong giải thuật STRAIGHT_MSORT là [log2n].ở lượt 1 kích thước của bảng con là 1 =2^0 lươt sau sẽ là 2^i -1 mà sau lượt gọi cuối cùng thì bảng con có kích thước bằng n vậy sắp xếp hòa nhập 2 đường trực tiếp có cấp O(nlog2n)
IV Ý nghĩa Vì phương pháp sắp xếp kiểu hòa nhập có Vì nhược điểm là chi phí không gian kích thước quá lớn nó đòi hỏi tới 2n phần tử nhớ gấp đôi so với phương pháp thông thường do vậy người ta thường sử dụng phương pháp này khi sắp xếp ngoài đối với các tệp
Trong quá trình biên soạn chúng tôi đã cố gắng tìm Trong hiểu , chắt lọc các vấn đề có liên quan đến các sắp xếp hòa nhập ngưng có thể vẫn còn nhiều thiếu sót mong thầy cô và các bạn bổ xung và góp ý thêm . Cám ơn thầy cô và các bạn lắng nghe !!!!!!!! Cám