정렬 알고리즘(선택, 삽입, 버블, 머지, 퀵)

선택 정렬(Selection Sort)

선택 정렬은 배열의 맨 앞부터 차례대로 가장 작은 값을 찾는 정렬 방법이다.

인덱스 0부터 시작해 배열의 가장 작은 값을 찾아 해당 위치와 스왑한다.

비교하는 횟수는 n-1, n-2, n-3, ... 1개씩 비교한다

따라서 시간 복잡도는 항상 O(N^2)이 된다.

 

버블 정렬(Bubble Sort)

버블 정렬은 매번 연속된 두 개의 인덱스를 비교하여, 마치 거품이 보글보글 올라가는 것 처럼 정렬하는 방식이다.

첫 번째 인덱스 부터 시작해서 바로 다음 인덱스를 비교해서, 다음 인덱스가 더 작다면 스왑한다.

다음 인덱스와 다다음 인덱스를 비교하는 식으로 계속 증가해서 끝까지 비교한다.

이렇게 한 싸이클을 돌고 나면 배열의 제일 오른쪽엔 제일 큰 숫자가 차례대로 정렬 될 것이다.

버블정렬 또한 시간 복잡도는 항상 O(N^2)이 된다.

 

삽입 정렬(Insertion Sort)

삽입 정렬은 특정 위치에서 그 이하의 배열들을 비교하며 자신이 들어갈 위치를 찾아 그 곳에 삽입하는 방식이다.

특정 위치는 두 번째 인덱스 부터 제일 마지막 인덱스까지 차례대로 증가한다. 

삽입 정렬의 시간 복잡도는 최악의 경우 O(N^2)이지만, 이미 정렬 되어있는 경우, 각 위치에서 한 번씩만 비교하기 때문에 O(N)이 된다.

 

합병 정렬(Merge Sort)

합병 정렬은 분할 정복 방식의 알고리즘이다.

 

분할 과정은 우선 배열을 반으로 나눈다. 쪼갠 배열의 크기가 0일때까지 반복한다.

 

합병 과정은 반으로 쪼갠 두 배열  A와 B를 합병한다.

A의 제일 왼쪽 인덱스와 B의 제일 왼쪽 인덱스를 차례대로 비교하며 더 작은 값을 임시 배열에 저장한다.

A와 B 둘 중 한 배열의 끝에 다다를때까지 해당 작업을 반복한 후, 아직 저장 못 한 남은 배열 값을 임시 배열에 저장한다.

그 후 원본 배열에 차례대로 정렬된 임시 배열 값을 적용한다.

 

합병 정렬의 시간 복잡도는 분할, 합병의 두 단계로 나눠서 생각한다.

분할 과정은 배열을 항상 반으로 나누므로 O(logN)이라 할 수있다.

합병 과정은 나눈 배열 A, B를 차례대로 모두 탐색하므로 O(N)이라 할 수 있다.

따라서 전체 시간 복잡도는 O(NlogN)이 된다.

 

퀵 정렬(Quick Sort)

퀵 정렬도 합병 정렬처럼 분할 정복 방식이다.

 

퀵 정렬은 특정 위치를 pivot으로 설정한다. 이 pivot을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽에 두는 방식으로 정렬한다.

pivot의 위치는 아무 위치나 설정해도 좋다. 보통 시작점, 끝점이나 중간 지점을 설정하는데 시작점으로 설정했다.

그 후 pivot 보다 큰 값을 찾을 left, 작은 값을 찾을 right 변수를 지정한다.

left의 위치는 pivot + 1로 즉 start+1이고, right의 위치는 배열의 끝 지점 즉 end 이다.

left는 1씩 증가하며 pivot보다 큰 값을 찾고, right는 1씩 감소하며 pivot보다 작은 값을 찾는다.

찾고 난 뒤에는 left와 right를 스왑한다. 이때 만약 right가 left보다 왼쪽에 위치하게 된다면, 즉 엇갈린다면 

