정렬 알고리즘

정렬 알고리즘 정리

1. 버블 정렬 (Bubble Sort)

인접한 두 데이터를 비교하면서, 정렬 순서에 맞지 않으면 서로 교환하는 방식의 정렬이다.
작은 값이나 큰 값이 한 단계씩 이동하는 모습이 거품이 올라오는 것 같아서 버블 정렬이라고 부른다.

동작 방식

오름차순 정렬 기준:

• 앞에서부터 인접한 두 값을 비교한다.
• 왼쪽 값이 더 크면 서로 교환한다.
• 한 번 끝까지 순회하면 가장 큰 값이 맨 뒤로 이동한다.
• 다음 순회에서는 맨 뒤의 정렬 완료 구간을 제외하고 반복한다.

즉,

• 1번째 순회: n - 1번 비교
• 2번째 순회: n - 2번 비교
• …
• 마지막 순회: 1번 비교

총 비교 횟수는 다음과 같다.

$(n-1)+(n-2)+\cdots +2+1=\frac{n(n-1)}{2}$

따라서 시간 복잡도는 O(n²) 이다.

데이터 이동

교환은 보통 임시 변수 하나를 사용하므로 대입이 3번 일어난다.

temp = arr[indexA];
arr[indexA] = arr[indexB];
arr[indexB] = temp;

따라서 최악의 경우 비교도 많이 하고 교환도 많이 해서 실제 실행 비용이 커진다.

특징

• 구현이 단순하다.
• 성능은 좋지 않은 편이다.
• 기본 구현은 이미 거의 정렬된 배열에도 비효율적이다.
• 다만, 한 번의 순회에서 교환이 한 번도 없으면 종료하는 최적화를 넣을 수 있다.

---

2. 선택 정렬 (Selection Sort)

정렬되지 않은 구간에서 최솟값을 찾아, 정렬해야 할 위치에 한 번에 가져다 놓는 방식의 정렬이다.

동작 방식

오름차순 정렬 기준:

• 0번 인덱스부터 끝까지 탐색해 가장 작은 값을 찾는다.
• 그 값을 0번 인덱스와 교환한다.
• 1번 인덱스부터 끝까지 탐색해 가장 작은 값을 찾는다.
• 그 값을 1번 인덱스와 교환한다.

이런 식으로 앞에서부터 자리를 확정해 나간다.

시간 복잡도

비교 횟수는 다음과 같다.

• 0번 자리를 정할 때: n - 1번 비교
• 1번 자리를 정할 때: n - 2번 비교
• …
• 마지막 전 자리: 1번 비교

총 비교 횟수는 버블 정렬과 마찬가지로 O(n²) 이다.

데이터 이동

선택 정렬은 비교 횟수는 많지만 교환 횟수는 적다.

• 매 단계마다 최솟값을 찾은 뒤 한 번만 교환하면 되므로
• 최대 교환 횟수는 n - 1번이다.

교환 1회당 대입 3번이 필요하다고 보면, 총 대입 횟수는 최악의 경우에도 대략 3(n - 1) 수준이다.

특징

• 비교 횟수는 많다.
• 교환 횟수는 버블 정렬보다 적다.
• 시간 복잡도는 여전히 O(n²) 이므로 큰 데이터에는 비효율적이다.

---

3. 삽입 정렬 (Insertion Sort)

배열을 정렬된 구간과 정렬되지 않은 구간으로 나눈 뒤, 정렬되지 않은 구간의 값을 하나씩 꺼내 정렬된 구간의 알맞은 위치에 삽입하는 방식이다.

동작 방식

오름차순 정렬 기준:

• 처음에는 첫 번째 원소만 정렬된 상태라고 본다.
• 그 다음 원소를 꺼내서, 앞의 정렬된 구간과 비교한다.
• 들어갈 위치를 찾을 때까지 큰 값들을 한 칸씩 뒤로 민다.
• 비어 있는 자리에 현재 값을 삽입한다.

예를 들어:

(2, 4, 5, 1, 3)

여기서 1을 삽입하려면:

