정렬 알고리즘 (거품, 선택, 삽입 정렬)

※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장.

 

목차 (눌러서 이동)

 

거품 정렬 (Bubble Sort)

바로 뒤의 원소와 비교해 순서를 바꾸는 작업을 원소의 개수만큼 반복한다. 반복할 때마다 가장 큰 원소가 맨 뒤에 위치하므로 매번 반복의 길이는 1씩 줄어든다. 

 

N 개 원소에 대해 N + (N-1) + (N-2) + ... + 2 + 1, 즉, (N + 1) * N / 2 만큼 연산한다. 최대 차항은 N^2 이므로 O(N^2) 의 시간 복잡도를 가진다.

 

void bubbleSort(vector<int>& v) {
	for (int i = 0; i < v.size() - 1; ++i) {
		for (int j = 0; j < v.size() - (i + 1); ++j) 
			if (v[j + 1] < v[j]) swapVectorElement(v, j, j+1);
	}
}

 

위는 가장 단순한 형태의 거품 정렬인데 주어지는 배열에 상관없이 모든 반복문을 순회한다. 내부의 if 문에 진입할 때 배열의 순서가 바뀌는데, 진입하지 않는다면 이미 모두 정렬된 것이다. 이를 이용해 불필요한 반복을 줄일 수 있다.

 

void bubbleSortOpt(vector<int>& v) {

	for (int i = 0; i < v.size() - 1; ++i) {
		bool swapped = false;

		for (int j = 0; j < v.size() - (i + 1); ++j) {
			if (v[j + 1] < v[j]) {
				swapVectorElement(v, j, j+1);
				swapped = true;
			}
		}
		if (!swapped) break;
	}
}

 

실제로 정렬된 배열을 통해 반복의 횟수를 세어보면 bubbleSort 는 (1 + N) * N / 2 만큼 반복하지만, bubbleSortOpt 는 내부의 for 문만 한 번 진행하므로 N 번만 반복한다.

선택 정렬 (Selection Sort)

배열에서 매번 최솟값을 찾아 앞 (혹은 뒤) 에서부터 쌓아 나간다. 거품 정렬처럼 매번 반복의 길이가 1씩 줄어들어 N 개의 배열 원소에 대해 (1 + N) * N / 2 번의 연산을 반복하므로 O(N^2) 의 시간 복잡도를 가진다.

 

void selectionSort(vector<int>& v) {
	for (int i = 0; i < v.size(); ++i) {
		int minIndex = i;
		
		for (int j = i + 1; j < v.size(); ++j) 
			if (v[j] < v[minIndex]) minIndex = j;
            
		swapVectorElement(v, i, minIndex);
	}
}

삽입 정렬 (Insertion Sort)

반복할 때마다 배열의 앞부분에 정렬된 부분 배열을 쌓아 나간다. 아직 정렬되지 않은 부분의 각 원소를 정렬된 부분 배열의 원소들과 비교하며 정렬된 부분 배열에서의 위치를 찾아 삽입해 나간다.

 

void insertionSort(vector<int>& v) {
	for (int i = 1; i < v.size(); ++i) {
		for (int j = i; j > 0; --j) {
			if (v[j - 1] < v[j]) break;
			swapVectorElement(v, j - 1, j);
		}
	}
}

 

이미 정렬된 배열에 대해서는 매번 if 문의 break 를 수행하므로 선택 정렬이나 기본 거품 정렬보다 평균적으로 좋은 수행 속도를 보인다.