230313

1. 정렬

정렬은 핵심 항목의 대소관계(일정한 기준)에 따라 데이터 집합을 일정한 순서로 나열하는 작업을 말한다.

• 정렬을 진행하면 검색을 더 쉽게 할 수 있다.
• 값이 작은 데이터를 앞쪽에 놓으면 오름차순, 반대로 놓으면 내림차순 정렬
• 정렬 기반 알고리즘으로 "이분탐색", "다익스트라", "힙" 등이 있다.

버블 정렬

이웃한 두 요소의 대소 관계를 비교하여 교환을 반복하는 알고리즘, 기본적으로 시간복잡도는 O(N^2)이다.

선택 정렬

최소값 인덱스를 찾아 현재 위치값과 교환을 진행하는 알고리즘, 기본적으로 시간복잡도는 O(N^2)이다.

삽입 정렬

선택한 요소 앞쪽에 알맞은 위치에 삽입하는 과정을 반복하는 알고리즘, 최선의 경우 시간복잡도는 O(N)이다.

• 삽입값을 따로 빼놓은 다음 내부 반복문을 진행한다.

퀵 정렬

기준 값(pivot)을 기준으로 작은 값과 큰 값으로 나누는 작업을 반복하는 알고리즘, 보통 재귀 호출을 이용, 최악의 경우 O(N^2) 보통 O(NlogN)

※ 재귀를 다룰때는 종료조건을 꼭 잊지 말것!

병합 정렬 (분할 정복)

배열을 분할하고 분할한 배열을 정복하며 정렬하는 알고리즘, 최악의 경우 O(Nlog2N)를 무조건 보장한다.