• 5를 뒤로 밀고
• 4를 뒤로 밀고
• 2를 뒤로 밀고
• 맨 앞에 1을 넣는다.

시간 복잡도

최악의 경우, 매번 앞의 모든 원소와 비교하고 이동해야 한다.
예를 들어 내림차순 배열을 오름차순으로 정렬하면:

• 2번째 원소 삽입: 1번 비교
• 3번째 원소 삽입: 2번 비교
• …
• 마지막 원소 삽입: n - 1번 비교

따라서 최악의 시간 복잡도는 O(n²) 이다.

특징

• 최악의 경우는 O(n²) 이다.
• 하지만 이미 어느 정도 정렬된 데이터에서는 매우 빠르게 동작한다.
• 그래서 작은 구간 정렬이나, 거의 정렬된 데이터 처리에서 유리하다.

보충

삽입 정렬은 선택 정렬의 “개선판”이라고 보기보다는,
동작 방식이 다른 별개의 정렬이라고 보는 편이 더 정확하다.

---

4. 힙 정렬 (Heap Sort)

힙 자료구조의 특성을 이용한 정렬 방식이다.

힙은 보통 다음 성질을 가진다.

• 최대 힙: 부모 노드의 값이 자식 노드의 값보다 크거나 같다.
• 따라서 루트 노드에는 가장 큰 값이 위치한다.

이 성질을 이용하면 루트에서 가장 큰 값을 하나씩 꺼내며 정렬할 수 있다.

동작 방식

오름차순 정렬 기준:

• 배열을 최대 힙으로 만든다.
• 루트(가장 큰 값)를 맨 뒤 원소와 교환한다.
• 힙 크기를 1 줄인다.
• 다시 힙 성질을 맞춘다.
• 이를 반복한다.

시간 복잡도

힙 정렬은 보통 다음처럼 이해하면 된다.

1. 초기 힙 구성(Heapify): $O(n)$
2. 루트 제거 및 재정렬을 n - 1번 반복: 각 단계 $O(logn)$

따라서 전체 시간 복잡도는:

$O(nlogn)$

특징

• 시간 복잡도가 O(n log n) 이다.
• 추가 배열 없이 정렬 가능하다.
• 다만 실제 구현과 동작 원리는 버블/선택/삽입보다 어렵다.
• 일반적으로 안정 정렬은 아니다.

수정 포인트

“힙에 원소를 하나씩 넣고, 루트를 하나씩 빼며 정렬한다”라고 설명해도 큰 흐름은 맞지만,
배열 기반 힙 정렬은 보통 heapify를 통해 한 번에 힙을 만든다고 설명하는 편이 더 정확하다.

---

5. 병합 정렬 (Merge Sort)

병합 정렬은 분할 정복(Divide and Conquer) 을 기반으로 하는 정렬이다.

분할 정복이란?

큰 문제를 작은 문제로 나누고,
작은 문제를 해결한 뒤 그 결과를 합쳐서 전체 문제를 해결하는 방식이다.

병합 정렬에서는:

1. 배열을 절반으로 나눈다.
2. 원소가 1개가 될 때까지 계속 나눈다.
3. 다시 합치면서 정렬한다.

동작 방식

예를 들어 다음 배열이 있다고 하자.

{5, 2, 4, 1}

분할:

{5, 2, 4, 1} → {5, 2} {4, 1}
→ {5} {2} {4} {1}

병합:

• [5]와 [2]를 비교해서 [2, 5]
• [4]와 [1]를 비교해서 [1, 4]
• [2, 5]와 [1, 4]를 비교해서 [1, 2, 4, 5]

병합 방식

두 배열의 앞쪽부터 비교하면서 더 작은 값을 임시 배열에 넣는다.

예를 들어:

• arrA[indexA]
• arrB[indexB]

를 비교해서 더 작은 값을 결과 배열에 넣고,
그 값을 꺼낸 배열의 인덱스를 한 칸 증가시킨다.

한쪽 배열이 먼저 끝나면, 나머지 배열의 값들을 그대로 뒤에 붙인다.

시간 복잡도

