| 작성자 | 장원준 |
| 일 시 | 2024. 10. 01 (화) 18:00 ~ 21:00 |
| 장 소 | 복지관 b128-1호 |
| 참가자 명단 | 임혜진, 이재영, 성창민, 김명원, 장원준 |
| 사 진 |  |
오늘은 알고리즘 강의 시간에 배우는 merge sort 와 Quick sort 에 대해서 공부를 했다.
먼저
Merge sort
Merge Sort는 분할 정복(Divide and Conquer) 알고리즘의 대표적인 예시입니다. 리스트를 더 작은 부분으로 분할한 후, 각 부분을 정렬하고, 마지막에 다시 합병하여 최종 정렬된 리스트를 얻는 방식으로 동작합니다. Merge Sort의 시간 복잡도는 항상 O(nlogn)O(n \log n)입니다.
Merge Sort의 단계
- 분할 (Divide): 리스트를 두 개의 하위 리스트로 나눕니다. 더 이상 분할할 수 없을 때까지(즉, 리스트의 길이가 1이 될 때까지) 계속해서 나누어 줍니다.
- 정복 (Conquer): 하위 리스트가 모두 정렬될 때까지 재귀적으로 각 하위 리스트를 정렬합니다.
- 병합 (Merge): 이제 정렬된 두 개의 하위 리스트를 병합하여 다시 하나의 정렬된 리스트로 만듭니다.
Merge Sort의 장점
- 안정적인 정렬: 동일한 값이 있는 경우, 그들의 순서는 변하지 않음.
- 일관된 시간 복잡도: 최악, 최선, 평균의 시간 복잡도가 모두 O(nlogn), O(n \log n),
Merge Sort의 단점
- 추가적인 메모리가 필요: 병합 단계에서 추가적인 배열을 사용하기 때문에 공간 복잡도가 O(n)입니다.
이처럼 Merge Sort는 재귀적으로 분할하고 병합하는 방식으로 안정적인 정렬을 수행합니다.
Quick sort
Quicksort는 분할 정복(Divide and Conquer) 알고리즘 중 하나로, 평균적으로 매우 빠른 정렬 성능을 보입니다. 리스트를 작은 하위 리스트로 나눈 뒤, 각각을 재귀적으로 정렬하며, 병합하지 않고 바로 정렬된 결과를 얻습니다.
Quicksort의 단계
- 기준 값 선택 (Pivot Selection): 리스트에서 하나의 요소를 선택하여 피벗(pivot)으로 설정합니다. 이 피벗을 기준으로 리스트를 두 개의 하위 리스트로 분할합니다.
- 분할 (Partition): 피벗보다 작은 값들은 왼쪽에, 큰 값들은 오른쪽에 배치합니다.
- 정렬 (Sort): 분할된 두 개의 하위 리스트에 대해 다시 퀵소트를 재귀적으로 적용하여 정렬합니다.
Quicksort의 장점
- 빠른 평균 성능: 평균적으로 시간 복잡도가 O(nlogn)O(n \log n)로 매우 빠릅니다.
- 공간 효율성: 추가 메모리를 많이 사용하지 않으며, 제자리(in-place)에서 정렬이 가능합니다.
Quicksort의 단점
- 최악의 경우 시간 복잡도: 피벗을 비효율적으로 선택할 경우, O(n2)O(n^2)의 성능이 나올 수 있습니다. 특히, 이미 정렬된 배열에 대해 비효율적인 피벗을 선택하면 이런 상황이 발생할 수 있습니다.
- 불안정한 정렬: 동일한 값을 가진 요소들의 순서가 보장되지 않음.
시간 복잡도
- 평균 시간 복잡도: O(nlogn)O(n \log n)
- 최악 시간 복잡도: O(n2)O(n^2) (비효율적인 피벗 선택 시)
이처럼 Quicksort는 매우 빠르고 공간 효율적인 정렬 알고리즘이지만, 피벗 선택이 성능에 크게 영향을 미칩니다.
Merge sort 와 Quick sort 를 공부해보며 merge sort 는 시간 복잡도가 일정하고 정렬이 안정적인 장점이 있지만 공간복잡도가 큰 단점이 있었고, Quick sort는 시간복잡도가 최악의 경우에 매우 크게 나오는 단점이 있지만 공간을 효율적으로 쓸 수 있는 장점이 있었습니다. 이를 통해 데이터를 먼저 분석한 뒤에 더 효율적인 정렬 알고리즘을 택한다면 좋을 것 같다고 느꼈습니다.