Search
Duplicate

[정렬] 선택정렬(selection sort), 삽입정렬(insertion sort)

간단소개
정렬들을 한번 훑어보자!
팔만코딩경 컨트리뷰터
ContributorNotionAccount
주제 / 분류
Algorithm
알고리즘
태그
Scrap
8 more properties

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