병합 정렬은 매 단계에서 전체 원소를 한 번씩 확인하며 병합한다.
즉, 한 단계의 병합 비용은 O(n) 이다.

그리고 배열은 절반씩 나뉘므로 분할 깊이는 O(log n) 이다.

따라서 전체 시간 복잡도는:

$O(nlogn)$

비교 횟수 주의

길이가 각각 a, b인 두 정렬된 배열을 병합할 때
최대 비교 횟수는 a + b - 1번이다.

예를 들어 길이 4짜리 배열 두 개를 병합하면:

• 원소 수는 총 8개
• 최대 비교 횟수는 7번

데이터 이동

병합 과정에서는 보통:

1. 임시 배열에 정렬된 결과를 저장하고
2. 그 결과를 다시 원래 배열로 복사한다.

그래서 추가 메모리가 필요하고, 데이터 이동도 꽤 많은 편이다.

특징

• 시간 복잡도가 O(n log n) 으로 안정적이다.
• 데이터 분포와 관계없이 일정한 성능을 기대할 수 있다.
• 안정 정렬이다.
• • 배열로 병합 정렬할 때는 보통 병합 결과를 담아둘 임시 배열이 필요하다.
    • 그런데 연결리스트로 병합 정렬할 때는, 노드 자체를 새로 복사해서 옮기기보다 포인터 연결만 바꿔서 병합할 수 있다.
    • 추가 메모리 부담이 연결리스트에서는 훨씬 덜하다.

---

6. 퀵 정렬 (Quick Sort)

퀵 정렬은 분할 정복(Divide and Conquer) 을 기반으로 하는 정렬 방식이다.
병합 정렬처럼 배열을 나누어 해결하지만, 피벗(Pivot) 을 기준으로 데이터를 양쪽으로 분할한다는 점이 핵심이다.

---

핵심 개념

• 피벗(Pivot): 기준이 되는 값
• 피벗보다 작은 값은 왼쪽
• 피벗보다 큰 값은 오른쪽
• 이렇게 피벗을 기준으로 좌우를 나눈 뒤,
  각 구간에 대해 다시 같은 작업을 반복한다.

즉, 퀵 정렬은
”하나의 기준값을 정하고, 그 기준보다 작은 값과 큰 값을 양쪽으로 분리한 뒤, 각각을 다시 정렬하는 방식” 이다.

---

포인터 개념

배열의 구간을 다음처럼 둔다고 하자.

• left: 현재 정렬할 구간의 시작 인덱스
• right: 현재 정렬할 구간의 끝 인덱스
• pivot: 기준값
• low: 왼쪽에서 오른쪽으로 이동하는 포인터
• high: 오른쪽에서 왼쪽으로 이동하는 포인터

예를 들어 피벗을 맨 왼쪽 원소로 선택했다면:

• pivot = left
• low = left + 1
• high = right

처럼 시작하는 방식으로 구현할 수 있다.

---

동작 방식

피벗을 하나 정한 뒤, low와 high가 서로를 향해 이동한다.

1. low 이동

• low는 오른쪽으로 이동한다.
• 피벗보다 큰 값을 만날 때까지 이동한다.

2. high 이동

• high는 왼쪽으로 이동한다.
• 피벗보다 작은 값을 만날 때까지 이동한다.

3. 두 값 교환

• 아직 low <= high 라면
• 둘이 가리키는 값은 서로 자리가 잘못된 상태이므로 교환한다.

4. 교차 시 피벗 교환

• 계속 진행하다 보면 low와 high가 서로 교차하게 된다.
• 이 시점에서는 피벗과 high를 교환한다.

그러면 피벗은 최종적으로 자기 자리에 놓이게 된다.

즉,

• 피벗 왼쪽: 피벗보다 작은 값들
• 피벗 오른쪽: 피벗보다 큰 값들

이 되므로, 피벗 하나의 위치는 확정된다.

---

예시 흐름

[5, 3, 8, 4, 9, 1, 6]

피벗을 맨 왼쪽 5로 잡는다고 하자.

