[알고리즘] 선택정렬, 삽입정렬, 퀵정렬, 계수정렬 정리

정렬

1. 선택 정렬
   • 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨앞에 있는 데이터와 바꾸는 것을 반복한다
   • 시간 복잡도는 O(n^2)
2. 삽입 정렬
   • 처리되지 않은 데이터를 하나씩 골라 적합한 위치에 삽입한다
   • 시간 복잡도 O(n^2)
   • 가장 빠른 경우는 O(n) 거의 정렬이 되었다고 가정할 시
3. 퀵 정렬
   • 기준데이터(pivot)을 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다
   • 병합정렬과 더불어 프로그래밍 언어의 정렬 라이브러리에 근간이 되는 알고리즘이다
   • 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정합니다
   • 피봇을 기준으로 왼쪽은 큰값, 오른쪽은 작은값을 골라서 서로 바꿔주고 이 값들의 인덱스가 엇갈리는 경우 작은데이터와 피봇값의 위치를 변경한다
   • 한 번 작업이 되면 분할(divide)를 할 수 있다, 반복하며 재귀적으로 퀵정렬은 동작한다
   • 이상적인 경우 분할이 절반식 일어난다면 시간 복잡도는 O(NlogN)
   • 최악의 경우는 O(N^2) , 이미 정렬되어있다고 가정할 경우

• 하지만 표준 라이브러리를 가지고 정렬을 사용하는 경우 O(NlogN)을 보장한다

4. 계수 정렬
   • 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘
     • 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능합니다.
   • 데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행시간 O(N+K)를 보장한다
   • 동일한 값을 가지는 데이터가 여러개 존재할 때 효율적이다