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)이므로, 시간상으론 다소 비 효율적이지만, 그 구현이 가장 간단한 형태의 정렬 알고리즘 이다.
