Sort

Java 정렬 알고리즘

1. 알고리즘 한눈에 보기

정렬 방식	핵심 메커니즘	최선 복잡도	최악 복잡도	특징
선택 (Selection)	최댓값을 찾아 맨 뒤 데이터와 교환	O(n^2)	O(n^2)	정렬 상태와 상관없이 항상 전체 비교 발생
버블 (Bubble)	인접한 두 값을 비교하며 큰 값을 뒤로 이동	O(n^2)	O(n^2)	매 턴마다 가장 큰 값이 맨 뒤에 고정됨
삽입 (Insertion)	데이터를 앞쪽의 정렬된 제자리에 삽입	O(n)	O(n^2)	뒤에서부터 역방향 탐색 및 시프팅이 효율적
병합 (Merge)	분할 정복을 통해 배열을 쪼갠 후 합치며 정렬	O(n log n)	O(n log n)	데이터 상태와 무관하게 항상 일정한 성능 보장 (단, 임시 배열 공간 필요)
퀵 (Quick)	피벗 기준으로 작은 값/큰 값을 양쪽으로 분할 후 재귀 정렬	O(n log n)	O(n^2)	추가 메모리 없이 제자리(in-place) 정렬, 평균적으로 가장 빠름 (피벗 선택이 성능을 좌우)
힙 (Heap)	배열을 최대 힙으로 만든 뒤 루트(최댓값)를 맨 뒤로 보내며 정렬	O(n log n)	O(n log n)	추가 메모리 없이 제자리(in-place) 정렬, 입력 상태와 무관하게 항상 O(n log n) 보장 (불안정 정렬)
계수 (Counting)	값의 등장 횟수를 세고 누적 합으로 위치를 계산해 배치	O(n + k)	O(n + k)	비교 없이 정렬하는 선형 시간 알고리즘 (값이 0~k 정수여야 함, k가 크면 비실용적, 안정 정렬)
기수 (Radix)	낮은 자리수부터 각 자리를 기준으로 안정 정렬을 반복	O(d(n + k))	O(d(n + k))	비교 없이 자리 단위로 정렬 (d=자릿수, k=진법 범위), 계수 정렬을 자리마다 반복, 안정 정렬

---

2. 알고리즘별 핵심 포인트

선택 정렬

• 정렬되지 않은 영역에서 최댓값의 인덱스를 기억했다가 맨 뒤와 스왑(Swap)합니다.

버블 정렬

• 인접 원소끼리 계속 자리를 바꾸면서 큰 원소를 거품처럼 뒤로 밀어냅니다.

삽입 정렬

• 앞에서부터 탐색하면 뒤쪽 데이터를 매번 밀어야 하므로, 뒤에서부터 앞으로 탐색하며 공간을 한 칸씩 확보(Shifting)한 뒤 끼워 넣습니다.
• 이미 정렬된 상태(최선의 경우)에는 직전 값과 한 번만 비교하므로 O(n)이라는 최고의 효율을 냅니다.

병합 정렬

• 분할 정복(Divide and Conquer): 문제를 더 이상 쪼갤 수 없을 때까지 반으로 나눈 후(mergeSort), 쪼개진 원소들을 정렬하며 다시 하나로 합칩니다(merge).
• 안정 정렬(Stable Sort): 동일한 값을 가진 원소들의 상대적인 순서가 정렬 후에도 그대로 유지되는 안전성을 가집니다.
• 메모리 최적화: merge 단계에서 매번 임시 배열(tmp)을 생성하면 불필요한 메모리 할당/해제가 반복되므로, 최초 호출 시 배열을 딱 한 번만 생성하여 매개변수로 공유하는 구조가 가장 효율적입니다.

퀵 정렬

• 분할 정복(Divide and Conquer): 기준값인 피벗(pivot) 을 하나 정해, 피벗보다 작은 값은 왼쪽 / 큰 값은 오른쪽으로 모으는 분할(partition) 을 거친 뒤, 양쪽 영역을 각각 재귀적으로 정렬합니다. 분할이 끝나면 피벗은 항상 자신의 최종 위치에 놓입니다.
• 제자리 정렬(In-place): 병합 정렬과 달리 별도의 임시 배열 없이 스왑(Swap)만으로 정렬하므로 추가 메모리 부담이 거의 없습니다.
• 피벗 선택이 성능을 좌우:
  • 피벗을 항상 맨 끝 원소로 고정하면, 이미 정렬된 입력에서 한쪽으로만 쪼개져 최악 O(n^2) 가 됩니다.
  • 랜덤 피벗(partitionRandom) 으로 고르면 특정 입력에 치우치지 않아, 어떤 입력에서도 평균 O(n log n) 성능을 안정적으로 기대할 수 있습니다.
• 불안정 정렬(Unstable Sort): 분할 과정에서 멀리 떨어진 원소끼리 교환되므로, 동일한 값의 상대적 순서가 보장되지 않습니다. (병합 정렬과의 차이점)

힙 정렬

