Từ 1 tới 3 trên tổng số 3 kết quả

Đề tài: Giải thuật trộn n đường (multiway merging) khi sắp dữ liệu. Giúp mình với??

  1. #1
    No Avatar
    lovedream Khách

    Mặc định Giải thuật trộn n đường (multiway merging) khi sắp dữ liệu. Giúp mình với??

    các bạn thân cộng đồng C oi, giúp mình với.
    mình đang gặp khó khăn khi nghiên cứu giải thuật trộn n đường (multiway -merging) khi sắp dữ liệu . Ai biết hay có Source hãy gởi cho mình đi

  2. #2
    Ngày gia nhập
    08 2006
    Nơi ở
    Hải Phòng
    Bài viết
    218

    Mặc định Sắp xếp kiểu hòa nhập

    Sắp xếp kiểu hòa nhập (Merge Sort): Ý tưởng của nó như sau chia dãy cần sắp xếp thành các dãy con đã được sắp xếp (tăng dần hoặc giảm dần) sau đó sử dụng phép hòa nhập hai đường để giảm bớt số lượng các dãy con cho tới khi chỉ còn 1 dãy thì ta được dãy cần sắp xếp;
    * Phép hòa nhập hai đường: Nguyên tắc hòa nhập dược xây dựng khá đơn giản: Ta đã có hai dãy được sắp xếp, ban đầu ta sẽ so sánh hai phần tử nhỏ nhất (hoặc lơn nhất) của hai dãy con đó, chọn khóa nhỏ hơn (lớn hơn)
    để đưa ra cuối mảng phụ có kích thước bằng tổng kích thước hai dãy. Phần tử được chọn sẽ được loại ra khỏi dãy con và quá trình chọn phần tử lại tiếp tục cho tới khi một trong hai dãy đã hết, khi đó toàn bộ phần tử của dãy còn lại sé được đẩy vào cuối mảng phụ và quá trình hòa nhập kết thúc. Như vậy từ hai dãy đã sắp xếp ban đầu ta có được một dãy đã sắp xếp lớn hơn chứa trong mảng phụ.
    Đây là mô tả của thủ tục hoà nhập hai đường:
    Code:
       Procedure MERGE(X,b,m,n,Z)
    {Thủ tục này thực hiện hòa nhập hai bảng con đã được sắp xếp có tính chất
    như đã nêu thành một bảng mới được sắp xếp}
    1) i:=k:=b;j:=m+1
    2) while i<=m and j<=n do
            if X[i]<=X[j] then begin
                               Z[k]:=X[i]
                                   i :=i+1;
                                    end
                             else begin
                                    Z[k]:=X[j]
                                    j:= j+1
                                   end
                 k:= k+1
    
    3){Một trong hai bảng con đã cạn trước}
    if i>m then (Zk,.....,Zn):= (Xj,....,Xn)
            else  (Zk,.....,Zn):=(Xi,....Xm)
    4)return
    
    Chú thích: (Zk....Zn):= (Xi....Xn) là phép gán qui ước thay cho một dãy các phép gán tương ứng các phần tử thuộc bảng ở vế phải cho các phần tử thuộc bảng ở vế trái.
    Từ thủ tục hòa nhập hai đường như trên người ta triển khai thành một số phương pháp sắp xếp mới:
    + Sắp xếp kiểu hòa nhập hai đường trực tiếp: Mỗi phần tử có thể được coi là một dãy đã sắp xếp với độ dài 1. Nếu hòa nhập hai bảng như vậy ta sẽ được một mạch mới có độ dài 2, lại hòa nhập được độ dài 4... cuối cùng ta đươcj một mạch có độ dài n, tức là bảng đã sắp xếp hoàn toàn. Cách này có nhược điểm là không tận dụng được tính " đã sắp xếp rồi của hai dãy" khi một trong hai dãy đã hết phần tử thì số phần tử của dãy còn lại cũng không đáng kể, ta không được lợi nhiều.
    + Sắp xếp kiểu hòa nhập hai đường tự nhiên : Trong dãy cần sắp xếp đã tồn tại những dãy con tăng (giảm )liên tiếp. Ta sẽ tìm những dãy này và hòa nhập chúng. Cách này trong trường hợp mà dãy ban đầu "dường như đã được sắp xếp" có nghĩa là những dãy con tăng có độ dài lớn thì lợi hơn cách trên
    Nhìn chung phương pháp Merge Sort nhanh không kém Heap Sort hoặc Quick Sort tuy nhiên nó đòi hỏi không gian khá lớn 2n nên nó thích hợp với sắp xếp ngoài hơn. Để bao giờ có thời gian mình sẽ giới thiệu ứng dụng cuả nó trong sắp xép ngoài cho các bạn.
    Còn phần giải thuật mình đã nêu trên kia các bạn thử cài đặt nó xem sao

  3. #3
    Ngày gia nhập
    10 2008
    Bài viết
    1

    Mặc định multiway merge

    hình như cái này gọi là "trộn nhiều đường cân bằng"

Các đề tài tương tự

  1. Giải thuật shaker sort. Giúp mình giải thuật với?
    Gửi bởi nguyenhai trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 6
    Bài viết cuối: 29-01-2015, 10:53 PM
  2. Bài tập C Cần giải giúp 3 câu trong đề thi kĩ thuật lập trình C và Cấu trúc dữ liệu và giải thuật
    Gửi bởi nguyenthi0602 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 24-09-2012, 08:42 PM
  3. lưu đồ giải thuật bài mã đi tuần thuật toán quay lui vét cạn. Giúp mình với?
    Gửi bởi katemat000 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 05-01-2010, 10:53 PM
  4. ai bít về thuật toán multiway va polypharese merge chi em
    Gửi bởi sieutruc trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 18-07-2009, 06:54 PM
  5. Tài liệu về giải thuật mã hóa. Mã hóa file theo giải thuật DES. Ai có giúp mình?
    Gửi bởi daolong83 trong diễn đàn Công cụ, ebooks C#, ASP.NET, và Windows Mobile
    Trả lời: 6
    Bài viết cuối: 17-07-2009, 11:28 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn