정렬 알고리즘(선택Select/ 삽입Insertion/ 퀵Quick/ 계수Count)

---

선택 정렬(Selection Sort), 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾼다.

삽입 정렬(Insertion Sort), 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입한다.

(특정한 데이터가 적절한 위치에 들어가기 전, 그 앞까지의 데이터는 이미 정렬되었다고 가정하므로,

삽입 정렬은 두번째 데이터부터 시작한다.) 

퀵 정렬(Quick Sort), 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.

계수 정렬(Count Sort), 데이터의 크기 범위가 제한되어 있는 정수 형태로 표현할 수 있을 때 사용한다. 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다.

---

• 수행시간 (N=데이터 갯수 K=데이터 중 최대값)

선택 정렬	삽입 정렬	퀵 정렬	계수 정렬
O(N²)	O(N²) 데이터가 거의 정리되어 있는 상태라면 O(N)	O(NlogN) 선택, 삽입에 비해 매우 빠른편	O(N+K) 가장 빠르지만 제한적 사용(데이터 범위 한정)

* 기수 정렬Radix Sort는 계수 정렬에 비해서 동작은 느리지만, 처리할 수 있는 정수의 크기가 더 크다.

참고자료 : 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 지음, 한빛미디어 옮김