시간복잡도 비교 (선택정렬/삽입정렬/버블정렬/병합정렬/퀵정렬/선형탐색/이진탐색)

 

각 정렬/탐색별로 간단한 알고리즘과 시간복잡도만 정리

 

1. 선택정렬 (Selection Sort)

제자리 정렬 알고리즘의 일종.

주어진 리스트 중 최소값을 index의 값과 교체 -> index는 단계를 거듭할 수록 1씩 증가.

버블정렬보다는 빠름

최선: O(N^2) / 최악: O(N^2)

 

2. 삽입정렬 (Insertion Sort)

모든 요소를 앞에서부터 차례대로 비교하여, 자신의 위치를 찾아서 삽입

구현은 쉽지만 효율이 떨어짐. 선택정렬이나 버블정렬보다는 빠름 

최선:O(N) / 최악: O(N^2)

 

3. 버블정렬 (Bubble Sort)

인접한 원소를 정렬시켜나감. 코드로 구현하기엔 쉽지만 느리다

최선: O(N) / 최악: O(N^2)

 

4. 병합정렬 (Merge Sort)

분할정복알고리즘의 일종. 부분리스트가 하나만 남을 때까지 n개의 부분리스트로 분할 후 정렬 반복

최선: O(NlogN) / 최악 : O(NlogN)

 

5. 퀵 정렬 (Quick Sort)

내장함수로 제공되는 경우가 많음. 분할 정복 알고리즘의 일종

리스트 가운데서 하나의 원소를 고른 후(피벗) -> 피벗을 기준으로 앞에는 피벗보다 작은 원소들 / 뒤에는 큰 원소들이 오도록 리스트를 분할

분할된 두 개의 리스트에 대해 각각 재귀적으로 같은 과정을 반복함.

최선:O(NlogN) / 최악: O(N^2)

 

6. 선형탐색 (Linear Search)

일반적으로 각 언어에서 제공되는 탐색방법. 차례대로 탐색

최선: O(1) / 최악 : O(N)

 

7. 이진탐색 (Binary Sear

각 단계별로 반으로 쪼개서 탐색

최선: O(1) / 최악: O(logN)