[코딩테스트][C++]이론4-1. 정렬

오늘은 정렬에 대해 학습해보기로 했다.

정렬알고리즘의 종류에는 버블, 선택, 삽입, 퀵,병합,기수가 있다. 

1.버블정렬

버블정렬은 인접한 요소끼리 비교하고 swap연산을 통해 정렬을 한다. 

간단하게 구현가능하지만 시간복잡도는 O(n^2)으로 다른 정렬 알고리즘에 비해 느린편

문제 예시1.

버블정렬 프로그램1

 

문제에서 요구하는바는 swap이 끝나고 change가 false로 유지될때의 i 값이다. for문이 몇번이나 수행됐는지 구하면 된다.

n의 최대가 500,000이기 때문에 버블정렬은 사용할 수 없다. 

어떤 방법을 사용할지 생각해보자면 일단 버블정렬이 수행되는 방식에 대해 생각해보면 좋다.

버블정렬은 1~n-1까지 왼쪽에서 오른쪽으로 이동하면서 swap을 수행한다. 이는 swap할때 왼쪽으로 1칸씩만 이동할 수 있다는 것이다. 따라서 데이터 정렬하기전과 정렬 후의 index를 비교해서 가장 많이 이동한 값이 for문이 수행된 횟수가 나온다.  그리고 정렬이 끝난 후 마지막으로 for문이 돌때를 고려하여 max에 1을 더해준다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> Node;

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

	int n;
	cin >> n;
	vector<pair<int, int>>a(n);

	for (int i = 0; i < n; i++) {
		cin >> a[i].first;
		a[i].second = i;
	}

	sort(a.begin(), a.end());
	int max = 0;

	for (int i = 0; i < n; i++) {
		if (max < a[i].second - i) {
			max = a[i].second - i;
		}
	}

	cout << max + 1;
}

 

2.선택 정렬

최대나 최소 데이터를 나열된 순으로 찾아가며 선택하고 그 수를 앞으로 보내면서 정렬하는 방법이다. 

문제예시2.

내림차순으로 자릿수 정렬하기

 

내장함수를 사용해도 풀 수 있지만 n의 길이가 길지 않아서 선택정렬을 통해 풀어보아도 된다.

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

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

	string n;
	cin >> n;
	vector<int>a(n.size(), 0);

	for (int i = 0; i < n.size(); i++) {
		a[i] = stoi(n.substr(i,1));
	}

	for (int i = 0; i < n.size(); i++) {
		int max = i;
		for (int j = i + 1; j < n.size(); j++) {		//제일 큰 수  구하기
			if (a[j] > a[max]) {
				max = j;
			}
		}
		if (a[i] < a[max]) {
			int tmp = a[i];
			a[i] = a[max];
			a[max] = tmp;
		}
	}

	for (int i = 0; i < a.size(); i++) {
		cout << a[i];
	}
}

 

3.삽입정렬

삽입정렬은 현재 정렬된 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입하는 방식이다. 

문제예시3.

ATM인출 시간 계산하기

ATM에서 모든 사람이 가장 빠른 시간에 인출하려면 시간이 가장 적게 걸리는 사람이 먼저 인출할 수 있도록 그리디하게 접근하면 된다.

그럼 오름차순으로 정렬을 하면 되는데 n의 최댓값이 1,000이고 시간제한이 1초여서 O(n^2)이하인 정렬 알고리즘이면 모두 사용 가능하다. 지금은 삽입정렬을 사용해보려고 한다.

#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>a(n, 0);
	vector<int>s(n, 0);			//합배열

	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i=0; i < n; i++) {
		int insertval = a[i];
		int insertidx = i;
		for (int j = i - 1; j >= 0; j--) {            //i 왼쪽을 탐색
			if (a[i] > a[j]) {
				insertidx = j + 1;			//i가 j보다 크다면 i는 j보다 오른쪽에 있어야한다.
				break;
			}
			if (j == 0) {
				insertidx = 0;
			}
		}
		for (int j = i; j > insertidx; j--) {
			a[j] = a[j - 1];					//j~insertidx까지 값을 바꾸면서 insertidx의 값이 j로 가도록 한다.
		}
		a[insertidx] = insertval;
	}
	s[0] = a[0];

	for (int i = 1; i < n; i++) {
		s[i] = s[i - 1] + a[i];
	}
	int sum = 0;
	for (int i = 0; i < n; i++) {
		sum += s[i];
	}
	cout << sum;
}