+ Trả lời chủ đề
Hiện kết quả từ 1 tới 1 của 1

Chủ đề: Thuật toán Merge Sort

  1. #1
    Status : ngovanhieu_Alpha đang ẩn
    Tham gia ngày : Aug 2011
    Bài gửi : 200

    Thuật toán Merge Sort

    Thuật toán Merge Sort

    Mô tả bài toán: cho 2 danh sách A và B lần lượt có m và n phần tử đã sắp xếp theo thứ tự. Bài toán đặt ra trộn 2 danh sách A và B với nhau thành danh sách C cũng là một danh sách có thứ tự.
    Thuật toán:
    • Bước 1: khởi tạo ba chỉ số chạy trong vòng lặp i = 0, j = 0, k = 0 tương ứng cho ba mảng A, B và C.
      Bước 2: tại mỗi bước nếu cả hai chỉ số (i<m và j<n) ta chọn min(A[i],B[j]) và lưu nó vào trong C[k]. Chuyển sang Bước 4.
      Bước 3: tăng giá trị k lên 1 và quay về Bước 2.
      Bước 4: sao chép tất cả các giá trị còn lại từ các danh sách mà chỉ số còn vi phạm (tức i<m hoặc j<m) vào trong mảng C.

    Mã:
    #include <iostream.h>
    #include <conio.h>
    #define max 100
    void NhapMang(int A[],int n) {
        for(int i=0; i<n; i++) {
            cout<<"Phan tu "<<i<<" = ";
            cin>>A[i];
        }
    }
    void XuatMang(int A[],int n) {
        cout<<endl;
        for(int i=0; i<n; i++)
            cout<<A[i]<<"\t";
    }
    void MergeSort(int m, int n, int &k, int A[], int B[], int C[]) {
          int i = 0, j = 0;
          k = 0;
          while (i < m && j < n) {
                if (A[i] <= B[j]) {
                      C[k] = A[i];
                      i++;
                } else {
                      C[k] = B[j];
                      j++;
                }
                k++;
          }
          if (i < m) {
                for (int p = i; p < m; p++) {
                      C[k] = A[p];
                      k++;
                }
          } else {
                for (int p = j; p < n; p++) {
                      C[k] = B[p];
                      k++;
                }
          }
    }
    void main() {
        int A[max],B[max],C[max],n,m,k;
        clrscr();
        cout<<"n = ";
        cin>>n;
        cout<<"m = ";
        cin>>m;
        cout<<"Nhap danh sach co thu tu A:\n";
        NhapMang(A,m);
        cout<<"Nhap danh sach co thu tu B:\n";
        NhapMang(B,n);
        cout<<"\nSap xep tron 2 mang A, B\n";
        MergeSort(m,n,k,A,B,C);
        XuatMang(C,k);
        getch();
    }
    Lần sửa cuối bởi ngovanhieu_Alpha; 06-08-2011 lúc 03:06 PM

+ Trả lời chủ đề

Quyền viết bài

  • Bạn không thể gửi chủ đề mới
  • Bạn không thể gửi trả lời
  • Bạn không thể gửi file đính kèm
  • Bạn không thể sửa bài viết của mình
Trang Chủ Việc Làm Gia Sư Gia sư