# 정렬 알고리즘 선택 기준

### 1. 시간 복잡도 : 얼마나 빨리 작동되는가?

***

#### 🔷 느린 알고리즘 : O(n^2)

**◻️ 작은 데이터 세트나 거의 정렬된 데이터 : 버블 정렬, 삽입 정렬**

* 버블 정렬 : 정렬될때까지 순회하면서 2개씩 비교 후 순서 변경
* 삽입 정렬 : 맨 앞에 크기 순으로 정렬된 영역 하나씩 키우기

**◻️ 메모리가 부족한 환경 : 선택 정렬**

* 선택 정렬 : 최솟값 찾고 앞으로 보내는거 반복

#### 🔷 빠른 알고리즘 : O(n log n)

**◻️ 대부분의 일반적인 상황 : 퀵 정렬**

* 퀵 정렬 : 피벗 하나 고르고 왼쪽 오른쪽으로 보내버리는거 반복

**◻️ 안정성이 중요한 대규모 데이터 세트 : 병합 정렬**

* 병합 정렬 : 작게 쪼갠 다음 하나씩 합치는거 반복
* 안정성 : 동일한 키를 가진 요소들이 정렬 전의 순서를 유지하는 것
* 예를 들어, 학생들을 성적 순으로 정렬할 때, 동일한 성적을 가진 학생들은 원래의 순서를 유지해야 할 경우에 적합

**◻️ 추가 메모리 공간을 사용할 수 없는 대규모 데이터 세트 : 힙 정렬**

* 힙 정렬 : 최대/최소 힙 만들고 루트 노드 제거
* 힙 정렬은 입력 배열 자체를 힙 구조로 변환한 후 정렬을 수행하기 때문에, 추가적인 메모리 공간이 필요하지 않음

#### 🔷 매우 빠르지만, 제한적인 알고리즘 : O(n)

**◻️ 정수나 고정 길이 문자열 정렬 : 기수 정렬**

**◻️ 데이터의 범위가 제한적일 때 매우 효율적 : 계수 정렬**

**◻️ 버킷 정렬 : 데이터가 균등하게 분포된 경우에 적합 : 버킷 정렬**

### 2. 공간 복잡도 : 메모리 얼마나 쓰는가?

***

#### 🔷 추가 메모리 거의 사용 안 함 (In-place 알고리즘)

* 퀵 정렬(Quick Sort)
* 힙 정렬(Heap Sort)
* 삽입 정렬(Insertion Sort)
* 선택 정렬(Selection Sort)
* 버블 정렬(Bubble Sort)

#### 🔷 추가 메모리 사용함 (Not In-place 알고리즘)

* 병합 정렬(Merge Sort)
* 계수 정렬(Counting Sort)
* 기수 정렬(Radix Sort)

### 3. 데이터의 특성 : 어떤 데이터를 정렬하는가?

***

#### 🔷 거의 정렬된 데이터

* 삽입 정렬
* 버블 정렬

#### 🔷 작은 데이터

* 삽입 정렬
* 선택 정렬
* 버블 정렬

#### 🔷 큰 데이터

* 퀵 정렬 : 평균적으로 매우 빠르지만 최악의 경우 O(n^2)이 될 수 있음
* 병합 정렬 : 안정적이고 O(n log n) 성능을 보장하지만 추가 메모리가 필요함
* 힙 정렬 : 안정적인 O(n log n) 성능을 제공하고 추가 메모리가 필요하지 않음

#### 🔷 범위가 제한된 데이터

* 계수 정렬
* 기수 정렬
* 버킷 정렬

### 4. 안정성 (Stability)

***

#### 🔷 안정성이 있음 (동일한 키 값을 가지는 요소들의 상대적인 순서를 유지함)

* 병합 정렬(Merge Sort)
* 삽입 정렬(Insertion Sort)
* 버블 정렬(Bubble Sort)
* 계수 정렬(Counting Sort)

#### 🔷 안정성이 없음

* 퀵 정렬
* 힙 정렬


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lazyartisan.gitbook.io/note/main-page/algorithm/undefined/undefined-8.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.