#5-1 The Art of Computer Programming - 정렬과 검색

이번 절은 순열의 조합 성질에 대한 내용 및 '반전'에 대한 내용이다.

순열은 정렬되지 않는 입력 자료를 대표하기에 정렬 알고리즘 연구에 중요하다.

순열은 이전 장들에서도 자주 나왔으며 이제부터는 조합 수학에 대해서도 많이 배우게 될 것이다.

순열의 성질들은 자체로 흥미로운 부분이 있으며, 5-1절은 수학적인 내용이 많을 예정이다.

 

반전: i < j이고 a_i > a_j인 두 원소의 쌍.

예를 들어 순열 3 1 4 2에는 (3,1), (3,2), (4,2)라는 세 개의 반전이 있다.

각 반전은 순서에 맞지 않는 원소들의 쌍이며, 따라서 반전이 전혀 없는 순열은 정렬되어 있는 순열뿐이다.

반전이라는 개념은 동적 저장소 할당 알고리즘 분석 시 사용한다.

반전이라는 개념은 크레이머가 일차연립방정식을 푸는 법칙에 관련해 소개했었다.

 

반전표 : 왼쪽에 있는 원소들 중 큰 원소들의 개수의 순열

예를 들어 순열 5 9 1 8 2 6 4 7 3의

반전 표는 순열 2 3 6 4 0 2 2 1 0이다.

 

마지막 결론은

n개의 원소들의 순열들 중 반전이 k개이고 지표가 l인 순열들의 개수는

반전이 l개이고 지표가 k인 것들의 개수와 같다. 이다.