개념

• 정렬이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것
• 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용
• 선택 정렬
  • 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복
  • 시간 복잡도 ⇒ O($N^2$)
• 삽입 정렬
  • 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입
  • 선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작
  • 시간 복잡도 ⇒ O($N^2$)
  • 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작
    • 최선의 경우 O(N)의 시간 복잡도를 가진다.
• 퀵 정렬
  • 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
  • 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘
  • 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정
  • 이상적인 경우 분할이 절반씩 일어난다면 전체 연산횟수로 O(NlogN)를 기대할 수 있다.
  • 평균의 경우 O(NlogN)의 시간 복잡도를 갖는다.
  • 하지만 최악의 경우 O(N^2)의 시간 복잡도를 갖는다.
• 계수 정렬
  • 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘
    • 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능
  • 데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행 시간 O(N+K)를 보장한다.
  • 계수 정렬의 시간 복잡도와 공간 복잡도 모두 O(N+K)이다.
  • 계수 정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용 가능

예시

Coding_Test_Study/삼성준비/정렬 at main · jaesukpark77/Coding_Test_Study