[백준] 2750 수 정렬하기

[백준] 2750 수 정렬하기

• https://www.acmicpc.net/problem/2750

버블 정렬

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

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

	int n;
	cin >> n;

	vector<int> vec;
	int input;
	for (int i = 0; i < n; ++i) {
		cin >> input;
		vec.push_back(input);
	}

	//버블정렬
	for (int i = 0; i < n-1; ++i) {
		for (int j = 0; j < n - i -1; ++j) {
			if (vec[j] > vec[j + 1]) {
				swap(vec[j], vec[j + 1]);
			}
		}
	}

	for (int i = 0; i < n; ++i) {
		cout << vec[i] << "\n";
	}

	return 0;
}

삽입 정렬

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

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

	int n;
	cin >> n;

	vector<int> vec;
	int input;
	for (int i = 0; i < n; ++i) {
		cin >> input;
		vec.push_back(input);
	}

	//삽입정렬
	for (int i = 1; i < n; ++i) {
		for (int j = i; j > 0; --j) {
			if (vec[j - 1] > vec[j]) {
				swap(vec[j-1], vec[j]);
			}
		}
	}

	for (int i = 0; i < n; ++i) {
		cout << vec[i] << "\n";
	}

	return 0;
}

퀵 정렬

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

int n;
vector<int> vec;


void quickSort(int start, int end) {
	//정렬하고자하는 배열의 길이 1
	if (start == end) {
		//no action
	}
	//정렬하고자하는 배열의 길이 2
	else if (start + 1 == end) {
		if (vec[start] > vec[end]) swap(vec[start], vec[end]);
	}
	//정렬하고자하는 배열의 길이 2이상인 경우 쪼개기
	else {
		int pivot = start;
		int low = start + 1;
		int high = end;

		while (true) {
			while (low <= end && vec[low] <= vec[pivot]) {
				low++;
			}
			while (high > start && vec[high] >= vec[pivot]) {
				high--;
			}
			if (low > high) break;
			swap(vec[low], vec[high]);
		}
		swap(vec[pivot], vec[high]);
		pivot = high;

		if (pivot-1 > start) {
			quickSort(start, pivot-1);
		}
		if (pivot+1 < end) {
			quickSort(pivot + 1, end);
		}
	}
	return;
}



int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> n;

	vec.clear();
	int input;
	for (int i = 0; i < n; ++i) {
		cin >> input;
		vec.push_back(input);
	}

	//퀵 정렬
	quickSort(0, n - 1);

	for (int i = 0; i < n; ++i) {
		cout << vec[i] << "\n";
	}
	return 0;
}

병합 정렬

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

int n;
vector<int> vec;

void merge(int start1, int end1, int start2, int end2) {
	vector<int> sorted;
	int idx1 = start1;
	int idx2 = start2;

	while (idx1 <= end1 && idx2 <= end2) {
		if (vec[idx1] < vec[idx2]) {
			sorted.push_back(vec[idx1]);
			idx1++;
		}
		else {
			sorted.push_back(vec[idx2]);
			idx2++;
		}
	}

	while (idx1 <= end1) {
		sorted.push_back(vec[idx1]);
		idx1++;
	}
	while (idx2 <= end2) {
		sorted.push_back(vec[idx2]);
		idx2++;
	}

	for (int i = 0; i < sorted.size(); ++i) {
		vec[start1 + i] = sorted[i];
	}
	return;
}

void mergeSort(int start, int end) {
	//정렬하고자하는 배열의 길이 1
	if (end == start) {
		//no action
	}
	//정렬하고자하는 배열의 길이 2
	else if (end - start == 1) {
		if (vec[start] > vec[end]) swap(vec[start], vec[end]);
	}
	//정렬하고자하는 배열의 길이 2이상인 경우 쪼개기
	else {
		int mid = (end + start) / 2;
		mergeSort(start, mid);
		mergeSort(mid + 1, end);
		merge(start, mid, mid + 1, end);
	}
	return;
}



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

	cin >> n;

	int input;
	for (int i = 0; i < n; ++i) {
		cin >> input;
		vec.push_back(input);
	}
    
	for (int i = 0; i < 1000; ++i) {
		vec.push_back(500 - i);
	}

	//병합정렬
	mergeSort(0, n - 1);

	for (int i = 0; i < n; ++i) {
		cout << vec[i] << "\n";
	}
	return 0;
}