병합 함수가 정렬되지 않은 배열을 출력하는 이유는 무엇입니까?

Question

두 개의 배열 aa[5] = {5, 4, 9, -1, 3} 및 bb[2] = {16, -11}이 주어진 경우 세 번째 배열 cc[7]에 정렬하는 간단한 함수를 만들었습니다.

#include<stdio.h> 
void merge(int *, int *, int *, int, int); 

int main(){ 
    int aa[5] = {5, 4, 9, -1, 3}; 
    int bb[2] = {16, -11}; 
    int cc[7]; 

    merge(aa, bb, cc, 5, 2); 

    return 0; 
} 

void merge(int *aa, int *bb, int *cc, int m, int n){ 

    int i = 0, j = 0, k = 0; 

    while(i < m && j < n){ 
     if(aa[i] < bb[j]) 
      cc[k++] = aa[i++]; /*Smallest value should be assigned to cc*/ 
     else 
      cc[k++] = bb[j++]; 
    } 

    while(i < m)    /*Transfer the remaining part of longest array*/ 
     cc[k++] = aa[i++]; 


    while(j < n) 
     cc[k++] = bb[j++]; 
}  

cc 배열

올바르게 충전되어 있지만, 값이 정렬되지 않는다. 예상 된 cc = {-11, -1, 3, 4, 5, 9, 16} 대신 cc = {5, 4, 9, -1, 3, 16, 11}을 반환합니다. cc[k++] = aa[i++] 및 cc[k++] = bb[j++]과 같은 할당은 작동하지 않습니다. 어쨌든 논리적 테스트 if aa[i] < bb[j]은 무시됩니다.

나는 그래서 내가 더 차이, 두 개의 서로 다른 표준 테스트, 연산자 우선 순위 문제를 가정 :

gcc main.c -o main.x -Wall 
gcc main.c -o main.x -Wall -std=c89 

나는 모든 관련 오류를 찾을 수없는 코드를 여러 번 체크. 이 시점에서 어떤 제안을 주시면 감사하겠습니다.

Answer 1

당신은 제대로을 통해 알고리즘을 생각해야합니다. 거기에 명백한 버그가 없습니다. 문제는 당신의 기대입니다. 이를 명확하게하는 한 가지 방법은 하나의 배열이 비어 있다면 어떻게 될지 생각하는 것입니다. 기능을 merge 다른 것으로 바꾸면 되겠습니까? 그건 그렇지 않을거야. 사실, 두 가지 요소 a 및 b이 에서 경우 같은 배열는 - 그리고 a 오는 배열 b하기 전에, 다음 a도 cc에 b 전에 올 것이다 - 그것은 aa 또는 bb가합니다.

이 함수는 에서 예상 한대로 배열을 정렬하므로 배열을 정렬하기 전에 정렬해야합니다. 이 경우 qsort을 사용할 수 있습니다.

그 외의 경우, 변경하지 않으려는 배열에 대한 포인터를 사용하는 경우 const 한정자를 사용하십시오. 이 보블 종류의의 원인 ...

void merge(const int *aa, const int *bb, int *cc, int m, int n) 

Answer 2

프로그램이 정상적으로 작동하면 비교를 통해 O(N)을 정렬 할 수 있습니다. @Karzes의 주석에서 언급 할 수 없으므로 프로그램은 정렬 된 하위 배열에 대해서만 올바르게 작동합니다. 당신이 병합 정렬에 대한 병합 기능을 구현하려는 경우 따라서, 당신은이 두 개의 입력을위한 프로그램을 시도해야합니다 :

int aa[5] = {-1, 3, 4, 5, 9}; 
int bb[2] = {-11, 16}; 

Answer 3

가장 효율적이지 문제는 당신을 병합한다는 것이다 (내가 이럴 어떤 표시되지 않습니다 적어도) 구현에는 버그가 없다

#include<stdio.h> 
    void merge(int *, int *, int *, int, int); 
    void sortarray(int array[], int arraySize) 
    { 
     int c,d,temp; 

     for (c = 0 ; c < arraySize-1; c++) 
     { 
     for (d = 0 ; d < arraySize - c - 1; d++) 
     { 
      if (array[d] > array[d+1]) /* For decreasing order use < */ 
      { 
      temp  = array[d]; 
      array[d] = array[d+1]; 
      array[d+1] = temp; 
      } 
     } 
     } 
    } 
    int main(){ 
     int aa[5] = {5, 4, 9, -1, 3}; 
     int bb[2] = {16, -11}; 
     int cc[7]; 
     int i; 
     sortarray(aa,sizeof(aa)/sizeof(aa[0])); 

     sortarray(bb,sizeof(bb)/sizeof(bb[0])); 

     merge(aa, bb, cc, 5, 2); 

     for(i=0;i<sizeof(cc)/sizeof(cc[0]);i++) 
     { 
      printf("%d,",cc[i]); 
     } 
     return 0; 
    } 

    void merge(int *aa, int *bb, int *cc, int m, int n){ 

     int i = 0, j = 0, k = 0; 

     while(i < m && j < n) 
     { 
      if(aa[i] < bb[j]) 
       cc[k++] = aa[i++]; /*Smallest value should be assigned to cc*/ 
      else 
       cc[k++] = bb[j++]; 
     } 

     while(i < m)    /*Transfer the remaining part of longest array*/ 
      cc[k++] = aa[i++]; 


     while(j < n) 
      cc[k++] = bb[j++]; 
    } 

