3주차 자료구조 스터디 - 삽입정렬(insert_sort)

3주차 이번 주 주제는 <정렬> 이었다. 

1) 삽입정렬이란?

갓키백과에 따르면 삽입 정렬(揷入整列, insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

그냥 자신의 이전부분과 비교해가며 자신의 자리를 찾아 삽입하는 정렬 알고리즘이다. 

 

2) 삽입정렬 원리

엄청 간단하다. 정렬되어있는 자기 인덱스 이전부분(왼쪽)만 바라보며 자기의 자리를 찾아가면 된다. 

 

1. 설정한 피봇을 temp등으로 저장해놓고 자신보다 인덱스가 작은 쪽으로 (왼쪽) 내려간다.

- 그렇기 때문에 1번 인덱스부터 pivot이 될 수 있다.

2. 자신의 값보다 큰 값이 나왔다면 오른쪽으로 한칸씩 민다. 

ex) 1 4 5 3 에서 피봇이 3이라면 

     1    4 5 이렇게 한칸씩 미뤄준다.

3-1. 자신보다 작은 값이 나온 그 바로 뒤 인덱스에 pivot값으로 대체해준다.

3-2. 배열의 맨 앞으로 탐색할때까지 작은 값이 나오지 않았다면 맨 앞에 삽입 

4. 피봇이 다음 인덱스로 넘어간다.

1~4 과정을 배열이 끝날때까지 반복한다. 

 

1) arr[1] = 2를 pivot으로 잡는다. 

index 1 기준을로 index를 하나씩 줄이며 탐색한다. 왼쪽만 바라보겠다는 뜻

6은 2보다 크므로 6을 오른족으로 한 칸 민다. 

6

6

5

1

4

3

이후 배열의 맨 앞까지 탐색하는 동안 작은 값이 나오지 않았으므로 맨 앞에 2 삽입 

2

6

5

1

4

3

 

2) pivot = 5 설정

한 칸 앞인 6은 5보다 크므로 6을 오른쪽으로 한 칸 민다. 

2

6

6

1

4

3

또 한 칸 앞인 2는 5보다 작으므로 stop 

2 바로 뒤에 5를 삽입한다. 

2

5

6

1

4

3

 

3) pivot = 1 설정

한 칸 앞인 6은 1보다 크므로 6을 오른쪽으로 한 칸 민다.

2

5

6

6

4

3

또 한 칸 앞인 5는 1보다 크므로 5를 민다.

2

5

5

6

4

3

또 한 칸 앞인 2도 1보다 크므로 2를 민다. 

2

2

5

6

4

3

배열의 맨 앞까지 왔지만 pivot보다 작은 수가 없었으므로 맨 앞에 삽입 

1

2

5

6

4

3

 

3) pivot = 4 설정

한 칸 앞인 6은 4보다 크므로 6은 오른쪽으로 한 칸 밀림

1

2

5

6

6

3

또 한 칸 앞인 5도 4보다 크므로 한 칸 밀림 

1

2

5

5

6

3

2는 4보다 작으므로 stop 2 바로 뒤에 4를 삽입 

1

2

4

5

6

3

 

 

4) pivot = 3 설정 

한 칸 앞인 6이 더 크므로 오른쪽으로 한 칸 밀림 

1

2

4

5

6

6

한 칸 앞인 5이 더 크므로 오른쪽으로 한 칸 밀림 

1

2

4

5

5

6

한 칸 앞인 4이 더 크므로 오른쪽으로 한 칸 밀림 

1

2

4

4

5

6

3보다 더 작은 2가 나오면 stop! 2 뒤에 3 삽입

1

2

3

4

5

6

 

3 ) 시간복잡도 : $n^{2}$

이미 정렬이 되어있는 경우 즉 운이 좋은 경우는 자기 바로 앞과만 비교하면 정렬이 되므로 n 이다. 

4) 삽입정렬 코드 

include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n;
vector<int>arr;

void insert_sort() {
	int i, j;
	// 인덱스 0기준 왼쪽에 아무것도 없으므로 1부터 시작
	for (i = 1; i < n; i++) {
		int temp = arr[i];
		for (j = i - 1; j > -1; j--) {// 현재 인덱스 i기준으로 왼쪽으로 내려가면서 확인 
			if (arr[j] > temp) arr[j + 1] = arr[j]; //만약 i 왼쪽 값이 i번째 값보다 크다면 인덱스를 하나 뒤로 미룬다.
			else break; // //i왼쪽에서 i값보다 작은 값 발견시 바로 멈춘다.  
		}
		printf("%d", j);
		// 만약 멈췄다면 j는 처음으로 i번째 값인 temp보다 작은 값일테고 
		// 멈추지않고 for문이 끝났다면 j는 -1일것이다.
		// 그렇기 때문에 j+1 번째에 삽입해주자.
		arr[j + 1] = temp;
	}
}

int main()
{
	scanf("%d", &n);
	arr.resize(n + 1);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}
	insert_sort();
	for (int i = 0; i < n; i++)printf("%d\n", arr[i]);
}