1. low는 오른쪽으로 가면서 5보다 큰 값 탐색
2. high는 왼쪽으로 가면서 5보다 작은 값 탐색
3. 잘못 놓인 두 값을 교환
4. 반복하다가 low와 high가 교차하면
5. 피벗 5와 high 위치의 값을 교환

그러면 5는 정렬이 완료된 위치에 놓이게 된다.

이후:

• 5의 왼쪽 구간
• 5의 오른쪽 구간

에 대해 같은 작업을 재귀적으로 반복한다.

---

종료 조건

퀵 정렬은 구간을 계속 나누며 진행한다.
재귀 호출은 보통 다음 조건에서 멈춘다.

if (left >= right)
return;

즉, 구간의 크기가 1 이하가 되면 더 이상 나눌 필요가 없다.

• 전체 퀵 정렬의 종료 조건은 left >= right
• 한 번의 분할 과정에서 포인터 종료 조건은 low > high

이렇게 구분해서 이해하는 것이 좋다.

---

시간 복잡도

평균

배열이 적절히 반씩 나뉘면:

• 한 번 분할할 때 전체를 한 번 훑으므로 O(n)
• 이런 분할이 log n 단계 정도 반복된다.

따라서 평균적인 시간 복잡도는:

$O(nlogn)$ 정도

최악

피벗이 계속 한쪽으로 치우치게 잡히면
예를 들어 이미 정렬된 배열에서 맨 앞 원소를 계속 피벗으로 잡으면:

• 한 번에 1개와 n-1개로만 나뉜다.
• 결국 비교가 n-1번 만큼 나뉘고 n번 비교한다.

$O(n^2)$ 이 된다.

---

특징

• 평균적으로 매우 빠르다.
• 추가 메모리 사용이 적은 편이다.
• 실제로 자주 사용되는 정렬 방식이다.
• 하지만 피벗 선택이 나쁘면 최악의 경우 O(n²) 이 된다.
• 일반적으로 안정 정렬은 아니다.

---

보충: 피벗 선택

피벗은 아무 값이나 잡을 수 있지만, 보통 성능을 위해 다양한 방법을 사용한다.

예시:

• 맨 앞 원소
• 맨 뒤 원소
• 가운데 원소
• 무작위 원소
• 세 값의 중앙값(Median-of-Three) 중간값을 선택하면 균등하게 나뉘기 때문에 성능이 제일 좋은 것 같다.

피벗을 잘 선택할수록 한쪽으로 치우친 분할을 줄일 수 있다.

7. 기수 정렬 (Radix Sort)

기수 정렬은 숫자의 자릿수를 기준으로 정렬하는 방식이다.
비교를 통해 순서를 정하는 정렬이 아니라, 각 자릿수의 값에 따라 데이터를 분배하고 다시 모으는 과정을 반복해서 정렬한다.

즉, 다른 정렬처럼
“두 값을 비교해서 누가 더 큰가?”를 따지는 것이 아니라,

• 1의 자리
• 10의 자리
• 100의 자리

처럼 자릿수별로 정렬을 여러 번 수행해서 전체 순서를 맞춘다.

---

핵심 아이디어

예를 들어 다음 숫자들이 있다고 하자.

170, 45, 75, 90, 802, 24, 2, 66

이 숫자들을 오름차순으로 정렬하고 싶다면:

1. 1의 자리 기준으로 정렬
2. 10의 자리 기준으로 정렬
3. 100의 자리 기준으로 정렬

처럼 가장 낮은 자리부터 차례대로 정렬해 나간다.

이 과정을 통해 최종적으로 전체 정렬이 완성된다.

---

동작 방식

기수 정렬은 보통 LSD 방식으로 많이 설명한다.

• LSD(Least Significant Digit): 가장 작은 자리수부터 정렬
  → 1의 자리 → 10의 자리 → 100의 자리 순서

예를 들어 숫자:

170, 45, 75, 90, 802, 24, 2, 66

1단계: 1의 자리 기준 정렬

• 170 → 0
• 45 → 5
• 75 → 5
• 90 → 0
• 802 → 2
• 24 → 4
• 2 → 2
• 66 → 6

