📒 갈무리 - 안정 정렬과 불안정 정렬

📌 안정 정렬이란?(Stable Sort)

- 중복된 값을 입력 순서와 동일하게 정렬하는 정렬 알고리즘

- 예를 들어, [1, 3, 9, 3, 5]를 오름차순 정렬하면 [1, 3, 3, 5, 9]가 되는 것이다.

📌 안정 정렬 알고리즘

- 병합 정렬(Merge Sort)

- 버블 정렬(Bubble Sort)

- 삽입 정렬(Insertion Sort)

 

📌 불안정 정렬이란?(Unstable Sort)

- 중복된 값을 입력 순서와 상관없이 무작위로 정렬하는 정렬 알고리즘

- 예를 들어, [1, 3, 9, 3, 5]를 오름차순 정렬하면 [1, 3, 3, 5, 9]가 될 수도, [1, 3, 3, 5, 9]가 될 수도 있다.

- 당장 숫자들만 있을 때에는 의미가 없는 것처럼 보일 수 있지만 만약 저 숫자가 각기 다른 데이터들과 함께 묶여있었다면 어떨까?

- 그렇기에 경우에 따라 정렬 알고리즘을 잘 선택할 필요가 있을 것 같다.

📌 불안정 정렬 알고리즘

- 선택 정렬(Selection Sort)

- 힙 정렬(Heap Sort)

- 퀵 정렬(Quick Sort)

 

📌 in-place 알고리즘이란?

- 원소들의 개수에 비해 충분히 무시할 만한 저장 공간만을 더 사용하는 정렬 알고리즘

- 간단히 말하면, 추가적인 메모리 공간이 거의 들지 않는 정렬이다.(아예 안 드는 것은 아니다.)

📌 In-place 알고리즘

- 삽입 정렬(Insertion Sort)

- 선택 정렬(Selection Sort)

- 버블 정렬(Bubble Sort)

- 힙 정렬(Heap Sort)

- 퀵 정렬(Quick Sort) (Quick Sort는 경우에 따라 다르지만, 보편적으로는 In-place 알고리즘으로 본다.)

- 셸 정렬(Shell Sort)