[Do it! 알고리즘 코딩테스트: Chapter 4] 삽입 정렬(Insertion Sort), 퀵 정렬(Quick Sort)

본 포스팅은 Do it! 알고리즘 코딩테스트: C++편을 토대로 공부한 내용을 정리하기 위한 포스팅입니다.

 

 

1. 삽입 정렬(Insertion Sort)

 삽입 정렬(Insertion Sort)은 배열을 정렬하는 간단한 알고리즘 중 하나다. 이 알고리즘은 두 번째 요소부터 시작하여 현재 요소를 정렬된 부분과 비교하면서 적절한 위치에 삽입하는 방식으로 동작한다.

 

삽입 정렬의 과정

1. 현재 index에 있는 데이터 값을 선택한다.
2. 현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치를 탐색한다.
3. 삽입 위치부터 index에 있는 위치까지 shift 연산을 수행한다.
4. 삽입 위치에 현재 선택한 데이터를 삽입하고 index++ 연산을 수행한다.
5. 전체 데이터의 크기만큼 index가 커질 때까지, 즉 선택할 데이터가 없을 때까지 반복한다.

시간 복잡도

• 최선의 경우 (이미 정렬된 상태): O(n)
• 최악의 경우 (역순으로 정렬된 상태): O(n²)
• 평균적인 경우: O(n²)

 

// Baekjoon Online Judge Problem. 11399

#include <iostream>
#include <vector>
using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);


	int N;
	cin >> N;
	vector<int> v(N, 0);

	for (int i = 0; i < N; i++) {
		cin >> v[i];
	}
	
	for (int i = 1; i < N; i++) {
		int index = i - 1;
		int temp = v[i];

		while (index >= 0 && temp < v[index]) {
			v[index + 1] = v[index];
			index--;
		}

		v[index + 1] = temp;
	}

	int sum = v[0];
	
	for (int i = 1; i < N; i++) {
		v[i] = v[i] + v[i - 1];
		sum += v[i];
	}

	cout << sum << endl;

	return 0;

}

 

 

2. 퀵 정렬(Quick Sort)

 퀵 정렬(Quick Sort)은 분할 정복(Divide and Conquer) 기법을 사용하는 효율적인 정렬 알고리즘이다. 배열을 기준값(pivot)을 중심으로 두 개의 부분으로 나눈 뒤, 각 부분을 재귀적으로 정렬하는 방식으로 동작한다

 

 퀵 정렬의 과정

1. 데이터를 분할하는 pivot을 설정한다.

2. pivot을 기준으로 다음 a~e 과정을 거쳐 데이터를 2개의 집합으로 분리한다.

   2-a. start가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start를 오른쪽으로 1칸 이동한다.

   2-b. end가 가리키는 데이터가 pivot이 가리키는 데이터보다 크면 end를 왼쪽으로 1칸 이동한다.

   2-c. start가 가리키는 데이터가 pivot이 가리키는 데이터보다 크고, end가 가리키는 데이터가 pivot이 가리키는 데이터보            다 작으면 start, end가 가리키는 데이터를 swap하고 start는 오른쪽, end는 왼쪽으로 1칸씩 이동한다. 

   2-d. start와 end가 만날 때까지 2-a~2-c를 반복한다.

   2-e. start와 end가 만나면 만난 지점에서 가리키는 데이터와 pivot이 가리키는 데이터를 비교하여 pivot이 가리키는 데이            터가 크면 만난 지점의 오른쪽에, 작으면 만난 지점의 왼쪽에 pivot이 가리키는 데이터를 삽입한다.

3. 분리 집합에서 각각 다시 pivot을 선정한다.

4. 분리 집합이 1개 이하가 될 때까지 과정 1~3을 반복한다.

 

 

// Baekjoon Online Judge Problem. 11004

#include <iostream>
#include <vector>
using namespace std;

int partition(int start, int end, vector<int> &v) {
	int pivot = v[start];
	int low = start + 1;
	int high = end;

	while (low < high) {

		while (low <= end && v[low] <= pivot) {
			low++;
		}
		while (high >= start && v[high] > pivot) {
			high--;
		}

		if (low < high) {
			swap(v[low], v[high]);
		}
	}

	swap(v[start], v[high]);
	
	return high;
}

void quick_sort(int start, int end, vector<int> &v) {
	
	if (start < end) {
		int pivotindex = partition(start, end, v);
		quick_sort(start, pivotindex - 1, v);
		quick_sort(pivotindex + 1, end, v);
	}
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, K;
	cin >> N >> K;

	vector<int> A(N);
	
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}

	quick_sort(0, A.size() - 1, A);

	cout << A[K - 1];

	return 0;

}

 

 교재에서 퀵 정렬로 문제를 풀라고 했는데 아무리해도 답이 나오지 않아서 해설 코드를 따라쳐도 되지 않았다. 그래서 그냥 algorithm 헤더 파일에 있는 sort 알고리즘으로 쉽게 해결했다.

 

// Baekjoon Online Judge Problem. 11004

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, K;
	cin >> N >> K;

	vector<int> A(N);
	
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}

	sort(A.begin(), A.end());

	cout << A[K - 1];

	return 0;

}