2 개의 정렬 된 하위 배열이있는 배열을 내부 정렬

Question

[이것은 인터뷰 질문입니다. 중복을 찾을 수 없습니다.]

배열에는 두 개의 하위 정렬 된 배열이 있습니다. 2 개의 하위 배열을 정렬하는 inplace 알고리즘을 제공하십시오. 전 용

: I가/P : 1 4 5 7 8 9 1 2 3 6 10 11 O/P : I가있는 장소의 관점에서 생각 1 2 3 4 5 6 7 8 9 10 11

병합 정렬, 삽입 정렬 (하위 배열은 이미 정렬되어 있기 때문에) 및 빠른 정렬이라는 측면에서 볼 때 표준 정렬 방법을 사용할 때보 다 더 복잡 해지는 솔루션을 생각할 수 없습니다.

정렬 된 하위 배열 속성을 활용하고 입력시 Quicksort를 실행하는 것보다 시간이 더 복잡 해지는 알고리즘을 찾으십시오.

이

이 예제를 사용하여, 내가 생각 병합 정렬 시뮬레이션 :

1) For position 0, Comparing 1 & 2, 1 is smaller let it stay at it's original place 
    2) For position 1, Comparing 2 & 4, 2 is smaller so swap 2 and 4 
    3) For position 2, Comparison now is between 4 and 3 (5 > 4 anyways) swap 3 and 5 
    4) For position 3, Comparison between 4 & 5, swap 4 and 7 
    5) For position 4, Comparison between 7 & 5, swap 8 and 5 
    6) For position 5, Comparison between 7 & 8 (OUCH!!) it should have been between 7 & 6 

이 문제가 자리에서 병합가 너무 복잡 매트릭스의 정렬 된 행을 정렬과 비슷한 것 같다.

Answer 1

이 정확한 문제를 해결하기위한 선형 시간 알고리즘과 그 해결 방법을 생각해 내는데 얼마나 많은 노력이 있었는지 표시하려면 http://comjnl.oxfordjournals.org/content/38/8/681.full.pdf+html을 참조하십시오.

내 생각에 인터뷰어는 그들이 일했다고 생각한 귀여운 대답을했습니다. 실제로는 그렇지 않습니다. 두 번째로 가장 좋은 추측은 이유 때문에 복잡성을 지정하지 않았다는 것입니다.

인터뷰에서 저는 실제로이 질문에 대한 연구가 있다고 확신하지만 "효율적으로 처리하는 방법을 모르지만 비효율적 인 대답입니다." 그러면 분명히 효과가있는 것을 할 것입니다.

Answer 2

O (n log n) 최악의 경우 동작을 수행하는 적절한 위치 정렬이 있지만 종이에 "상수 요인이 있기 때문에이 알고리즘은 주로 이론적 인 흥미가 있습니다." https://stackoverflow.com/a/2571104/56778

정렬 된 하위 배열 중 하나만큼 큰 임시 버퍼를 할당 할 수없는 경우에는 위치에서 병합하는 것이 매우 어렵습니다.

Answer 3

인터뷰 질문의 경우 알고리즘에서 한 번 바꾸면 결과 배열이 더 이상 별도로 정렬되지 않습니다. 더 큰 스왑 된 요소가 올바른 위치에 도달 할 때까지 '버블 링'해야합니다.

간단하게 2 개의 배열을 취하여 topA와 topB를 현재 위치로 사용합니다 (처음에는 둘 다 0 임). 필요한 결과 배열을 A [1..m] ... B [1..n]이라고합시다. 다음은 의사 코드입니다.

if (A[topA] < B[topB]) { 
    swap (A[topA], B[topB]) 
    index = topB; 
    while (B[index] < B[index + 1]) { 
     swap(B[index], B[index + 1]) 
    } 
    topB++ 
} else { 
    topA++; 
} 

위의 각 실행이 끝날 때 결과 배열은 정렬되고 작아집니다. 배열 중 하나가 다 떨어질 때까지이 작업을 계속할 수 있습니다. 그러나 버블 링 단계로 인해 복잡성은 O (m + n)보다 커집니다.

Answer 4

// since both are sorted use array b as min heap 
    // if a[i] > b[0] (top of min-heap), exch it and heapify b 
    // order : O(nlog(n)) 
    void inplaceMerge(vector<int>& a, vector<int>& b) 
    { 
    for (int i=0; i < a.size(); i++) { 
     if (a[i] > b[0]) { 
       swap(a[i], b[0]); 
       sink(b, 0, b.size()-1); // bubbleDown() operation in heap() 
     } 
     } 
     sort(b.begin(), b.end()); 
    } 

    void sink(vector<int>& b, int i, int n) 
    { 
      int j = 2*i + 1; 
      while (j <= n) { 
       if (j+1 < n && b[j+1] < b[j]) j++; 
       if (b[j] < b[i]) swap(b[i], b[j]); 
       else break; 
       i = j; 
       j = 2*i + 1; 
      } 
    }