이 값을 기준으로 분류하면:

0: 170, 90
2: 802, 2
4: 24
5: 45, 75
6: 66

모으면:

170, 90, 802, 2, 24, 45, 75, 66

2단계: 10의 자리 기준 정렬

이제 위 결과를 가지고 10의 자리를 기준으로 다시 정렬한다.

3단계: 100의 자리 기준 정렬

마찬가지로 100의 자리 기준으로 정렬한다.

이렇게 끝까지 진행하면 전체가 정렬된다.

---

왜 정렬이 되는가?

기수 정렬이 제대로 동작하려면
각 자릿수 정렬이 안정 정렬(Stable Sort) 이어야 한다.

안정 정렬이란:

• 값이 같은 경우
• 기존의 상대적 순서가 유지되는 정렬

을 말한다.

예를 들어 1의 자리 기준으로 정렬한 뒤
10의 자리 기준으로 다시 정렬할 때,
10의 자리가 같은 값들끼리는 이전 단계(1의 자리)의 순서가 유지되어야
전체 정렬이 올바르게 완성된다.

그래서 기수 정렬은 보통 각 자릿수 정렬에 카운팅 정렬을 함께 사용한다.

내가 이해가 안되었던 점 어차피 자리수별로 정렬할거면 가장 큰 자리로 하지 왜 작은 자리부터 하나? → 해당 자릿수 안에 정렬된 그룹들은 이전 자릿수 기준으로 정렬이 되어 있는 상태. 그래서 의미가 있다.

---

구현 방식

기수 정렬은 보통 각 자릿수별로 0 ~ 9까지의 버킷을 사용한다.

예를 들면:

• 0번 버킷: 현재 자리수가 0인 숫자들
• 1번 버킷: 현재 자리수가 1인 숫자들
• …
• 9번 버킷: 현재 자리수가 9인 숫자들

각 숫자를 현재 자릿수에 맞는 버킷에 넣고,
버킷 0부터 9까지 순서대로 다시 꺼내 배열에 채운다.

---

시간 복잡도

기수 정렬의 시간 복잡도는 보통 다음처럼 표현한다.

$O(d\times (n+k))$

여기서:

• n: 데이터 개수
• d: 자릿수 개수
• k: 각 자리에서 가능한 값의 범위

10진수 정수라면 k = 10 이다.

즉, 자릿수마다 한 번씩 전체 데이터를 순회하고,
버킷 정리도 함께 하므로 이런 형태가 된다.

정수 범위가 제한적일 때

k = 10 은 상수처럼 볼 수 있으므로,
보통 10진수 정수 정렬에서는:

O(dn)O(dn)O(dn)

처럼 이해해도 된다.

---

다른 정렬과의 차이

기수 정렬은 비교 기반 정렬이 아니다.

일반적인 비교 기반 정렬들:

• 버블 정렬
• 선택 정렬
• 삽입 정렬
• 힙 정렬
• 병합 정렬
• 퀵 정렬

이들은 결국 두 값을 비교해 순서를 정한다.

반면 기수 정렬은 비교 대신
자릿수 정보 자체를 이용해 분류한다.

그래서 특정 조건에서는 O(n log n) 보다 더 좋은 성능처럼 보일 수 있다.

---

특징

• 비교 기반 정렬이 아니다.
• 정수나 문자열처럼 자리 개념이 분명한 데이터에 잘 맞는다.
• 자릿수가 크지 않다면 매우 빠르게 동작할 수 있다.
• 각 단계에서 안정 정렬이 필요하다.
• 추가 버킷이나 임시 배열이 필요하므로 메모리를 더 사용한다.

---

장점

• 자릿수가 작은 정수 정렬에서는 매우 효율적일 수 있다.
• 비교 기반 정렬의 하한인 O(n log n)에 묶이지 않는다.
• 같은 길이의 숫자나 문자열 정렬에 강하다.

---

단점

