[알튜비튜] 01. 정렬

대표적인 정렬 알고리즘

∘ 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하는 식으로 작동한다는 거지?