역순쌍(inversion) 개수 계산기

앞에 있는 값이 뒤에 있는 값보다 큰 쌍입니다. i < j인데 a[i] > a[j]인 (i, j)를 셉니다. 완전히 정렬된 수열은 0이고, 거꾸로 정렬된 수열은 n(n−1)/2로 최대가 됩니다. 수열이 «얼마나 뒤죽박죽인지»를 재는 가장 기본적인 값입니다.

이웃끼리 바꾸기만으로 정렬할 때의 최소 교환 횟수와 정확히 같기 때문입니다. 이웃 두 개를 한 번 바꾸면 역순쌍이 하나 줄거나 늘 뿐이므로, 0으로 만들려면 그 개수만큼 바꿔야 합니다. 그래서 버블 정렬의 실제 교환 횟수가 곧 역순쌍의 개수이고, 이 계산기는 두 값이 같은 것을 화면에서 보여 줍니다.

두 정렬된 조각을 합칠 때, 오른쪽 조각의 값을 먼저 꺼냈다면 왼쪽 조각에 남아 있는 것들은 모두 그 값보다 큽니다. 남은 개수를 한꺼번에 더하면 됩니다. 합치는 비용에 얹혀 가므로 전체가 O(n log n)이고, 이중 반복의 O(n²)보다 훨씬 빠릅니다. 원소가 512개면 비교 횟수가 13만 대 6천으로 갈립니다.

켄달 타우 상관계수는 τ = 1 − 2·(역순쌍 / 최대)로 계산합니다. 두 순위가 완전히 같으면 1, 완전히 뒤집혔으면 −1입니다. 이 계산기는 넣은 수열을 «오름차순 순위와 견준 것»으로 보고 타우를 냅니다. 다만 같은 값이 있을 때 동점을 따로 보정하는 타우-b와는 값이 다를 수 있습니다.

15퍼즐 같은 슬라이딩 퍼즐이 풀리는지 가릅니다. 조각을 한 번 밀 때마다 역순쌍의 홀짝과 빈칸 줄 번호의 홀짝이 함께 뒤집히므로, 이 둘의 조합이 목표와 맞지 않으면 아무리 밀어도 풀리지 않습니다. «14와 15만 바뀐» 퍼즐이 영원히 안 맞춰지는 이유가 이것입니다.

a[i] > a[j]로 엄격히 큰 경우만 셉니다. 같은 값끼리는 순서를 바꿔도 정렬 상태가 달라지지 않으므로 역순쌍이 아닙니다. 예를 들어 [2, 2, 2]는 0쌍, [2, 1, 2]는 1쌍입니다.

계통이 다른 세 방법으로 각각 구해 대조합니다. 이중 반복으로 직접 세기, 병합정렬을 고쳐 세기, 버블 정렬을 실제로 돌려 교환 횟수 세기입니다. 셋이 같은 실수를 저지를 길이 없으므로 값이 모두 일치하면 믿을 수 있습니다. 화면에 세 값을 나란히 냅니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지고 넣은 값은 이 기기에만 남습니다.