[알고리즘] 8. 정렬 알고리즘 (2)

1. 쉘 정렬 (Shell Sort)

• Donald L. Shell이 제안한 삽입 정렬을 보완한 알고리즘

• 삽입 정렬의 문제점: 삽입될 위치가 멀리 떨어진 경우 많은 이동이 필요

• 일정한 간격(gap)만큼 떨어진 데이터들을 부분 리스트로 만들어 정렬하는 방식

• 큰 간격에서 시작해 점점 줄여가며 정렬 수행

• 최종적으로 간격을 1로 설정하여 삽입 정렬 진행

 

특징:

• 삽입 정렬보다 빠르게 데이터의 이동 가능

• 간격이 줄어들수록 부분 리스트의 크기가 증가하지만 데이터가 점진적으로 정렬됨

• 삽입 정렬이 정렬된 데이터에 유리한 점을 활용한 방식

 

간격 설정:

• 데이터 개수의 절반을 첫 번째 간격으로 설정하고 반복적으로 절반으로 감소

• 비교 횟수는 간격에 의해 결정

 

시간 복잡도:

• 최악: O(n^2)

• 평균: O(n^(1.5))

• 삽입 정렬(O(n^2))보다 개선된 성능을 가짐

 

 

2. 병합 정렬 (Merge Sort)

• 데이터를 동일한 크기의 부분 리스트로 분할 후 정렬하여 병합하는 방식

• 분할 정복 알고리즘 적용

• 재귀적으로 리스트를 나누고 정렬된 리스트를 병합

 

효율성:

• 평균 및 최악의 경우 모두 O(n log n)의 성능

• 추가 메모리 공간이 필요하지만 안정적인 성능 제공

• 데이터 이동 횟수가 많지만 입력 데이터 상태와 무관하게 일정한 성능 유지

 

 

3. 퀵 정렬 (Quick Sort)

• 피벗(pivot)을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 정렬하는 방식

• 분할 정복 알고리즘 활용

 

피벗 선택 방법:

• 첫 번째 데이터, 마지막 데이터, 중간 데이터 중 하나 선택

• 특정 수식을 활용해 피벗 설정 가능

 

효율성:

• 평균: O(n log n)

• 최악: O(n^2) (피벗 선택이 비효율적인 경우)

• 정렬 전 데이터의 상태에 따라 성능이 달라질 수 있음

• 평균적으로 매우 빠른 수행 속도를 가져 널리 사용됨

• 데이터 이동 연산이 비교적 적어 효율성이 높음

• 대량의 데이터 정렬 시 매우 유용

---

이 내용은 휴넷사회복지평생교육원의 알고리즘 강의를 듣고 정리한 것입니다.