[백준 2750번][C++] 수 정렬하기 - 5. 삽입 정렬

<문제 소개>

---

<소스 코드>

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <cmath>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstdlib>
using namespace std;

void InsertionSort(vector<int>& v)
{
	for (int i = 1; i < v.size(); i++)
	{
		int insertVal = v[i]; // 삽입할 원소
		int insertIndex = i; // 삽입할 위치

		for (int j = i - 1; j >= 0; j--)
		{
			if (insertVal < v[j])
			{
				// 앞의 원소보다 작은 경우 -> swap 아님
				// -> 뒤의 원소에 앞의 원소의 값을 넣음
				v[j + 1] = v[j];
				insertIndex--;
			}
			else
			{
				// 앞의 원소보다 큰 경우 -> 해당 위치 다음 위치에 원소 삽입
				break;
			}
		}

		// 삽입할 위치에 삽입할 원소를 넣음
		v[insertIndex] = insertVal;
	}
}

int main()
{
	int N;
	cin >> N;

	vector<int> v;

	// 원소 입력
	while (N > 0)
	{
		int x;
		cin >> x;

		v.push_back(x);
		N--;
	}

	// 5. 삽입 정렬
	// 1. 두 번째 원소부터 시작하여 해당 원소 앞의 원소들과 하나씩 대소비교
	// 2. 앞의 원소보다 작을 경우 swap을 통해 위치변경x (swap은 비용이 많이들기 때문)
	// -> 뒤의 원소자리에 앞의 원소를 넣음
	// 3. 자신보다 작은 수가 나올때까지 반복진행
	// 4. 반복이 끝나면 삽입할 자리에 해당 원소를 넣음
	InsertionSort(v);

	// 원소 출력
	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << endl;
	}

	return 0;
}

---

<풀이과정>

1. 두번째 원소부터 정렬 시작

2. 정렬할 원소의 값 insertVal는 v[i]로, 해당 원소가 마지막에 삽입될 인덱스를 나타낼 insertIndex는 i로 초기화

3. 정렬할 원소의 앞의 원소들부터 차례로 대소비교

4. 정렬할 원소 insertVal가 현재 비교하는 앞의 원소 v[j]보다 작을 경우에 비교하는 원소의 값 v[j]를 한칸 뒤 v[j+1]에 넣어주고 insertIndex를 1씩 감소시킨 뒤 다음 반복을 진행한다.

5. 정렬할 원소 insertVal가 현재 비교하는 앞의 원소 v[j]보다 클 경우에는 반복을 끝낸다.

6. 정렬할 원소에 대한 대소비교가 끝나면 insertIndex자리에 insertVal를 넣어준다. v[insertIndex] = insertVal;

7. 다음 원소를 정렬시킴

8. 위의 과정을 마지막 원소까지 반복 

---

<코멘트>

이번엔 다섯번째 방법인 삽입 정렬로 풀어보았다!

여태까지 반복하면서 삽입할 원소를 계속 swap을 하는 줄 알았는데 아니었고, 비교한 원소의 값만 옮겨주고 삽입할 원소는 마지막에 삽입위치에 넣어주는 거였다.

 

- 삽입 정렬 -

장점 

- 최선의 경우 O(n)이라는 엄청나게 빠른 효율성을 가진다.

- 성능이 좋아서 다른 정렬 알고리즘의 일부로 사용될 만큼 좋은 정렬법이다.

 

단점

- 최악의 경우 O(n^2)이라는 시간복잡도를 갖게됨

- 데이터의 상태 및 데이터의 크기에 따라서 성능의 편차가 굉장히 심한 정렬법이다.

 

특징 

1. 시간복잡도

- 최악 : O(n^2)

- 평균 : O(n^2)

- 최선 : O(n)

2. 공간복잡도 O(1) 

3. in-place정렬 - 주어진 배열 내에서만 위치를 바꾸기 때문

4. not-stable정렬 

5. 선택 정렬이나 버블 정렬에 비해 상대적으로 빠름

 

<cf>

1. stable vs not-stable

- stable 정렬은 중복된 키 값이 있을 때 이를 순서대로 정렬하는 알고리즘을 뜻함.

- 즉 , 정렬했을 때 중복된 키 값이 원래 순서대로 정렬되어있으면 stable 아니면 not-stable이다.

2. in-place vs not in-place

- in- place 정렬은 원소들의 개수에 비해 충분히 무시할 만한 저장 공간만을 더 사용하는 정렬 알고리즘을 뜻함.

- not in-place 정렬은 원소들의 개수에 비례하여 저장 공간을 더 사용하는 정렬 알고리즘을 뜻함.

---

<제출 결과>

<삽입 정렬> - 버블/선택 정렬보다 빠른 시간대, 밑의 결과는 매번 swap했을 경우

<힙 정렬> - 퀵 정렬보다 느린 시간대

<퀵 정렬> - 준수한 시간이라 선택정렬과 비슷한 시간대가 나온듯..?

<비교 - 선택정렬> - 버블정렬에 비해 조금 더 빠르다는 것을 알 수 있음

<비교 - 버블정렬> 

---