[바킹독의 실전 알고리즘] 0x0E강 - 정렬 I

오젼·2024년 1월 4일

알고리즘

[바킹독의 실전 알고리즘]

목록 보기

12/13

강의

https://youtu.be/59fZkZO0Bo4?si=L7IS5zTnwv4BWlLV

설명

선택 정렬

$O(N^2)$

버블 정렬

$O(N^2)$

merge sort

재귀적으로 정렬하는 함수
$O(NlogN)$

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

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

얻어갈 것: a[aidx] < b[bidx] 말고 else if (a[aidx] <= b[bidx]) c[i] = a[aidx++]; 여야 stable sort 성질을 만족함. 두 개의 크기가 같을 때 a의 원소가 앞쪽에 들어가는 것.

quick sort

보통 $O(NlogN)$
최악의 경우 $O(N^2)$ --> 최대 단점~~~ 직접 구현할 땐 quick sort 피해야 하는 이유!
quick sort는 in-place sort. 추가 공간이 필요 없다!

$O(NlogN)$ 을 보장하기 위해 STL에선 introspective sort로 quick sort를 구현해 놓음. https://choiseokwon.tistory.com/209

merge sort vs quick sort

문제

https://github.com/encrypted-def/basic-algo-lecture/blob/master/workbook/0x0E.md

2750, 2751

완죤 간단한 정렬 문제. bubble sort, merge sort 연습해보기

10989

시간제한과 메모리제한을 살펴보면~~ 시간은 넉넉한데 메모리가 부족하다. 그럼 메모리를 줄일 방법을 생각해야 함.

입력받는 수의 범위가 10,000보다 작거나 같은 자연수이고 입력받는 수의 개수의 범위는 N(1 ≤ N ≤ 10,000,000)이기 때문에 int arr[10001]을 선언하고 입력받은 수를 인덱스로 가지는 배열값을 늘려가면서 저장해준다.

#include <iostream>
using namespace std;

int N, num;
int arr[10001];

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 0; i < N; ++i) {
		cin >> num;
		++arr[num];
	}
	for (int i = 1; i <= 10000; ++i) {
		while (arr[i]--) {
			cout << i << '\n';
		}
	}
}