[알고리즘]정렬 알고리즘 정리

매번 보는 지겨운 정렬 알고리즘

실제 개발에 있어서 라이브러리를 잘 사용하여 짜기만 하면되는데.... 라는 생각을 떠나

언젠가 자기만의 커스텀 정렬을 위하여 이번 기회에 정리 합니다.

---

목표

1, 정렬 알고리즘 종류와 방법을 이해

2. 정렬 알고리즘의 복잡도 이해

3. 고급정렬 알고리즘

용어

1. 레코드(record) : 정렬할 각 원소

2. 필드(field) : 레코드에 포함되어 있는 정보

3. 키 : 레코드간의 순서를 나타내는 자

4. 안전성(stability) : 상대적인 위치가 정렬후에도 유지가 될 것

비교에 의한 정렬

1. 선택정렬 O(N^2) 불안정

2. 버블정렬 O(N^2) 안정적

3. 삽입정렬 O(N^2) 안정적

4. 쉘정렬 O(N^3/2) 안정적

5. 히프정렬 O(NlogN) 불안정적

분포에 의한 정렬

1. 계수에 의한 정렬(Counting sort) O(N) 안정적 

애니메이션(http://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html)

2. 기수정렬(Radix sort) O(n) 안정적

애니메이션(https://www.cs.usfca.edu/~galles/visualization/RadixSort.html)