• 정렬(Sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다.
• 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다.

선택 정렬

• 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다.

  

  

  

  

선택 정렬의 시간 복잡도

• 선택 정렬은 N 번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다.
• 구현 방식에 따라 사소한 오차는 있을 수 있지만, 전체 연산 횟수는 다음과 같다.
  • N + (N-1) + (N-2) + ... + 2
• 이는 (N2 + N - 1) / 2 로 표현할 수 있는데, 빅오 표기법에 따라 O(N2)이라고 작성한다.

삽입 정렬

• 처리 되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.
• 선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작한다.