[정렬] 고급 정렬 알고리즘(병합/퀵/힙/셀)

병합 정렬 (Merge Sort)

• 병합 정렬은 분할 정복 방법을 사용하는 정렬 방법

작동 원리:

• 배열을 반으로 나눕니다.
• 각 부분을 재귀적으로 정렬합니다.
• 정렬된 두 부분을 병합하여 완전한 정렬된 배열을 만듭니다.

시간 복잡도:

• 최선, 평균, 최악 모두 O(nlogn)

공간 복잡도:

• O(n) (추가 배열을 사용하기 때문)

약점:

• 추가 메모리가 필요합니다.

자주 사용되는 클래스나 컬렉션:

• 배열(int[], Integer[], String[] 등), ArrayList, LinkedList

 

 

 

퀵 정렬 (Quick Sort)

• 퀵 정렬도 분할 정복 전략을 사용하지만, 병합 정렬과는 다르게 작동

작동 원리:

• 피벗(pivot) 요소를 선택합니다.
• 피벗을 기준으로 배열을 두 부분으로 나눕니다: 피벗보다 작은 요소와 피벗보다 큰 요소.
• 이 과정을 재귀적으로 반복합니다.

시간 복잡도:

• 평균: O(nlogn)
• 최악: O(n2) (피벗 선택이 좋지 않을 경우)

공간 복잡도:

• O(logn) (재귀 호출로 인한 스택 공간)

약점:

• 최악의 경우 시간 복잡도가 )O(n2)이 될 수 있습니다.

자주 사용되는 클래스나 컬렉션:

• 배열, ArrayList

 

 

 

힙 정렬 (Heap Sort)

• 힙 정렬은 이진 힙(binary heap) 자료구조를 사용하여 정렬을 수행

작동 원리:

• 배열 요소를 최대 힙(max heap)으로 구성합니다.
• 힙의 루트(최대 값)를 배열의 맨 끝과 교환합니다.
• 힙의 크기를 줄이고, 힙 속성을 복구합니다.
• 위 과정을 반복합니다.

시간 복잡도:

• 평균 및 최악: O(nlogn)

공간 복잡도:

• O(1) (제자리 정렬)

약점:

• 안정성이 없고, 퀵 정렬이나 병합 정렬에 비해 상대적으로 느릴 수 있습니다.

자주 사용되는 클래스나 컬렉션:

• 배열, PriorityQueue

 

 

 

셸 정렬 (Shell Sort)

• 셸 정렬은 삽입 정렬의 변형으로, 일정한 간격으로 떨어진 요소들을 정렬하는 방식

작동 원리:

• 간격을 점점 줄여가며, 각 간격에 있는 요소들에 대해 삽입 정렬을 수행합니다.
• 마지막 단계에서는 일반 삽입 정렬을 수행합니다.

시간 복잡도:

• 평균: O(n(logn)2) 또는O(n1.5), 간격에 따라 달라짐
• 최악: 간격에 따라 다름, 일반적으로 O(n2)

공간 복잡도:

• O(1) (제자리 정렬)

약점:

• 최악의 경우 성능이 매우 떨어질 수 있습니다.

자주 사용되는 클래스나 컬렉션:

• 배열, ArrayList

.

 

 

참고자료 : 「쉽게 배우는 자료구조 with 자바」