어떤 상황에서 어떤 정렬 알고리즘을 사용할까

알고리즘 별 정리

---

 

- 선택정렬

• 방법 : "남은 것 중에서 가장 작은 값을 앞으로 가져오기" 를 반복한다.
• 시간복잡도 : O(N^2)

- 삽입정렬

• 방법 : 하나씩 보면서 그 지점의 왼쪽은 정렬이 되었다고 생각하고 왼쪽의 수와 비교하며 적절한 위치에 놓는 방법
• 시간복잡도 : O(N^2)
• 특징 : 왼쪽이 정렬되었다고 생각하고 진행하기 때문에, 거의 정렬이 되어있다면 매우 빠르게 동작한다.

- 퀵 정렬

• 방법 : pivot보다 큰 데이터와 작은 데이터의 위치를 바꾼다.
• 시간복잡도 : O(N log N)
• 특징 :
  1. pivot을 기준으로 분할함 -> 데이터의 범위가 줄어듦. 그래서 빠르다
  2. 최악의 경우(이미 정렬된 배열일 때) O(N^2)의 시간복잡도를 가진다. -> 양쪽으로 분할이 안이루어짐

- 계수 정렬

• 방법 : 가장작은 값 ~ 가장 큰 값 범위를 담을 수 있는 배열을 생성하고 각 수가 몇번 나오는지 카운팅한다
• 시간복잡도 : O(N + K)
• 특징 :
  1. 타입이 정수형일때만 사용 가능하다.
  2. 경우에 따라 심각한 비효율성 발생가능( ex. 데이터가 0, 999999만 존재할때)
  3. 동일한 값을 가지는 데이터가 여러개 등장할때 효율적이다. (ex. 성적)

 

 

 

어떤상황에서 어떤 알고리즘을 선택해야할까?

---

알고리즘	시간복잡도	좋은 상황
선택정렬	O(N^2)	단순한 구현이 필요할때
삽입정렬	O(N^2)	데이터가 거의 정렬되어 있을때
퀵정렬	O(N log N)	거의 정렬된 배열이 아닐때 ( 대부분의 경우)
계수 정렬	O(N + K)	데이터가 정수일때, 중복된 수가 많을 때