목록이 얼마나 정렬되어 있는지 측정하는 방법이 있습니까?

목록이 정렬되어 있는지 아닌지 (부울) 아는 것이 아니라 통계의 상관 계수와 같은 “정렬”의 비율과 같은 것입니다.

예를 들어

목록의 항목이 오름차순 인 경우 비율은 1.0입니다.
목록이 내림차순으로 정렬되면 비율은 -1.0입니다.
목록이 거의 오름차순으로 정렬되면 비율은 0.9 또는 1에 가까운 값입니다.
목록이 전혀 정렬되지 않은 경우 (임의의 경우) 비율은 0에 가깝습니다.

실습을 위해 스칼라에 작은 도서관을 쓰고 있습니다. 정렬 속도가 유용하다고 생각하지만 그와 관련된 정보는 찾지 못했습니다. 어쩌면 나는 그 개념에 대한 적절한 용어를 모른다.

답변

목록에서 반전 수를 간단히 계산할 수 있습니다.

전도

유형의 요소 시퀀스에서 반전 T은의 세트에서 일부 순서 <에 따라 순서가 다르게 나타나는 한 쌍의 시퀀스 요소입니다 T.

에서 위키 백과 :

공식적으로 A(1), A(2), ..., A(n)일련의 n숫자를 보자 .
만약i < j 와 A(i) > A(j), 그 쌍은 (i,j)이라고 반전 의를 A.

그만큼 시퀀스 반전 번호 는 정렬의 일반적인 측정 방법 중 하나입니다.
공식적으로, 반전 번호는 반전 횟수, 즉,

이러한 정의를보다 명확하게하려면 sequence 예제를 고려하십시오 9, 5, 7, 6. 이 순서는 반전 (0,1), (0,2), (0,3), (2,3) 과 반전 번호가 4 있습니다.

0와 사이의 값을 원하면 1반전 숫자를로 나눌 수 있습니다 N choose 2.

목록 정렬 방식에 대해이 점수를 계산하는 알고리즘을 실제로 만들려면 다음 두 가지 방법이 있습니다.

접근법 1 (결정 론적)

자주 사용하는 정렬 알고리즘을 수정하여 실행시 수정되는 반전 수를 추적하십시오. 이것은 사소하지 않으며 선택한 정렬 알고리즘에 따라 다양한 구현이 있지만, 시작한 정렬 알고리즘보다 비싸지 않은 (복잡성 측면에서) 알고리즘으로 끝납니다.

이 경로를 사용하는 경우 “스왑”을 계산하는 것만 큼 간단하지는 않습니다. 예를 들어 Mergesort는 최악의 경우 O(N log N)이지만 내림차순으로 정렬 된 목록에서 실행하면 모든 N choose 2반전 이 수정됩니다 . 그것은 작업 O(N^2)에서 수정 된 반전 O(N log N)입니다. 따라서 일부 작업은 불가피하게 한 번에 두 개 이상의 반전을 수정해야합니다. 구현에주의를 기울여야합니다. 참고 : O(N log N)복잡 하게이 작업을 수행 할 수 있습니다 .

관련 : 순열에서 “반전”수 계산

접근법 2 (확률 론적)

무작위로 샘플 쌍 (i,j),i != j
각 쌍에 대해 list[min(i,j)] < list[max(i,j)](0 또는 1)
이 비교의 평균을 계산 한 다음 N choose 2

나는 당신이 정확성을 요구하지 않는 한 개인적으로 확률 론적 접근을 할 것입니다-구현하기가 쉽기 때문입니다.

당신이 정말로 원하는 것은 값 (경우 z'사이) -1에 (정렬 내림차순) 1(정렬 오름차순)는, 당신은 단순히 위의 값 (매핑 할 수 있습니다 z사이에), 0(정렬 오름차순) 및 1공식을 사용하여이 범위 (정렬 내림차순) :

z' = -2 * z + 1

답변

목록 (또는 다른 순차적 구조)을 정렬하는 방법에 대한 전통적인 측정 방법은 반전의 수입니다.

반전 수는 a <b AND b a의 쌍 (a, b) st 인덱스 수입니다 <<. 이러한 목적 <<을 위해 특정 정렬에 대해 선택한 주문 관계를 나타냅니다.

완전히 정렬 된 목록에는 반전이없고 완전히 반대의 목록에는 최대 반전 수가 있습니다.

답변

실제 상관 관계를 사용할 수 있습니다.

정렬 된 목록의 각 항목에 0부터 시작하는 정수 순위를 지정한다고 가정하십시오. 요소 위치 인덱스 대 순위의 그래프는 직선의 점처럼 보입니다 (위치와 순위 사이의 상관 관계는 1.0).

이 데이터에 대한 상관 관계를 계산할 수 있습니다. 역 정렬의 경우 -1 등이 표시됩니다.

답변

큰 답이 있었고, 완성도를 위해 수학적 측면을 추가하고 싶습니다.

정렬 된 목록과 얼마나 관련되어 있는지 측정하여 목록이 정렬 된 정도를 측정 할 수 있습니다. 그렇게하려면 순위 상관 관계 (가장 알려진 Spearman ‘s )를 사용하면 일반적인 상관 관계와 정확히 동일하지만 항목의 아날로그 값 대신 목록에서 요소의 순위를 사용합니다.
상관 계수 (정확한 정렬의 경우 +1, 정확한 반전의 경우 -1) 와 같은 많은 확장이 존재합니다.
이를 통해 순열 중심 한계 정리와 같이이 측정에 대한 통계적 속성을 가질 수 있으며,이를 통해 임의의 목록에 대한이 측정의 분포를 알 수 있습니다.

답변

숫자 목록의 경우 반전 수를 제외하고 정렬 된 상태에서 평균 제곱 거리를 상상할 수 있습니다.

#! ruby
d = -> a { a.zip( a.sort ).map { |u, v| ( u - v ) ** 2 }.reduce( :+ ) ** 0.5 }

a = 8, 7, 3, 4, 10, 9, 6, 2, 5, 1
d.( a ) #=> 15.556
d.( a.sort ) #=> 0.0
d.( a.sort.reverse ) # => 18.166 is the worrst case

답변

나는 “최상의”방법을 확신하지 못하지만 간단한 방법은 모든 요소를 그다음 요소와 비교하고 element2> element 1 (또는 테스트하려는 대상)이면 카운터를 증가시킨 다음 총 수로 나눕니다. 요소 그것은 당신에게 백분율을 제공해야합니다.

답변

나는 비교를 세어 총 비교 수로 나눕니다. 다음은 간단한 파이썬 예제입니다.

my_list = [1,4,5,6,9,-1,5,3,55,11,12,13,14]

right_comparison_count = 0

for i in range(len(my_list)-1):
    if my_list[i] < my_list[i+1]: # Assume you want to it ascending order
        right_comparison_count += 1

if right_comparison_count == 0:
    result = -1
else:
    result = float(right_comparison_count) / float((len(my_list) - 1))

print result