Answer 4

두 개의 정렬 된 배열 (정렬 된 숫자의 여러 묶음에 대한)이 아닙니다. 두 개의 정렬 된 배열을 피드하는 경우 결과가 올바르게 정렬됩니다.

정렬 알고리즘은 정렬을 정렬 된 두 부분으로 나누는 것으로 시작됩니다. 이것은 요소가 순서대로 정렬되지 않았을 때 배열을 전환하여 수행됩니다 (마지막 번호보다 크지 않습니다). 배열을 채우는 첫 번째 정렬 된 집합을 얻습니다 (첫 번째 배열의 첫 번째 a 요소는 배열 A에 넣고 두 번째 묶음을 배열 B에 넣습니다.이것은 병합 될 수있는 두 개의 배열을 생성합니다 (이미 배열되어 있기 때문에).이 병합은 결과를 더 큰 배열로 만듭니다.이 사실은 알고리즘이 각 패스마다 크고 큰 배열을 만들 것이라는 사실을 보증합니다. . 목록이 정렬 된 요소의 큰 무리 적게 팩이 통과 각에서 같이, 배열에 의해 배열을 조작 할 필요가 없습니다 귀하의 경우 :.

1st pass input (the switching points are where the input 
is not in order, you don't see them, but you switch arrays 
when the next input number is less than the last input one): 
    {5}, {4, 9}, {-1, 3}, {16}, {-11} (See note 2) 
after first split: 
    {5}, {-1, 3}, {-11} 
    {4, 9}, {16} 
after first merge result: 
    {4, 5, 9}, {-1, 3, 16}, {-11} 
after second pass split: 
    {4, 5, 9}, {-11} 
    {-1, 3, 16} 
    result: 
    {-1, 3, 4, 5, 9, 16}, {-11} 
third pass split: 
    {-1, 3, 4, 5, 9, 16} 
    {-11} 
third pass result: 
    {-11, -1, 3, 4, 5, 9, 16} 

알고리즘 마감을 당신이하지 않을 때 정렬 된 스트림 두 개 묶음 (배열을 전환하지 않음)은 더 이상 데이터 스트림을 나눌 수 없습니다.

구현 은 병합 정렬 알고리즘 정렬 된 출력을 얻으려면이를 완벽하게 구현해야합니다. 이 알고리즘은 입력을 배열에 넣는 것이 불가능할 때 여러 패스를 수행 할 수 있도록하기 위해 설계되었습니다 (배열에서 배열을 완전히 설명하지는 않습니다). 파일에서 읽은 경우 아이디어가 더 잘 보입니다.

데이터 사용의 엄청난 양이 quicksort이 첫 에드, 그래서 우리 모두가 함께 배열에 맞지 않는 데이터의 버킷로 시작하는 데이터의 bunchs에 대한 알고리즘을 병합

정렬 프로그램 참고.

주 2

수 3이 {-1, 3, 16}하고, 이전의 무리와 같은 무리 했어야 뒤의 숫자 16,하지만 그들은 처음에 서로 다른 배열의 경우, 내가 넣을 수있는 방법을 발견하지 않았습니다로 이 정렬로 분할 목록에서, 나는 16 < 3처럼 버킷을 강제로 가지고, 인위적으로 입력을 분할에 배열을 전환. 이것은 데이터를 통해 추가 패스를 만드는 최종 결과에 영향을 미칠 수 있지만 정렬 된 숫자 목록 인 최종 결과에는 영향을 미치지 않습니다. 나는 이것을 의도적으로 만들었고, 실수가 아니다. (알고리즘의 작동 원리를 설명하는 것은 아무런 관련이 없다.) 어쨌든 알고리즘은 목록을 전환한다. (이 알고리즘을 설명 할 때 배열을 사용하지 않는다. 배열은 무작위 접근이며 배열은 무작위 접근이기 때문에리스트는 어떤 반복자 수단에 의해 처음부터 끝까지 접근해야한다. 이것은 병합 정렬 알고리즘의 요구 사항이다.) 첫 번째 분할 후에도 {4, 9}, {16}이 발생하고 결과를 상상해 보라. 첫 번째 병합 후에 모든 것이 정확하다는 점에서 비교 결과 중 하나가 표시되었습니다.