• 모든 데이터에 다 잘 맞는 것은 아니다.
• 자릿수가 너무 크면 비효율적일 수 있다.
• 실수, 음수, 길이가 제각각인 복잡한 데이터에는 바로 적용하기 어렵다.
• 추가 메모리가 필요하다.

---

주의할 점

1. 안정 정렬이 필요하다

기수 정렬은 각 자릿수 정렬에서 기존 순서가 유지되어야 한다.
그래서 카운팅 정렬처럼 안정적인 정렬과 함께 쓰는 경우가 많다.

2. 자릿수 개수를 알아야 한다

가장 큰 수가 몇 자리인지 알아야
1의 자리, 10의 자리, 100의 자리… 를 어디까지 볼지 정할 수 있다.

예를 들어 최댓값이 802라면 100의 자리까지만 보면 된다.

3. 음수 처리는 별도 고려가 필요하다

기본 설명은 보통 0 이상의 정수를 기준으로 한다.
음수가 섞이면 별도의 처리 방식이 필요하다.

---

한 줄 정리

기수 정렬은
숫자의 각 자릿수를 기준으로 데이터를 여러 번 나누고 합치면서 정렬하는 방식이다.

---

추가

안정 정렬과 불안정 정렬

정렬 알고리즘은 같은 값을 가진 원소들의 순서가 유지되는지에 따라
안정 정렬과 불안정 정렬로 나눌 수 있다.

---

1. 안정 정렬 (Stable Sort)

값이 같은 원소들의 원래 상대적 순서를 유지하는 정렬

예시 데이터:

• (3, A)
• (1, B)
• (3, C)
• (2, D)

여기서 정렬 기준을 숫자로만 잡으면,
값이 3인 (3, A)와 (3, C)의 순서가 중요하다.

정렬 결과:

• (1, B)
• (2, D)
• (3, A)
• (3, C)

같은 값 3을 가진 원소들이 원래 순서(A → C) 를 그대로 유지했다.
이런 정렬이 안정 정렬이다.

---

2. 불안정 정렬 (Unstable Sort)

값이 같은 원소들의 상대적 순서가 바뀔 수 있는 정렬

같은 예시에서 정렬 후 결과가 다음처럼 될 수도 있다.

• (1, B)
• (2, D)
• (3, C)
• (3, A)

값은 올바르게 정렬되었지만,
같은 값 3의 순서가 A → C 에서 C → A 로 바뀌었다.

이런 정렬이 불안정 정렬이다.

---

4. 대표적인 예시

안정 정렬

• 버블 정렬
• 삽입 정렬
• 병합 정렬
• 기수 정렬

불안정 정렬

• 선택 정렬
• 퀵 정렬
• 힙 정렬

참고: 퀵 정렬은 일반적으로 불안정 정렬로 분류되지만,
구현 방식에 따라 안정적으로 만들 수도 있다.

---

정렬 관련 질문 정리

---

Bubble Sort와 Selection Sort의 차이점을 설명해 보세요

#### Bubble Sort 버블 정렬은 **인접한 두 원소를 비교하며 큰 값을 뒤로 보내는 방식**이다. 한 번의 반복이 끝날 때마다 가장 큰 값이 맨 뒤로 이동한다.

Selection Sort

선택 정렬은 매 단계마다 가장 작은 값(또는 가장 큰 값)을 찾아 알맞은 위치에 배치하는 방식이다.
즉, 현재 위치에 들어갈 값을 전체 범위에서 선택해서 교환한다.

차이점 정리

• 비교 방식

  • 버블 정렬: 인접한 원소끼리 계속 비교
  • 선택 정렬: 전체 범위에서 최소값 또는 최대값 선택

• 교환 횟수

  • 버블 정렬: 교환이 자주 일어날 수 있음
  • 선택 정렬: 각 단계마다 많아야 1번 교환하므로 교환 횟수는 적음

• 안정성

  • 버블 정렬: 안정 정렬
  • 선택 정렬: 불안정 정렬

• 시간 복잡도

  • 둘 다 평균/최악 O(N^2)

즉,
버블 정렬은 계속 밀어내는 방식,
선택 정렬은 하나를 골라 배치하는 방식이라고 볼 수 있다.

