Sorting(정렬)

리스트에 저장된 값들을 크기 순서에 따라 재배열하는 문제

• 가능한 비교 횟수와 자리바꿈을 최소화 하는 것이 목표
• 매우 기본적이고 중요한 알고리즘 문제 중 하나 

---

단순 분류

• 기본 정렬 알고리즘: 느리지만 단순한 정렬 알고리즘 - insertion, selection, bubble정렬 알고리즘
• 빠른 알고리즘: 빠르지만 복잡할 수도 있는 정렬 알고리즘 - quick, heap, merge정렬 알고리즘
• 특별한 상황에 맞는 정렬 알고리즘 - count, radix, bucket정렬 알고리즘

---

정렬 알고리즘의 성질

1. stable & unstable

    - stable: 크기가 같은 숫자인 경우, 원래 입력 순서를 정렬 후에도 유지하는 알고리즘

출처: 위키피디아

2. in-place & not-in-place

    - in-place: 상수 개의 추가 변수(메모리)만 사용한 정렬 알고리즘. 즉 O(1)크기의 메모리 추가 사용

    - nor-in-place: O(n)이상의 크기 메모리를 추가 사용

 

 

---

출처

https://www.youtube.com/playlist?list=PLsMufJgu5932XYejsOwcUDJ2F75f56nrl 

https://en.wikipedia.org/wiki/Sorting_algorithm