정렬 알고리즘 비교·교환 횟수 계산기

입력과 무관하게 언제나 n(n−1)/2회입니다. 남은 구간을 끝까지 훑어 최솟값을 찾기 때문에 이미 정렬된 배열을 줘도 한 번도 줄지 않습니다. 대신 교환은 최대 n−1회로 적고, 이미 정렬돼 있으면 0회입니다.

역위(앞이 뒤보다 큰 쌍)의 개수와 정확히 같습니다. 붙어 있는 것끼리만 바꾸므로 한 번 바꿀 때 역위가 정확히 하나 줄기 때문입니다. 삽입 정렬에서 한 칸씩 밀어낸 횟수도 같은 이유로 역위 수와 같아, 겉보기에 다른 두 알고리즘이 실은 같은 일을 합니다.

삽입 정렬이 비교 n−1회, 이동 0회로 끝나 가장 빠릅니다. 반대로 첫 원소나 마지막 원소를 피벗으로 잡는 퀵 정렬은 분할이 한쪽으로만 쏠려 바로 이 입력에서 최악(n(n−1)/2회 비교)이 됩니다. 같은 O(n log n) 표기 안에서도 입력에 따라 순위가 뒤집힙니다.

원소가 어느 정도 많을 때만 이득입니다. 세 값을 견주는 데도 비교가 들어, 정렬된 5개에서는 마지막 원소 피벗이 10회·중앙값이 15회로 오히려 손해입니다. 8개에서 뒤집히고 16개면 120회 대 62회로 크게 벌어집니다. 실제 라이브러리가 작은 구간에서 삽입 정렬로 갈아타는 이유가 이 언저리입니다.

비교는 두 원소를 견준 횟수, 교환은 두 원소의 자리를 맞바꾼 횟수, 이동은 원소를 다른 칸에 쓴 횟수로 셉니다. 교환 한 번은 원소를 두 칸에 쓰는 것이라 이동으로 환산하면 2회이므로 두 값을 곧바로 견주면 안 됩니다. 반복문 조건에서 인덱스끼리 견주는 것은 비교로 세지 않습니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.