---

퀵 소트와 머지소트는 어떠한 차이점이 있나요?

퀵 정렬과 병합 정렬은 둘 다 **분할 정복** 기반 정렬이지만, 분할 방식과 성능 특성이 다르다.

퀵 소트

퀵 정렬은 피벗(pivot) 을 하나 정하고,
피벗보다 작은 값과 큰 값으로 나누는 방식이다.

머지소트

병합 정렬은 데이터를 반으로 계속 나눈 뒤,
정렬된 두 구간을 다시 합치면서 정렬한다.

차이점 정리

• 분할 방식

  • 퀵 소트: 피벗 기준으로 분할
  • 머지소트: 가운데 기준으로 반씩 분할

• 정렬이 일어나는 시점

  • 퀵 소트: 분할 과정에서 정렬 위치가 어느 정도 결정됨
  • 머지소트: 분할 후 병합하면서 정렬됨

• 시간 복잡도

  • 퀵 소트
    • 평균: O(N log N)
    • 최악: O(N^2)
  • 머지소트
    • 최선/평균/최악 모두: O(N log N)

• 추가 메모리

  • 퀵 소트: 보통 제자리 정렬에 가깝다
  • 머지소트: 병합용 임시 배열이 필요하여 추가 메모리 사용

• 안정성

  • 퀵 소트: 일반적으로 불안정 정렬
  • 머지소트: 안정 정렬

즉,
퀵 정렬은 평균적으로 빠르고 메모리를 적게 쓰지만 최악이 존재하고,
병합 정렬은 항상 일정한 성능을 보이지만 추가 메모리가 필요하다.

---

퀵 소트 성능 개선 기법으로는 어떤 게 있나요?

퀵 정렬은 피벗 선택이 좋지 않으면 성능이 크게 떨어질 수 있다. 그래서 이를 개선하기 위한 여러 기법이 있다.

대표적인 개선 기법

1) 좋은 피벗 선택

피벗이 한쪽으로 치우치면 분할이 불균형해져 최악의 경우 O(N^2)가 된다.
이를 줄이기 위해 다음과 같은 방법을 사용한다.

• 중간값 선택
• 랜덤 피벗 선택
• Median of Three
  • 첫 번째, 가운데, 마지막 값 중 중간값을 피벗으로 선택

이 방법들은 분할 균형을 개선하는 데 도움이 된다.

2) 작은 구간은 삽입 정렬로 전환

데이터가 아주 적은 구간에서는 퀵 정렬보다 삽입 정렬이 더 효율적일 수 있다.
그래서 원소 수가 작아지면 퀵 정렬 대신 삽입 정렬로 마무리하는 경우가 많다.

3) 꼬리 재귀 제거 / 반복문 변환

재귀 호출이 깊어지면 스택 사용량이 커질 수 있다.
이를 줄이기 위해 한쪽 구간만 재귀 호출하고, 나머지는 반복문으로 처리하는 방식이 사용된다.

4) 3-way partition

중복 값이 많은 경우,
작은 값 / 같은 값 / 큰 값 으로 3등분하는 방식이 더 효율적이다.
이 방법은 같은 값이 많을 때 성능 저하를 줄여준다.

---

이미 정렬된 데이터에 대해 가장 좋은 성능을 보이는 정렬 알고리즘은 무엇인가요?

대표적으로 **삽입 정렬(Insertion Sort)** 이다.

삽입 정렬은 현재 원소를 앞쪽의 정렬된 구간에 적절히 삽입하는 방식인데,
이미 정렬된 상태라면 비교만 조금 하고 거의 이동이 일어나지 않는다.

시간 복잡도

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

즉,
데이터가 이미 정렬되어 있거나 거의 정렬된 경우에는 삽입 정렬이 매우 효율적이다.

참고로 버블 정렬도 구현에 따라 교환이 한 번도 발생하지 않으면 조기 종료하여 O(N)이 가능하다.
하지만 일반적으로 이미 정렬된 데이터에 강한 대표적인 정렬로는 삽입 정렬을 더 많이 언급한다.

---