[it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비] 정렬 - 삽입정렬

문제

N개의 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.
정렬하는 방법은 삽입정렬입니다.

💡 입력설명
첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.

💡 출력설명
오름차순으로 정렬된 수열을 출력합니다.

💡 입력예제
6
13 5 11 7 23 15

💡 출력예제
5 7 11 13 15 23

 

---

코드

최종 풀이

#include <stdio.h>
#include <vector>

using namespace std;

int main() {
	int n, i, j, tmp;
	scanf("%d", &n);
	vector<int> a(n);
	for(i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	
	for(i = 1; i < n; i++) {
		tmp = a[i];
		for(j = i - 1; j >= 0; j--) {
			if(a[j] > tmp) {
				a[j + 1] = a[j];
			} else {
				break;
			}
		}
		a[j + 1] = tmp;
	}
	
	for(i = 0; i < n; i++) {
		printf("%d ", a[i]);
	}
	return 0; 
}

 

---

설명

사용자로부터 N을 입력받고 N만큼 반복하는 for문을 작성하여 자연수를 입력받고 배열  a에 할당한다.

배열의 index 1부터 N까지 반복하는 for문을 작성하고 tmp에 해당 배열의 값을 할당해놓는다.

해당 배열로 부터 0까지 비교하면서 해당 tmp 값보다 큰 값이 나타나면 index + 1에 해당 값을 할당해나간다. 작은 값일 경우 break를 통해 해당 for문에서 나오고 index + 1에 tmp값 할당한다.

 

---

배운 점

삽입정렬

개념

2번째 원소를 시작으로 앞의 위치한 원소들과 비교한 후 원소를 뒤로 옮기면서 삽입할 위치를 지정하는 알고리즘이다.

 

 

시간복잡도

(n-1) + (n-2) + (n-3) + .... + 2 + 1 => n(n-1)/2이므로, O(n^2) 이다.

 

공간복잡도

하나의 배열 안에서 swap이 이루어지며 정렬이 되므로 O(n)이다.

 

장점

1. 구현이 간단하다.

2. 이미 원소가 정렬되어 있으면 매우 효율적이다.

3. 다른 메모리 공간이 필요하지 않다.

4. 선택정렬, 버블정렬과 같이 시간복잡도가 O(N^2)인 알고리즘과 비교했을 때 비교적 빠르다.

 

단점

1. 그래도 시간복잡도가 좋지 않아 비효율적이다.

 

---

 

해당 내용은 김태원님의 'it 취업을 위한 알고리즘 문제풀이' 강의를 듣고 작성한 글입니다.