Thắc mắc về chương trình trộn mảng một chiều trong C

Xin chào, mình có một bài tập như thế này
Hãy viết một hàm gọi là merge_arrays() nhận vào hai mảng một chiều đã được sắp xếp và trộn chúng thành một mảng cũng được sắp xếp. Khi thực hiện, không được chuyển hai mảng vào một mảng rồi sắp xếp lại. Hàm có tiêu đề như sau: void merge_arrays(double a[],double b[],double c[], int n, int m) ở đây, a và b là hai mảng đã sắp xếp và c là mảng chứa kết quả trộn.
và đây là code mà mình kiếm được trên google
Mình có một thắc mắc là không biết hàm index nó hoạt động như thế nào ạ ? mình có thử debug để xem nhưng vẫn không hiểu lắm, không biết đây có phải là một trong các thuật toán sắp xếp không ạ. Mình vẫn chưa học cấu trúc dữ liệu và giải thuật nên về mấy phần thuật toán này mình hơi tệ, Mong được mọi người giúp đỡ và giải đáp , xin cảm ơn :smile:

void arrays(long a[],long b[],long c[],int n,int m);
void encoder(long a[],int n);
void index(long a[],int n);
void display(long a[],int n);

int main()
{
    long a[100],b[100],c[200];
    int n,m;
    do
    {
        printf("Nhap vao kich thuoc mang A = ");
        scanf("%d",&n);
        if(n>100||n<0)
            printf("Error\n");
    }while(n>=100&&n<=0);
    encoder(a,n);
    do
    {
        printf("Nhap vao kich thuoc mang B = ");
        scanf("%d",&m);
        if(m>100||m<0)
            printf("Error\n");
    }while(m>=100||m<=0);
    encoder(b,m);
    index(a,n);
    index(b,m);
    printf("\n");
    printf("Mang a sau khi sap xep tang\n");
    printf("\n");
    display(a,n);
    printf("\n");
    printf("\nMang b sau khi sap xep tang\n");
    printf("\n");
    display(b,m);
    arrays(a,b,c,m,n);
    printf("\n");
    printf("\nMang sau khi sap xep tron\n");
    printf("\n");
    display(c,n+m);
    return 0;
}
void arrays(long a[],long b[],long c[],int n,int m)
{
    int i=0,j=0,k=0;
    while((i<n)&&(j<m))
    {
        if(a[i]<=b[j])
        {
            c[k]=a[i];
            i+=1;
        }
        else
        {
            c[k]=b[j];
            j+=1;
        }
        k+=1;
    }
    while(i<n)
    {
        c[k]=a[i];
        i+=1;
        k+=1;
    }
    while(j<m)
    {
        c[k]=b[j];
        j+=1;
        k+=1;
    }
}
void encoder(long a[],int n)
{
    int i;
    for(i=0;i<n;i++)
        a[i]=rand();
}
void index(long a[],int n)
{
    int i,j;
    long x;
    for(i=0;i<n-1;i++)
     for(j=i+1;j<n;j++)
     if(a[i]>a[j])
    {
       x=a[i];
       a[i]=a[j];
       a[j]=x;
    }
}
void display(long a[],int n)
{
    int i;
    for(i=0;i<n;i++)
    {
        printf("%6.1d\t",a[i]);

    }
}

Mình lười nên mình không đọc code của bạn. Nhưng mình gợi ý cho bạn, trộn 2 mảng đã sắp xếp thành 1 mảng đã sắp xếp, đó là cơ sở của Merge Sort

Hàm đó là Selection Sort đấy :slight_smile: có điều viết không tốt nên khó hiểu. Với lại đặt tên hàm linh tinh :smiley:

1 Like

Bạn này hay thật :v title là merge array nhưng nội dung thì hỏi selection sort :v Google wiki nhé :1234:

nếu hỏi hàm `arrays`