• 동작 원리: 배열을 최대 힙(Max Heap) 으로 만든 뒤(build heap), 루트(최댓값)를 배열의 맨 뒤와 교환(Swap) 하고 힙 크기를 하나 줄입니다. 줄어든 힙을 siftDown으로 다시 정리하는 과정을 반복하면, 큰 값이 뒤부터 쌓여 오름차순으로 정렬됩니다.
• 제자리 정렬(In-place): 별도의 배열에 복사하지 않고 입력 배열 자체를 힙으로 취급하여 스왑만으로 정렬하므로 추가 메모리가 O(1)입니다. (배열을 왼쪽=힙 구역 / 오른쪽=정렬 완료 구역으로 나눠 경계를 옮김)
• 항상 O(n log n) 보장: build heap은 O(n), 이후 n개의 루트를 각각 O(log n)에 빼내므로 전체는 O(n log n). 퀵 정렬과 달리 입력 상태에 따른 최악 O(n^2)가 없습니다.
• 구현 시 핵심: siftDown이 힙 범위(size)를 알아야 확정된 뒤쪽을 제외할 수 있습니다. 순서는 스왑 → 힙 크기 감소 → siftDown이어야 하며, 크기를 줄이기 전에 siftDown하면 방금 확정한 최댓값이 다시 올라옵니다.
• 불안정 정렬(Unstable Sort): 힙 구성 과정에서 멀리 떨어진 원소끼리 교환되므로, 동일한 값의 상대적 순서가 보장되지 않습니다.

계수 정렬(Counting Sort)

• 동작 원리: 값을 서로 비교하지 않고, 값 자체를 배열의 인덱스로 사용합니다. 길이 k+1인 count 배열에 각 값의 등장 횟수를 센 뒤, 이를 누적 합(count[i] += count[i-1])으로 바꿔 "값 i가 들어갈 위치"를 계산하고, 그 위치에 원소를 배치합니다.
• 비교 정렬의 하한을 우회: 비교 기반 정렬은 최선에도 O(n log n)이지만, 계수 정렬은 값의 범위 k를 안다는 사전 지식을 이용해 비교 없이 O(n + k) 에 정렬합니다. k = O(n)이면 사실상 선형 시간 O(n) 입니다.
• 안정 정렬(Stable Sort): 배치 단계를 뒤에서부터(i = n-1 ... 0) 순회하는 것이 안정성의 핵심입니다. 같은 값끼리 입력 순서가 그대로 유지되므로, (이름, 점수)처럼 키에 딸린 레코드 전체를 묶음 단위로 옮기는 정렬에 활용됩니다.
• 구현 시 핵심: 순서는 개수 세기 → 누적 합 → 뒤에서부터 배치입니다. 배치할 때 count[x]를 먼저 1 감소시키고 그 값을 0-based 인덱스로 사용합니다. 원본을 읽으며 결과를 써야 하므로 별도의 output 배열이 필요합니다. (count 배열 O(k) + output 배열 O(n))
• 한계: 값이 정수(또는 이산 범위)여야 하고, k가 매우 크면 count 배열이 커져 시간·공간 모두 비실용적입니다.

기수 정렬(Radix Sort)

• 동작 원리: 수 전체를 한 번에 비교하지 않고 자리(digit) 단위로 정렬합니다. 가장 낮은 자리(1의 자리)부터 시작해 한 자리씩 위로 올라가며(exp = 1, 10, 100 ...) 각 자리를 기준으로 정렬을 반복하면, 마지막 자리 정렬이 끝났을 때 전체가 정렬됩니다. (LSD 방식)
• 안정 정렬이 전제 조건: 각 자리를 정렬할 때 반드시 안정 정렬(계수 정렬) 을 써야 합니다. 상위 자리를 정렬하는 시점에 하위 자리는 이미 정렬돼 있는데, 안정 정렬이라야 상위 자리 값이 같은 원소들 사이에서 하위 자리 순서가 보존되어 정렬 결과가 누적됩니다. 불안정하면 이전 단계 결과가 무너집니다.
• 비교 정렬의 하한을 우회: 자리 하나를 계수 정렬로 처리하는 비용이 O(n + k)이고 이를 자릿수 d번 반복하므로 전체는 O(d(n + k)) 입니다. d와 k가 작은 상수면 사실상 선형 시간 O(n) 에 가깝습니다. (k = 진법, 10진수면 10)
• 구현 시 핵심: 현재 자리 숫자는 (arr[i] / exp) % 10으로 뽑습니다. exp로 나눠 보고 싶은 자리를 1의 자리로 내린 뒤 % 10으로 그 자리만 추출하는 방식이라, 자릿수가 짧은 수는 상위 자리가 자동으로 0으로 처리됩니다. 종료 조건은 최댓값 기준 max / exp > 0으로, 최대 자릿수를 넘어가면 반복이 끝납니다.
• 한계: 자리 개념이 명확한 비음수 정수(또는 고정 길이 데이터) 에 적합합니다. 음수가 섞이면 자릿값이 음수가 되어 그대로는 처리할 수 없고(양수/음수 분리 등 별도 처리 필요), 진법 k가 크면 메모리 부담이 커집니다. 제자리 정렬이 아니라 output 배열이 필요합니다.