정렬(Sort) 알고리즘

1. 비교 기반 정렬 (Comparision Sort)

두 요소를 비교하여 정렬 순서를 결정하는 알고리즘

✒️ 버블 정렬 (Bubble Sort)

서로 인접한 두 개의 값을 비교하는 방식으로 큰 값이 계속 뒤로 이동
구현이 간단하지만 매우 비효율적, 작은 데이터에만 적합
추가적인 메모리 공간을 사용 O(1)
안정 정렬 (Stable Sort)

1. 배열의 인접한 두 요소를 비교하여 순서가 잘못된 경우 교환
2. 한 바퀴 순회하면 가장 큰 값이 맨 뒤로 이동
3. 이 과정을 배열 길이만큼 반복

시간 복잡도

• 최선 : O(n) (거의 정렬된 경우)
• 평균 : O(n^2)
• 최악 : O(n^2)

✒️ 선택 정렬 (Selection Sort)

배열에서 가장 작은(큰) 값을 찾아 맨 앞 요소와 교환하는 방식
실행 속도가 일정하지만 비효율적
교환 횟수가 적어서 메모리 사용이 적음
추가적인 메모리 공간을 사용 O(1)
불안정 정렬(Unstable Sort)

1. 배열에서 최소값(최대값)을 찾기
2. 해당 값을 맨 앞 요소와 교환
3. 두 번째 요소부터 다시 위의 과정을 반복

시간 복잡도

• 최선 : O(n^2)
• 평균 : O(n^2)
• 최악 : O(n^2)

✒️ 삽입 정렬 (Insertion Sort)

배열을 앞부분 부터 정렬된 상태로 유지하면서 새로운 값을 적절한 위치에 삽입
데이터가 거의 정렬된 경우 매우 효율적
추가적인 메모리 공간을 사용 O(1)
안정 정렬 (Stable Sort)

1. 두 번째 요소부터 시작하여 이전 요소들과 비교
2. 적절한 위치를 찾아 삽입
3. 이 과정을 마지막 요소까지 반복

시간 복잡도

• 최선 : O(n) (거의 정렬된 경우)
• 평균 : O(n^2)
• 최악 : O(n^2)

✒️ 병합 정렬 (Merge Sort)

분할 정복 (Divide and Conquer) 방식을 이용하여 배열을 반으로 나눈 후 각각 정렬하고 병합하는 방식
추가적인 메모리 공간을 사용 O(n)
안정 정렬 (Stable Sort)

1. 배열을 더 이상 나눌 수 없을 때까지 2등분
2. 분할된 배열을 정렬하면서 병합

시간 복잡도

• 최선 : O(nlog n)
• 평균 : O(nlog n)
• 최악 : O(nlog n)

✒️ 퀵 정렬 (Quick Sort)

분할 정복 기법을 사용하여 피벗(pivot)을 기준으로 작은 값과 큰 값으로 나누어 정렬하는 방식
평균적으로 매우 빠름
추가적인 메모리 공간을 사용 O(log n)
불안정 정렬(Unstable Sort)

1. 배열에서 한 개의 요소를 피벗으로 선택
2. 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할
3. 분할된 배열을 재귀적으로 정렬

시간 복잡도

• 최선 : O(nlog n)
• 평균 : O(nlog n)
• 최악 : O(n^2) (피벗이 한쪽으로 치우친 경우)

✒️ 힙 정렬 (Heap Sort)

힙(Heap) 자료구조를 이용하여 최대/최소 값을 꺼내며 정렬하는 방식
추가적인 메모리 공간을 사용 O(1)
불안정 정렬(Unstable Sort)

1. 주어진 배열을 최대 힙(Max Heap) 또는 최소 힙(Min Heap)으로 변환
2. 힙에서 하나씩 요소를 꺼내 정렬

시간 복잡도

• 최선 : O(nlog n)
• 평균 : O(nlog n)
• 최악 : O(n^2) (피벗이 한쪽으로 치우친 경우)

2. 비교를 사용하지 않는 정렬 (Non-Comparison Sort)

데이터의 값을 직접 활용하여 정렬하는 알고리즘

✒️ 계수 정렬 (Counting Sort)

데이터의 빈도 수를 카운팅 하여 정렬하는 방식
매우 빠르지만 데이터 범위가 제한적일 때만 가능
추가적인 메모리 공간을 사용 O(k)
안정 정렬 (Stable Sort)

1. 데이터 범위의 크기만큼 카운트 배열을 생성
2. 각 데이터의 등장 횟수를 기록
3. 카운트 배열을 기반으로 정렬된 데이터를 생성

시간 복잡도

• 최선 : O(n+k) (k: 데이터 값의 범위)
• 평균 : O(n+k)
• 최악 : O(n+k)

✒️ 기수 정렬 (Radix Sort)

각 자리수를 기준으로 정렬을 수행하는 방식
매우 빠름, 숫자 정렬에 강함
추가적인 메모리 필요

1. 1의 자리부터 정렬 (기수 정렬의 보조 정렬로 계수 정렬을 사용)
2. 10의 자리 -> 100의 자리 순서로 정렬
3. 모든 자리수를 정렬하면 완료

시간 복잡도

• 최선 : O(nk) (k: 자리수 개수)
• 평균 : O(nk)
• 최악 : O(nk)

✒️ 버킷 정렬 (Bucket Sort)

데이터를 여러 개의 버킷에 나누어 담고 각 버킷을 정렬한 후 합치는 방식
데이터가 고르게 분포되어 있을 때 매우 효율적
추가적인 메모리 필요

1. 최대값과 최소값을 확인하여 범위를 결정
2. 적절한 개수의 버킷을 생성
3. 각 데이터를 해당하는 버킷에 분배
4. 각 버킷 내부를 정렬 (삽입정렬, 병합정렬 등을 사용)
5. 정렬된 버킷을 하나로 합침

시간 복잡도

• 최선 : O(n+k) (k: 버킷 개수)
• 평균 : O(n+k)
• 최악 : O(n+k)