Subject

• 선택정렬
• 삽입정렬

1. 선택정렬?

선택 정렬이란, 가장 작은 것을 “선택”해서 앞으로 보내는 정렬 기법이다. 가장 작은 것을 선택하는데에 N번, 그 수를 앞으로 보내는 데에 N번의 연산을 하므로, O(N^2)의 시간 복잡도를 가진다.

• cf > 시간 복잡도는 항상 최악의 경우를 가정하고 생각한다.

  • 정렬 예시

    

    초기 상태

    

    

    그 때 그때 가장 작은 값을 찾아 정렬 중인 상태

    

    정렬 완료 된 상태

구현 해보자!

• scanf 함수를 사용한 간단 구현
• atoi를 이용해 입력받기

2. 삽입정렬?

삽입 정렬이란, 각 숫자를 적절한 위치에 삽입하는 정렬 기법이다. 들어갈 위치를 선택하는데 N번, 선택하는 횟수로 N번의 연산이 필요해, O(N^2)의 시간 복잡도를 가진다. 그러나, 이론상으로는 선택 정렬과 동일한 시간 복잡도를 가지나, 일반적으론 삽입 정렬의 처리 속도가 더 빠르다.

• 정렬 예시

  

  초기 상태

  

  2 < 4 이므로 그냥 넘어간다.

  

  다음 3은 2와 4 사이에 넣는다.

  

  1은 앞의 모든 수보다 작으므로 맨 앞으로 넣는다.

  

  위와 같이 쭉 진행중인 상태

구현 해보자!

• scanf로 간단 구현
• atoi를 이용해 입력 받기

요약

⇒ 선택 정렬과 삽입 정렬은 시간복잡도가 O(N^2)이므로, 시간상으론 다소 비 효율적이지만, 그 구현이 가장 간단한 형태의 정렬 알고리즘 이다.