BOJ-2750 | 수 정렬하기 1~3 c++

✏️ 2750-수 정렬하기 1
✏️ 2751-수 정렬하기 2
✏️ 10989-수 정렬하기 3
🌊 GitHub @xaesu, Study-Algorithm

접근

✔️ 삽입정렬 + 퀵정렬 + 카운팅정렬

	삽입 정렬	퀵 정렬	카운팅 정렬
시간 복잡도	평균 O(N^2) 최소 O(N)	평균 O(N log N) 최악 O(N^2)	O(N + K)
공간 복잡도	O(1) 제자리 정렬	O(log N) 재귀 호출 스택	O(N + K) 추가 배열 필요
적용 대상	작은 데이터셋 거의 정렬된 배열	모든 타입의 비교 가능한 데이터	정수 범위 데이터
장점	구현이 쉬움 거의 정렬된 데이터에 적합	일반적으로 빠름 제자리 정렬 가능	정수 범위가 작을 때 매우 효율적
단점	대규모 데이터셋에서 비효율 O(N^2)	최악의 경우 O(N^2)	숫자의 범위가 크면 비효율적

ChatGPT 참고

풀이

// 삽입 정렬 (2750)

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

int main()
{
	int N;
	cin >> N;

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

	for (int i = 1; i < N; i++) {
		int temp = arr[i];
		int j = i - 1;

		while (j >= 0 && temp < arr[j]) {
			arr[j + 1] = arr[j];
			j--;
		}
		arr[j + 1] = temp;
	}

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

// 퀵 정렬 알고리즘 내재 함수 (2751)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int N;
    cin >> N;

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

    // 퀵 정렬 기반 정렬 함수 <algorithm>
    sort(arr.begin(), arr.end());

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

// 카운팅 정렬

#include <iostream>
#include <vector>

using namespace std;

void countingSort(vector<int>& arr, int max);

int main()
{
    int N,input;
    cin >> N;

    // 입력 받은 수의 갯수를 count 배열에 저장
    vector<int> count(10001, 0);
    for (int i = 0; i < N; i++) {
        cin >> input;
        count[input]++;
    }

    // count 배열을 순차적으로 순회하면서 숫자 출력
    for (int i = 1; i <= 10000; i++) {
        while (count[i] > 0) {
            cout << i << '\n';
            count[i]--;
        }
    }
}