2750번 수 정렬하기

문제 링크 : www.acmicpc.net/problem/2750

2750번: 수 정렬하기

 방법 1. 삽입정렬(insertion sort)

삽입 정렬 : 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는알고리즘.

  -> 장점 : 구현이 간단함, 같은 O(n^2)알고리즘에 비교하여 빠름, 안정적/in-place 알고리즘이다.

      단점 : 배열이 길어질 수록 효율이 떨어짐

내용 출처 : ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC

삽입 정렬 - 위키백과, 우리 모두의 백과사전

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

int main() {
	int T = 0;
	cin >> T;

	vector<int> list;
	
	while (T--) {
		int n = 0;
		cin >> n;
		if (list.size() == 0) list.push_back(n);
		else if (list.size() == 1) {
			if (list[0] > n) list.insert(list.begin(), n); 
			else list.push_back(n);
		}
		else {
			for (unsigned int i = 0; i < list.size(); i++) {
				if (list[i] >= n) {
					list.insert(list.begin() + i, n);
					break;
				}
				else if (list[i]<n && i==list.size()-1) {
					list.push_back(n);
					break;
				}
			}
		}
	}
	for (int i = 0; i < list.size(); i++) {
		cout << list[i] << "\n";
	}
	return 0;
}

(위의 코드)문제번호/정답여부/사용된 메모리와 시간/사용언어/코드길이

방법 2. 버블정렬(Bubble sort) = 거품정렬

  버블정렬 : 두 인접한 원소를 검사형 정렬하는 방법.(양 방향에서 진행하면 칵테일정렬)

    장점: 코드가 단순       단점 : 시간이 오래걸림(O(n^2))

내용 출처 : ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC

거품 정렬 - 위키백과, 우리 모두의 백과사전

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

int main() {
	int T = 0;
	cin >> T;

	vector<int> list;

	while (T--) {
		int n = 0;
		cin >> n;
		list.push_back(n);
		for (int i = 0; i < list.size(); i++) {
			for (int j = i; j < list.size(); j++) {
				if (list[j] < list[i]) {
					int temp = list[j];
					list[j] = list[i];
					list[i] = temp;
				}
			}
		}
	}

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

(위의 코드)문제번호/정답여부/사용된 메모리와 시간/사용언어/코드길이