버블 정렬 (Bubble Sort)
특징
- 인접한 두 원소를 비교하며 정렬하는 알고리즘
- 큰 값이 뒤로 이동하면서 정렬이 이루어짐
장단점
- 장점:
- 구현이 간단하고 이해하기 쉬움
- 정렬되어 있는 배열에 대해서는 최선의 성능을 보임
- 단점:
- 시간 복잡도가 O(n^2)로 비효율적임
- 배열의 크기가 클 경우 성능이 저하됨
- 이미 정렬이 된 배열에 대해서도 교환 연산이 발생하여 비효율적임
시간 복잡도
- 평균 및 최악의 경우 시간 복잡도: O(n^2)
- 최선의 경우(이미 정렬된 배열): O(n)
선택 정렬 (Selection Sort)
특징
- 배열에서 가장 작은 값을 찾아 가장 앞으로 보내는 정렬 알고리즘
- 배열을 정렬된 부분과 정렬되지 않은 부분으로 나눠가며 정렬함
장단점
- 장점:
- 구현이 간단하고 이해하기 쉬움
- 교환 횟수가 버블 정렬과 비교해 적어 성능이 좋음
- 단점:
- 시간 복잡도가 O(n^2)로 비효율적임
- 배열의 크기가 클 경우 성능이 저하됨
- 이미 정렬이 된 배열에 대해서도 교환 연산이 발생하여 비효율적임
시간 복잡도
- 평균, 최악, 최선의 경우 시간 복잡도: O(n^2)
삽입 정렬 (Insertion Sort)
특징
- 배열을 정렬된 부분과 정렬되지 않은 부분으로 나눠가며 정렬하는 알고리즘
- 정렬되지 않은 부분의 원소를 정렬된 부분에서 올바른 위치에 삽입함
장단점
- 장점:
- 구현이 간단하고 이해하기 쉬움
- 이미 정렬된 부분에 대한 비교 연산이 없으므로 비교적 효율적임
- 단점:
- 시간 복잡도가 O(n^2)로 비효율적임
- 삽입되는 위치를 찾기 위해 비교 연산이 많이 발생함
시간 복잡도
- 평균, 최악, 최선의 경우 시간 복잡도: O(n^2)
퀵 정렬 (Quick Sort)
특징
- 분할 정복(divide and conquer) 방식을 사용하여 원소를 정렬하는 알고리즘
- 기준(pivot)을 기준으로 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 분할하여 정렬함
장단점
- 장점:
- 평균적으로 가장 빠른 정렬 알고리즘으로 알려져 있음
- 시간 복잡도가 평균적으로 O(nlogn)으로 효율적임
- 단점:
- 이미 정렬된 배열에 대해서는 최악의 경우 시간 복잡도가 O(n^2)으로 비효율적임
- pivot을 선택하는 방식에 따라 성능이 달라짐
시간 복잡도
- 평균 및 최악의 경우 시간 복잡도: O(nlogn)
병합 정렬 (Merge Sort)
특징
- 분할 정복(divide and conquer) 방식을 사용하여 리스트를 정렬하는 알고리즘
- 리스트를 반으로 나눈 뒤, 각각을 정렬한 후 병합하여 정렬된 최종 리스트를 생성함
장단점
- 장점:
- 시간 복잡도가 항상 O(nlogn)으로 효율적임
- 안정한 정렬 방식으로 원소의 순서를 보존함
- 단점:
- 재귀 호출을 사용하므로 메모리를 많이 사용함
- 정렬할 리스트의 크기가 커질수록 성능이 저하됨
시간 복잡도
- 평균, 최악, 최선의 경우 시간 복잡도: O(nlogn)
댓글