[sorting | practice] Inversion 개수 출력

사이즈가 n인 array A가 있다. 해당 array의 inversion의 개수를 출력하는 프로그램을 작성하여라.

 

#그냥 구현하기

#include <stdio.h>
#include <iostream>
using namespace std;

int main(void) {
	int arr[10] = { 4,5,6,2,3,10,8,1,9,7 };
	int inversion_count = 0;
	for (int i = 0; i < 10; i++) {
		for (int j = i; j < 10; j++) {
			if (arr[i] > arr[j]) inversion_count++;
		}
	}
	cout << inversion_count;
}

 

#버블 정렬 사용해서 구현하기

#include <stdio.h>
#include <iostream>
using namespace std;

int main(void) {
	int arr[10] = { 4,5,6,2,3,10,8,1,9,7 };
	int temp;
	int inversion_count = 0;

	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 9 - i; j++) {
			if (arr[j] > arr[j + 1]) {
				temp = arr[j + 1];
				arr[j + 1] = arr[j];
				arr[j] = temp;
				inversion_count++;
			}
		}
	}
	cout << inversion_count;
}

 

#삽입 정렬 사용하기

#include <stdio.h>
#include <iostream>
using namespace std;

int main(void) {
	int arr[10] = { 4,5,6,2,3,10,8,1,9,7 };
	int inversion_sort = 0;
	int j;
	for (int i = 1; i < 10; i++) {
		int key = arr[i];
		int temp;
		for (j = i - 1; j >= 0 && arr[j] > key; j--) {
			arr[j + 1] = arr[j];
			temp = j;
			inversion_sort++;
		}
		arr[j + 1] = key;
		
	}
	cout << inversion_sort;
}

 

 

세 개의 결과 모두 18이 출력된다.

 

sorting algorithm을 수행하면서 두 element 간에 swap이 존재하는 경우 inversion의 개수를 1 증가시켜 준다.

==> O(n**2)시간이 소모된다.