정렬 개념 정리

유기태·2022년 6월 10일

sort 종류(오름차순 기준)

1. selct_Sort

#include<iostream>
using namespace std;

int arr[100];
int K;

void b_sort();
void solution();

void b_sort() {
	for (int i = K - 1; i > 0; i--) {
		int max = 0;
		for (int j = 0; j < i + 1; j++) {
			if (arr[max] < arr[j])max = j;
		}
		swap(arr[max], arr[i]);
	}
}

void solution() {
	for (int i = 0; i < K; i++)
		cout << arr[i] << ' ';
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> K;
	for (int i = 0; i < K; i++)
		cin >> arr[i];

	b_sort();
	solution();
}

가장 간단한 정렬 알고리즘으로 가장 큰 변수를 색출하여 맨 왼쪽으로 옮기는 작업을 반복하는 작업이다.
가장 큰 수를 색출하기 위해 정렬된 수를 제외한 배열을 계속 탐색해야하니 시간 복잡도가 높다.
시간 복잡도는 O(N^2)이다.

2. Bubble_sort

#include<iostream>
using namespace std;

int arr[100];
int K;

void bubble_sort();
void solution();

void bubble_sort() {
	for (int i = 0; i < K; i++) {
		for (int j = 0; j < K - i-1; j++) {
			if(arr[j] > arr[j + 1])swap(arr[j], arr[j + 1]);
		}
	}
}

void solution() {
	for (int i = 0; i < K; i++)
		cout << arr[i] << ' ';
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> K;
	for (int i = 0; i < K; i++)
		cin >> arr[i];

	bubble_sort();
	solution();
}

기본적인 정렬 알고리즘으로 선택 정렬과 다르게 max값을 찾아 가장 오른쪽 인덱스로 넘기는게 아닌 큰 변수를 점점 오른쪽으로 옮기는 식에 정렬이다.
선택 정렬과 마찬가지로 O(N^2)의 시간 복잡도를 가진다.

3. Merge_sort

#include<iostream>
using namespace std;

int arr[100];
int tmp[100];
int K;

void m_sort(int st,int en);
void merge(int st, int en);
void solution();

void m_sort(int st,int en) {
	if (st + 1 == en)return;
	int mid = (st + en) / 2;
	m_sort(st, mid);
	m_sort(mid, en);

	merge(st,en);
}

void merge(int st,int en) {
	int mid = (st + en) / 2;
	int c1 = st;
	int c2 = mid;
	for (int i = st; i < en; i++) {
		if (c1 == mid)tmp[i] = arr[c2++];
		else if (c2 == en)tmp[i] = arr[c1++];
		else if (arr[c1] < arr[c2])tmp[i] = arr[c1++];
		else tmp[i] = arr[c2++];
	}
	for (int i = st; i < en; i++)arr[i] = tmp[i];
}

void solution() {
	for (int i = 0; i < K; i++)
		cout << arr[i] << ' ';
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> K;
	for (int i = 0; i < K; i++)
		cin >> arr[i];

	m_sort(0,K);
	solution();
}

Merge_sort는 처음에 두 배열을 합하는 것으로 개념을 먼저 잡았다.

void merge(){
	int count1;
    int count2;
    for(int i=0;i<M1+M2;i++){
    	// M1, M2는 각각 합칠 배열들의 크기
       	// tmp는 m1,m2를 합한 배열
    	if(count1==M1)tmp[i]=arr[count2++];
        else if(count2==M2)tmp[i]=arr[count2++];
        else if(arr1[count1]<arr2[count2])tmp[i]=arr1[count1++];
        else tmp[i]=arr2[count2++];
    }
}

void merge(int st,int en) {
	int mid = (st + en) / 2;
	int c1 = st;
	int c2 = mid;
	for (int i = st; i < en; i++) {
		if (c1 == mid)tmp[i] = arr[c2++];
		else if (c2 == en)tmp[i] = arr[c1++];
		else if (arr[c1] < arr[c2])tmp[i] = arr[c1++];
		else tmp[i] = arr[c2++];
	}
	for (int i = st; i < en; i++)arr[i] = tmp[i];
}

4. Quick_sort

#include<iostream>
using namespace std;

int N;
int arr[1000000];

void v_sort(int st,int en) {
	if (st + 1 == en || st == en)return;
	int r = en - 1;
	int l = st + 1;
	int pivot = arr[st];

	while (1) {
		while (l <= r && pivot <= arr[r])r--;
		while (l <= r && pivot >= arr[l])l++;
		if (l > r)break;
		swap(arr[l], arr[r]);
	}
	swap(arr[st], arr[r]);
	v_sort(st, r);
	v_sort(r + 1, en);
}


int main(void) {
	ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> arr[i];

	v_sort(0,N);

	for (int i = 0; i < N; i++)
		cout << arr[i] << '\n';
}

5. counting_sort

#include<iostream>
using namespace std;

int N;

int freq[2000001];

void c_sort();

void c_sort() {
	int tmp = 0;
	int count = 0;
	for (int i = 0; i < N; i++) {
		cin >> tmp;
		freq[tmp + 1000000]++;
	}
	for (int i = 0; i < 2000001; i++) {
		if (freq[i] > 0) {
			for (int j = 0; j < freq[i]; j++) {
				cout << i - 1000000 << '\n';
				count++;
			}
		}
		if (count == N)
			break;
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> N;
	c_sort();
}

comparison_sort로 수의 최댓값이 정해져있을경우에 사용가능하다.
즉, 수의 범위가 한정적일 경우에만 사용가능하다. counting sort를 하기위해서는 해당 수의 범위만큼
freq 배열을 할당해야 하기 때문이다.

6. Radix_sort

7. STL_sort

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

int arr[10];
vector<int>v;
int N;

int main(void) {
	int tmp = 0;
	cin >> N;

	for (int i = 0; i < N; i++)
		cin >> arr[i]; 

	for (int i = 0; i < N; i++) {
		cin >> tmp;
		v.push_back(tmp);
	}
	//STL_sort(array)
	sort(arr, arr + N);
	//STL_sort(vector)
	sort(v.begin(), v.end());
	//sort(...,...,function)

	for (int i = 0; i < N;i++) {
		cout << arr[i] <<' ';
	}
	cout << '\n';
	for (auto x:v){
		cout << x << ' ';
	}
}