c에서 mergesort에서 최악의 경우를 만드는 방법은 무엇입니까?

-2

DataCount는 숫자를 정렬하는 횟수입니다.c에서 mergesort에서 최악의 경우를 만드는 방법은 무엇입니까?

int* MakeMWData(int DataCount) 
    {

//하게 배열

int* Data = (int*)malloc(DataCount*sizeof(int)); 

int number = 2; 
int count = 0; 
Data[0] = 1;

// 입력 데이터

int i,j; 
for(i = DataCount;; i/=2) 
{ 
    count++; 
    for(j = 1; j<DataCount;j++) 
    {

정렬 최악의

내가이 정확하지 않은 생각 병합합니다.

 if(j%i == 0 && j %(i * 2) != 0) 
     { 
      Data[j] = number; 
      number++; 
     } 
    } 
    if(i==1) 
     break; 
} 
for(i = 0; i<DataCount ; i++) 
{ 
    if(Data[i] ==0) 
     Data[i] = number; 
    number++; 
} 
return Data; 
    }

주 기능의 데이터가 최악입니다.

int* MergeData = MakeMWData(DataCount[i]);

출처

2014-04-13 user3450300

최악의 경우는 없습니다. "표준"병합 정렬은 항상 동일한 수의 작업을 수행합니다. –

이 답변보기 http://stackoverflow.com/questions/24594112/worst-input-data-on-mergesort/24594419#24594419 – Jerky

머지 소트 재귀 개의 어레이 (logn 회)에 배열 분할되어 작동하는 방식, 전까지 소자 쌍을 비교할 수있는. 그런 다음 재귀 적으로 만들어진 배열을 병합하여 동시에 정렬합니다.

일부 정렬 알고리즘 (예 : quicksort)의 경우 요소의 초기 순서가 수행 할 작업 수에 영향을 줄 수 있습니다. 그러나 어쨌든 정확히 동일한 수의 연산을 수행해야하므로 mergesort에 대해 변경하지 않습니다. 작은 배열로 재귀 적으로 나누어 다시 합쳐야합니다 (Θ(nlogn) 시간).

출처

2014-04-13 12:02:08 chrk

그래서 병합 정렬에는 최악의 경우가 있습니까? – user3450300

@ user3450300 바로. – chrk

@ user3450300이 링크 참조 http://stackoverflow.com/questions/24594112/worst-input-data-on-mergesort/24594419#24594419 – Jerky

c에서 mergesort에서 최악의 경우를 만드는 방법은 무엇입니까?

답변

관련 문제