대표적인 정렬 알고리즘
∘ O(n^2) : Insertion sort, Selection sort, Bubble sort
∘ O(nlongn) : Quick sort, Merge sort, Heap sort
버블 정렬 (Bubble sort)
∘ 인접한 두 원소 비교
∘ (왼쪽 원소) > (오른쪽 원소) 면 swap
∘ 가장 큰 원소부터 오른쪽에 정렬됨
∘ 데이터가 하나씩 정렬되면서 비교에서 제외됨
* 2750번 : 수 정렬하기
여기서 시간 초과될지 안 될지는 어떻게 예상해?
합병 정렬 (Merge sort)
∘ 분할 정복(Divide and Conquer) 방식으로 설계된 알고리즘
∘ 하나의 배열을 정확히 반으로 나눔 (Divide)
∘ 나뉜 배열들을 정렬 (Conquer)
∘ 다시 하나의 배열로 합치기 (Merge)
분할 정복
∘ 한 번에 해결할 수 없는 문제를 작은 문제로 분할하여 해결하는 알고리즘
∘ 주로 재귀 함수로 구현
∘ 크게 3단계로 이루어짐
1. Divide : 문제 분할
2. Conquer : 쪼개진 작은 문제 해결
3. Combine : 해결된 작은 문제들을 다시 합침
합병 정렬은 두 그룹으로 나눈 다음에 지들끼리 정렬하고 그 다음에 정렬된 거에서 각각의 첫 번째꺼 비교해서 넣고 그렇게 앞에 있는 것부터 비교하면서 넣어서 끝까지 넣는 것 같
log n 예시들 좀 봐봐
정렬
- 정렬 알고리즘은 종류가 많은데 다 구현할 필요 없고 그냥 sort 함수 쓰면 됨. sort 함수의 오름차순, 내림차순, 그 외의 정렬들은 comp 정의로 하면 됨.
sort는 comp가 false를 반환해야 swap됨. -> 그니까... comp가 함수 같은 거지? 정렬하려는 규칙에 맞는 거를 comp에 입력해두면 그거에 맞지 않는 거를 swap하는 식으로 작동한다는 거지?