정렬 정수 비교 기반

Question

가지고 선형 시간 정렬 어레이 A = [A1은 A2, ...,]는 어레이의 각 요소 중 0, 1 또는

정렬 할 필요가 2이고 이 배열은 구체적으로 비교 기반 알고리즘을 사용한다고 명시되어 있습니다. 선형 시간 알고리즘을 사용하는 것이 가능하다는 것을 알고 있지만 계산 정렬 또는 다른 배열을 사용할 수는 없습니다.

누구부터 시작할 수 있는지 알려주세요. 저는 1이 중간 값이라는 것을 알고 있다고 가정하고 있지만, 이것을 정립하기 위해 어떤 기법을 사용해야합니까?

Answer 1

요소를 비교하는 것만으로 3 개의 값으로 배열을 정렬 할 수 있습니다 (요소의 유형이나 비교 함수가 주어질 때 세 개의 값을 모르는 경우에도). 이렇게 :

첫 번째 두 요소를 비교하십시오. 하나가 다른 것보다 크다면, 더 작은 것은 0 또는 1이고, 큰 것은 1 또는 2입니다. 앞에 작은 것을 넣고 큰 것을 가장 마지막 요소와 바꾸십시오. 그런 다음 두 번째 (교체 된) 요소와 세 번째 요소를 비교하고 두 번째 요소를 두 번째 요소에 넣고 두 번째 요소를 마지막 요소 요소와 바꾸는 등의 작업을 수행합니다. 두 요소가 같으면 차이를 찾을 때까지 세 번째 요소와 요소를 비교하고, 필요하면 여러 요소를 끝까지 이동합니다.

이 결과는 첫 번째 영역이 모두 0 또는 1이고 두 번째 영역이 모두 1 또는 2 인 배열입니다. 그런 다음 각 영역을 비슷한 방식으로 정렬하여 완전히 정렬 된 배열을 얻을 수 있습니다 배열을 두 번 반복 한 후

예 : 소자 홀수가 있기 때문에 그들이 않으면 (이전 요소에 비교하여 중간 요소는, 상기 제 1 형태 또는 제 2 영역에 속하는지 여부를 확인할 수 있고

state: 2,1,2,1,0 
compare:^^ 
swap: 1,2,2,1,0 
move: ^ ^ 
state: 1,0,2,1,2 
compare: ^^ 
swap: 1,0,2,1,2 
move:  ^^ 
state: 1,0,1,2,2 

다음 요소와 동일). 이 예제에서 중간 요소는 1이므로 실제로는 차이가 없습니다. 이들 각각은 다음 별도로 정렬 할 수 있습니다

zone1: 1,0 
zone2: 1,2,2 

:

이제 우리는 두 개의 영역이이 단계에서

state: 1,0 
compare:^^ 
swap: 0,1 

state: 1,2,2 
compare:^^ 
swap: 1,2,2 
move: ^^ 
state: 1,2,2 

을, 우리는 홀수에 중간 요소를 확인할 필요가 없습니다 - 길이 영역.

Answer 2

피벗 요소로 1을 사용합니다. 모든 요소와 비교하십시오. 값이 0 인 경우 1으로 이동하고 2 인 경우 1 뒤에 이동하십시오.

#include <iostream> 
#include <vector> 
#include <iterator> 
using namespace std; 

void Sort(vector<int>& A) { 
    int n = A.size(), i = 0, j = 0, k = n - 1; 
    while (j < k) { 
     if (A[j] == 0) swap(A[i++], A[j++]); 
     else if (A[j] == 2) swap(A[k--], A[j]); 
     else ++j; 
    } 
} 

int main() { 
    vector<int> A {2, 1, 2, 1, 0}; 
    Sort(A); 
    copy(A.begin(), A.end(), ostream_iterator<int>(cout, " ")); 
    return 0; 
} 

Answer 3

다음은 자바 스크립트 솔루션입니다. 알고리즘은 파티션을 기준으로 pivot = 1 및 pivot = 0으로 두 번 실행됩니다. 알고리즘은 0, 1 또는 2를 알기보다는 비교를 수행함을 알 수 있습니다.

var array = [1,0,2,0,0,1,2,0,2,1,1,1,2,2,0,0,0,1]; 
console.log("Original Array " + array); 
var size = array.length; 

function partition(array, s, e, pivot) { 

    var i = s - 1; 
    var j = s; 
    while (j < e) { 
     if (array[j] <= pivot) { 
      var swap = array[i + 1]; 
      array[i + 1] = array[j]; 
      array[j] = swap; 
      i++; 
     } 
     j++; 
    } 
    return i; 
} 

var parti = partition(array, 0, size, 1) 
console.log("After one pass " + array); 
console.log("Partition " + parti); 
partition(array, 0, parti + 1, 0); 
console.log("Final Array " + array);