pivot과 right를 스왑한 후 pivot을 중심으로 왼쪽, 오른쪽으로 분할한다.

 

퀵 정렬의 시간 복잡도는 O(NlogN)이지만, 미리 정렬되어 있는 최악의 경우 분할이 N번만큼 일어나기 때문에 O(N^2)이 된다.

---

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algorithm/%EC%A0%95%EB%A0%AC.cpp

chosh95/STUDY

 

C++ 코드

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

vector<int> selection_sort(const vector<int> input) {
	vector<int> v = input;
	for (int i = 0; i < v.size()-1; i++) {
		int tmp = i;
		for (int j = i + 1; j < v.size(); j++) {
			if (v[tmp] >= v[j]) tmp = j;
		}
		swap(v[i], v[tmp]);
	}
	return v;
}

vector<int> bubble_sort(const vector<int> input) {
	vector<int> v = input;
	for (int i = 0; i < v.size(); i++) {
		for (int j = 0; j < v.size()-i-1; j++) {
			if (v[j] > v[j+1]) swap(v[j], v[j+1]);
		}
	}
	return v;
}

vector<int> insertion_sort(const vector<int> input) {
	vector<int> v = input;
	for (int i = 1; i < v.size(); i++) {
		int key = v[i], j = i - 1;
		while (j >= 0 && key < v[j]) {
			swap(v[j], v[j+1]);
			j--;
		}
		v[j + 1] = key;
	}
	return v;
}

vector<int> merge(const vector<int> input, int start, int end, int med) {
	vector<int> v = input;
	vector<int> tmp;
	int i = start, j = med + 1;

	while (i <= med && j <= end) {
		if (v[i] < v[j]) tmp.push_back(v[i++]);
		else if (v[i] > v[j]) tmp.push_back(v[j++]);
	}

	while (i <= med) tmp.push_back(v[i++]);
	while (j <= end) tmp.push_back(v[j++]);

	for (int a = 0, b = start; b <= end; b++) {
		v[b] = tmp[a++];
	}
	return v;
}

vector<int> merge_sort(const vector<int> input, int start, int end) {
	vector<int> v = input;
	if (start < end) {
		int med = (start + end) / 2;
		v = merge_sort(v, start, med);
		v = merge_sort(v, med + 1, end);
		v = merge(v, start, end, med);
	}
	return v;
}

vector<int> quick_sort(const vector<int> input, int start, int end) {
	vector<int> v = input;
	if (start >= end) return v;
	int pivot = start, left = start + 1, right = end;
	while (left <= right) {
		while (left <= end && v[left] <= v[pivot]) left++;
		while (right > start && v[right] >= v[pivot]) right--;
		if (left > right) swap(v[pivot], v[right]);
		else swap(v[left], v[right]);
	}
	v = quick_sort(v, start, right - 1);
	v = quick_sort(v, right + 1, end);
	return v;
}
int main()
{
	vector<int> input;
	srand((unsigned int)time(NULL));
	for (int i = 0; i < 100; i++) {
		input.push_back(rand() % 10000 + 1);
	}

	cout << "selection sort\n";
	vector<int> res;
	res = selection_sort(input);
	for (int i = 0; i < res.size(); i++)
		cout << res[i] << " ";
	cout << endl << endl;

	cout << "bubble sort\n";
	res = bubble_sort(input);
	for (int i = 0; i < res.size(); i++)
		cout << res[i] << " ";
	cout << endl << endl;

	cout << "insertion sort\n";
	res = insertion_sort(input);
	for (int i = 0; i < res.size(); i++)
		cout << res[i] << " ";
	cout << endl << endl;

	cout << "merge sort\n";
	res = merge_sort(input,0,input.size()-1);
	for (int i = 0; i < res.size(); i++)
		cout << res[i] << " ";
	cout << endl << endl;

	cout << "quick sort\n";
	res = quick_sort(input, 0, input.size() - 1);
	for (int i = 0; i < res.size(); i++)
		cout << res[i] << " ";
	cout << endl << endl;
}