바이너리 선택 정량을위한 정렬 알고리즘

Question

내가 좋아하는 책의 수를 기준으로 주문하고 싶은 도서 목록을 상상해보십시오. 개별 서적을 평가하는 대신 목록에서 2 권 중 1 권을 선택하고 원하는만큼 많은 책을 반복합니다 (모든 조합을 평가하지 않음).

어떻게이 바이너리 선택에 따라 내 도서 목록을 정렬합니까? 이 문제는 공식 이름입니까?

Answer 1

Fisher–Yates shuffle 개의 책을 만든 다음 2 개씩 가져올 수 있습니다. 단지 두 개의 인스턴스를 비교하는 것은 정렬이라고 불리는 스트레치이거나 매우 핵심이라고 할 수 있습니다.

Answer 2

Jonas Elfström으로 지적하면 Fisher-Yates는 세트를 셔플하는 표준 방법이며 모든 항목에 대한 데이터를 가져올 수 있으므로이 설정이 좋은 아이디어 일 수 있습니다. 나는 당신이 아마 하나 이상의 패스를 원한다고 생각한다. 기본적으로 항목 모음을 정렬 할 때 노드가 항목이고 가장자리가 관계 이보다 크거나 같은 방향 그래프를 작성하고 있습니다. 알고리즘 적으로이 관계를 정의 할 수 있으면 단일 패스로 충분할 것이고 잘 정렬 된 세트로 끝날 것입니다.

여기서 복잡한 점은 한 번에 두 권의 책을보고 잘 정의 된 알고리즘없이 사람이 결정하도록 내버려두면 A> B, B> C 및 C > A. 이것은 분명히 잘 정돈 된 세트를 산출하지 못할 것입니다. 더 나쁜 것은, 서로 다른 두 날에, 같은 책 2 권에 대해 서로 다른 대답을 줄 수 있다는 것입니다.

내가 생각할 수있는 가장 좋은 방법은 n x n 행렬을 유지하는 것입니다. 여기서 n은 정렬 할 항목의 양입니다. i, j 항목은 i 항목이 j 항목보다 우수한 것으로 선택된 항목입니다. 여기에서 i은 행을 인덱싱하고 j은 인덱스 열을 나타냅니다.

여기에서 불행히도 특허 번호 인 PageRank이 이상적입니다. 꽤 우아하지는 않지만, 충분히 좋은 점은 aij과 aji의 차이를 합한 다음이를 바탕으로 책을 분류하는 것입니다. 그래서 예를 들면, A이보다 나은 B 3 배보다 더 잘 C 2 번으로 평가 된 것을 의미 세 가지 책

A B C 
    _ _ _ 
A|0 3 2 
B|2 0 3 
C|1 2 0 

정렬. 행을 요약하면

A: (AB - BA) + (AC - CA) = (3 - 2) + (2 - 1) = 2 
B: (BA - AB) + (BC - CB) = (2 - 3) + (3 - 2) = 0 
C: (CA - AC) + (CB - BC) = (1 - 2) + (2 - 3) = -2 

등으로 표시되며 A > B > C으로 정렬됩니다.

---

당신은 페이지 순위를 사용하지 않을 경우, 다음 행렬을 제거하고 각 책에 대해 0으로 초기화 정수를 연결하여 동일한 결과를 얻을 수 있습니다. A이 B 이상으로 선택되면 A과 연결된 정수를 증가시키고 B과 연관된 정수를 감소시킵니다.

^{1 미안하지만 나는 본질적으로 수학적 결과 인 것을 어떻게 생각 하는지를 알고 있습니다.}

Answer 3

오래된 질문을 일깨우는 것에 대해 유감스럽게 생각합니다. 그러나 이것은 당신에게 유용 할 것이라고 생각합니다.

동일한 작업을 수행 할 때 온라인 삽입 정렬을 선택합니다. 소규모 컬렉션에서 완벽한 선택입니다. 예를 들어, 10 권의 도서는 평균 14 건의 비교 만하면됩니다. 가장 좋은 경우에는 9 개의 비교 만 수행하면됩니다 (컬렉션이 이미 정렬 된 경우).

퀵 정렬을 선택하면 20 번의 비교 (평균)를 수행해야하지만 항상 더러운 정렬 (컬렉션의 모든 책과 각 책을 비교하여)이 더 좋습니다.

어쨌든 온라인 순위 (이전 비교 결과에 근거한 다음 페어 선택)를 수행해야합니다.

이 모든 솔루션은 전이 관계에 대한 가정이 하나 있음을 유의하십시오 (book1이 book2보다 좋고 book2가 book3보다 좋으면 book1이 더 좋고 book3보다 좋음). 그것이 당신을 위해 작동하지 않는 경우 - 당신은 그들을 순위 수 없습니다. 당신은 완벽 위키 백과에 설명 모두 알고리즘을 찾을 수 있습니다

:
http://en.wikipedia.org/wiki/Insertion_sort
http://en.wikipedia.org/wiki/Quick_sort