Gia sư Cần Thơ, Dạy Kèm Cần Thơ

VỮNG TIN - TIẾP BƯỚC - THÀNH CÔNG


Thuật toán Merge Sort

Share
avatar
admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 37
Đến từ : Cần Thơ

Thuật toán Merge Sort

Bài gửi  admin on Sat Apr 17, 2010 9:04 am

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ố (iBướ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

    Code:
    #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();
    }

nvlong
Nhập môn
Nhập môn

Tổng số bài gửi : 2
Points : 2
Join date : 07/10/2010

Re: Thuật toán Merge Sort

Bài gửi  nvlong on Thu Oct 07, 2010 8:57 pm

Nếu khi trộn 2 mảng này với nhau ta được mảng thứ 3 và em muốn mảng thứ 3 này random thì phải làm sao vậy thầy ?
avatar
admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 37
Đến từ : Cần Thơ

Re: Thuật toán Merge Sort

Bài gửi  admin on Sun Oct 10, 2010 9:02 pm

nvlong đã viết:Nếu khi trộn 2 mảng này với nhau ta được mảng thứ 3 và em muốn mảng thứ 3 này random thì phải làm sao vậy thầy ?

Bạn có thể nói rõ hơn ý của mình không?

nvlong
Nhập môn
Nhập môn

Tổng số bài gửi : 2
Points : 2
Join date : 07/10/2010

Re: Thuật toán Merge Sort

Bài gửi  nvlong on Thu Oct 14, 2010 10:06 pm

Sorry , E không đọc kỹ đề



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ự.

Và e không hiểu cho lắm về thuật toán này .



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
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

Thầy có thể chạy tay từng bước được không ạ . E thực sự không hiểu lắm .

Thank 4 share .
avatar
admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 37
Đến từ : Cần Thơ

Re: Thuật toán Merge Sort

Bài gửi  admin on Fri Oct 15, 2010 7:20 am

Em phai tu debug thi moi hieu duoc!

Sponsored content

Re: Thuật toán Merge Sort

Bài gửi  Sponsored content


    Hôm nay: Wed Nov 21, 2018 10:38 am