O (1) 보조 공간을 사용하여 배열을 지정된 순서로 바꾸는 방법은 무엇입니까?

Question

다음과 같은 OrderElements 기능을 어떻게 구현합니까?

char chars[] = {'a', 'b', 'c', 'd', 'e'}; 
int want_order[] = {2, 4, 3, 0, 1}; 
int length = 5; 
OrderElements(chars, want_order, length); 

// chars now contains: c, e, d, a, b 

그것은 당신이 선형 여분의 공간을 사용할 수있을 때 쉽지만, 그것은 즉, 직접의-장소 chars 요소를 정렬 만 일정 여분의 공간으로 할 수 있는가?

피. 에스. : 이것은 시험 문제는 아니었다. 사실이 기능이 필요합니다.

정리 : 원하는 최종 요소 순서에 대한 오해가있는 것 같습니다. 예에서 얻어진 배열은 원래 chars 배열을 참조하여, 다음의 요소를 가져야한다 :

{chars[2], chars[4], chars[3], chars[0], chars[1]} 

엄밀히 말하면

{'c', 'e', 'd', 'a', 'b'}. 

Answer 1

하지만 O(lg length) 메모리 목록 인덱스를 나타 내기 위해 필요하다; 그러나이 토론에서는 이것을 무시할 것입니다. 왜냐하면 64 비트 i을 사용하면 실제로 순서를 재조정 할 수있을만큼 충분히 클 것이기 때문입니다.

for (int i = 0; i < length; i++) { 
    int t = want_order[i]; 
    while (t < i) { 
    // t has been moved already; we need to find out where the value that started there 
    // went. Since we must've put it at want_order[t] before, resume looking there 
    t = want_order[t]; 
    // once t >= i, we know we've not touched that slot more than once, and so our 
    // value is there 
    } 
    swap(chars[i], chars[t]); 
} 

직관적 인 설명 : 배열의 각 항목에 대해, 우리는 우리의 목표 값을 포함 슬롯에 우리의 이전 값을 저장, 그것의 목표 값을 넣습니다. 우리는 목표 가치가 실추 된 경우에 대처해야합니다. 이는 주어진 슬롯이 최대 두 번 스왑된다는 점을 지적함으로써 처리됩니다. 한 번은 다른 값으로 도난 당했을 때 (이 반복이 그렇게하기 때문에 일어날 수 없었던) 또는 값이 최종 값을 삽입하기 위해 이동 된 경우 (이는 인덱스를 낮추는 경우에만 발생합니다).

이 샘플 데이터를 보는 방법의 그림 :

이

i | want_order | chars  | t 
0 | 2 4 3 0 1 | a b c d e | 2 (swap) 
1 | 2 4 3 0 1 | c b a d e | 4 (swap) 
2 | 2 4 3 0 1 | c e d a b | 3 (swap) 
3 | 2 4 3 0 1 | c e d a b | 0 (follow) 
3 | 2 4 3 0 1 | c e d a b | 3 (swap - no-op) 
4 | 2 4 3 0 1 | c e d a b | 1 (follow) 
4 | 2 4 3 0 1 | c e d a b | 4 (swap - no-op) 

이 알고리즘은 (인덱스 용) 만 O(lg n) 메모리를 사용은하지만 완전히 그것의 실행 시간을 분석하는 시도하지 않았습니다. 분명히 그것은 최악의 경우입니다 O(n^2), 그러나 나는 그것이 실제보다 나은 것 같아요. 그러나 체인의 길이에 대한 실제 경계가 없기 때문에 원칙적으로 최악의 경우 입력으로 시간이 O(n^2)이 될 수 있습니다.

Answer 2

불가능합니다.

정렬 된 요소의 색인을 알기 위해서는 적어도 O (log (목록 크기))가 필요합니다. 메모리 O (1)와

Answer 3

정렬 작업은 거품 정렬이지만, O(n²)에서 일을 할 것 성능 O (n²)

http://en.wikipedia.org/wiki/Bubble_sort

Answer 4

이 있습니다. 외부 루프의 각 반복에서 현재 원하는 요소가 올바른 위치 (첫 번째 내부 루프)로 스왑 된 다음 나머지 요소의 원하는 순서가 새 상황 (두 번째 내부 루프)을 반영하도록 조정됩니다.

for (int i = 0; i < length; i++) 
{ 
    for (int j = wantedOrder[i]; j > i; j--) 
    { 
     Swap(chars, j, j - 1); 
    } 

    for (int j = i + 1; j < length; j++) 
    { 
     if (wantedOrder[j] < wantedOrder[i]) 
     { 
      wantedOrder[j]++; 
     } 
    } 
} 

물론 원하는 순서 배열을 파괴해야합니다. 이것이 허용되지 않는다면, 나는 그 문제를 (적어도 현재는) 해결하는 방법을 모른다.

Answer 5

want_order 배열을 변경할 수 있으면 가능합니다. 이 알고리즘은 순열이 사이클로 분해 될 수 있기 때문에 다소 간단합니다. 한 사이클을 반복 할 때 각각의 방문을 표시하십시오. 시간 복잡도는 O (N)입니다. 의사 코드 :

이 게시물은 위의 오류가

char chars[]  = {'a', 'b', 'c', 'd', 'e'}; 
int want_order[] = {2, 4, 3, 0, 1}; 
int length  = 5; 

OrderElements(chars, want_order, length) { 
    int i, j, k; 

    for(i = 0; i < length; ++i) { 
    if (want_order[i] == -1) continue; 

    j = startPos = want_order[i]; 
    c = chars[i]; 
    do { 
     swap(c, chars[j]); 
     k = want_order[j]; 
     want_order[j] = -1; 
     j = k 
    } while(j != startPos); 
    } 
} 

Answer 6

(가 우발적으로 인덱스를 덮어 씁니다). 다음은 수정 된 버전입니다.

char chars[]  = {'a', 'b', 'c', 'd', 'e'}; 
int want_order[] = {2, 4, 3, 0, 1}; 
int length  = 5; 

OrderElements(chars, want_order, length) { 
    int i, j, k; 

    for(i = 0; i < length; ++i) { 
    if (want_order[i] == -1) continue; 

    j = startPos = want_order[i]; 
    c = chars[i]; 
    do { 
     swap(c, chars[j]); 
     k = want_order[j]; 
     want_order[j] = -1; 
     j = k 
    } while(j != startPos); 
    } 
}