효율적으로 정수의 배열을 정렬

Question

한다고 가정 우리가라는 정수의 배열 data 또한

3 
2 
4 
5 
2 

우리가라는 같은 크기의 다음과 같은 배열 info

1 
4 
0 
2 
3 

각 값 info은 첫 번째 배열의 인덱스를 나타냅니다. 예를 들어 첫 번째 값은 1입니다. 즉, 0 위치에 최종 정렬 된 배열의 값은 data[info[0]]입니다. 크기 NN의 여분의 메모리를 사용하지 않고

data[info[0]] => 2 
data[info[1]] => 2 
data[info[2]] => 3 
data[info[3]] => 4 
data[info[4]] => 5 

내가 자리에 data 배열의 정렬을 을하고 싶습니다,이 논리를 최종 정렬 된 배열에 따라

은 다음이 될 것이다 data 배열의 크기입니다. 또한 총 작업량을 가능한 한 적게하고 싶습니다.

나는 내 문제에 대한 해결책을 생각하려고 노력했지만 추가 메모리를 사용하지 않을 것이라고는 생각할 수 없었다. 이것들은 내가 구현하고있는 시스템에 대한 내 자신의 제한 사항이라는 것을 명심하십시오. 이러한 제한 사항을 지키지 못하면 다른 것을 생각해야 할 것입니다.

어떤 아이디어

주시면 감사하겠습니다.

는 info 배열이 그대로 유지 할 필요가있는 경우

Answer 1

, 당신은 사용할 수 있습니다 미리 감사 등의 추가 저장 그와 종류 O(n)의 :

for(int i = 0; i < n; ++i) { 
    int where = info[i]; 
    if (where == i) continue; 
    info[i] = data[i]; 
    data[i] = i < where ? data[where] : info[where]; 
} 

data의 요소가 올바른 이미있는 경우 장소, 우리는 그 색인을 건너 뜁니다. 그렇지 않으면 info 배열의 요소를 기억하고 큰 요소 인 경우 data에 올바른 요소를 쓴 후 data을 가져오고 작은 인덱스 인 경우 info에서 가져옵니다.

물론 간단한 방법은 info과 data 배열의 유형이 동일해야하며 일반적으로 3*n 사본을 필요로합니다. data 요소가 info 배열에 저장할 수없는

경우에, 우리는 info의주기를 따를 수 :

F가 이미 있었다 요소의 수는 data 요소의 n - F + C 사본을 수행

for(int i = 0; i < n; ++i) { 
    // Check if this is already in the right place, if so mark as done 
    if (info[i] == i) info[i] = -1; 

    // Nothing to do if we already treated this index 
    if (info[i] < 0) continue; 

    // New cycle we haven't treated yet 
    Stuff temp = data[i]; // remember value 
    int j = info[i], k = i; 
    while(j != i) { 
     // copy the right value into data[k] 
     data[k] = data[j]; 
     // mark index k as done 
     info[k] = -1; 
     // get next indices 
     k = j; 
     j = info[j]; 
    } 
    // Now close the cycle 
    data[k] = temp; 
    info[k] = -1; 
} 

올바른 위치 (정렬 순열의 고정 점) 및 C은 정렬 순열에서 길이가 > 1 인주기 수입니다. 즉, 복사 매수는 많아야 3*n/2입니다.단순히

for i in 0..n-1 : 
    info[i] := data[info[i]] 

및 info 이제 정렬 된 배열을 유지하는 이유

Answer 2

. 이 data에 있어야하는 경우, 바로 옆에, 다시 복사 :

for i in 0..n-1 : 
    data[i] := info[i] 

2*n 사본을, 전체.