Chắc là thớt định hỏi hàm arrays.
Code này ngày xưa mình từng nghĩ ra + code :v sao trùng ý tưởng được nhỉ @@
Ngày xưa lúc mình chạy thì code này có lúc nhanh hơn QuickSort, có lúc như con rùa @@ Khuyên thật lòng là không nên code sort kiểu này, tốn time mà khó nhớ kinh khủng :v Mình code đúng 1 lần xong bỏ đấy :v

  • Tóm lại là hàm arrays chỉ là gán thông qua chỉ số thôi. Giải thích rõ luôn VD nhé: (mã giả thôi, mn đừng ném đá)
Có:
a[] = 3 1 9 2 4 7 5 8 6
b[] = 8 4 2 1 9 7 3 6 5

Vào hàm:
- Khởi gán i=0, j=0, k=0 (3 chỉ số tương ứng của 3 mảng a, b, c)
- while(i<n && j<m):
    + i=0, j=0, k=0: a[i] < b[j] (3 < 8) -> c[k]=a[i]:
    -> a[] = 3 1 9 2 4 7 5 8 6
        b[] = 8 4 2 1 9 7 3 6 5
        c[] = 3 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
        (c có m + n phần tử, mới có phần tử đầu tiên được gán, còn lại là rác)
    -> phải tăng i, k vì a[i] đã được đưa vào mảng c
       và phần tử đầu tiên của c đã được gán
    (trong code ghép 2 mảng thành 1 này, chỉ số của c phải luôn tăng)).

    + i=1, j=0, k=1: a[i] < b[j] -> c[k]=a[i]:
    -> a[] = 3 1 9 2 4 7 5 8 6
       b[] = 8 4 2 1 9 7 3 6 5
       c[] = 3 1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
    -> phải tăng i, k vì a[i] đã được đưa vào mảng c
       và phần tử thứ 2 của c đã được gán.

    + i=2, j=0, k=1: a[i] > b[j] -> c[k]=b[j]:
    -> a[] = 3 1 9 2 4 7 5 8 6
       b[] = 8 4 2 1 9 7 3 6 5
       c[] = 3 1 8 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
    -> phải tăng j, k vì b[j] đã được đưa vào mảng c
       và phần tử thứ 3 của c đã được gán.

    ...

- 2 vòng while ở cuối:
Khi 1 trong 2 mảng hết phần tử, mảng còn lại có thể sẽ thừa ra một số phần tử,
việc còn lại của ta chỉ là nhét hết đống phần tử thừa vào mảng c thôi.
  • Nói chung thuật toán là như thế. Cách hoạt động của hàm đó giống như đan 2 cái lược vào nhau.
  • Tuy nhiên, code này mới merge được 1 lần. Từ ví dụ trên, bạn hoàn toàn có thể tính bằng tay c[] = 3 1 8 4 2 1 9 2 4 7 5 8 6 9 7 3 6 5. Rõ ràng là mảng này chưa xếp tăng dần. Hàm arrays này phải trầy trật thêm 1 công đoạn tách nữa rồi mới lại chạy lại code merge được. Đó là lí do vì sao độ phức tạp của bài này rất to (O((2(n+m))^k) với k tuỳ vào dữ liệu).
  • Nói chung là có code mới thấy thuật toán này vô duyên cực kì.

theo ý kiến cá nhân thì code trên không phải code selection sort chuẩn. nó lai tạp giữa bubble sort và selection sort. thế nên bác đừng bảo đó là selection sort nhé.

Đúng vậy, nếu thay tìm min bằng tìm max thì sửa nhẹ 3 phát là y chang.

thế nếu thay điều kiện không phải là a[i]>a[j] nữa mà là a[i]>a[i+1] thì thành bubble rồi.(C vẫn cho tràn mảng nên không lo ex)

Nhưng vẫn sinh lỗi như thường :smiley: nó swap thật thì kết quả sai mất rồi.

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?