알고 공부. 2) 삽입 정렬

2020/05/28 - [알고리즘 공부하기/정렬] - 알고 공부. 1) 버블 정렬

알고 공부. 1) 버블 정렬

삽입 정렬은 각 숫자를 적절한 위치에 삽입하는 방법으로 문제를 해결하게 된다.

시간 복잡도 O(N*N) 중 가장 빠른 정렬 방법이다.

 

문제는 버블 정렬의 글에 있는 문제와 동일하다.

앞에 있는 원소들이 이미 정렬이 되어있다고 가정을 한다.

이 가정이 선택과 버블 정렬보다 조금 더 효율적이지만 시간복잡도는 동일하다.

 

#include <stdio.h>

int main(void) {
	int i, j, tmp;
	int array[10] = { 10,1,5,8,7,6,4,3,9,2 };
	for (i = 0; i < 9; i++)
	{
		j = i;
		while (array[j] > array[j + 1]) {
			tmp = array[j];
			array[j] = array[j + 1];
			array[j + 1] = tmp;
			j--;
			if (j < 0)
				break;
		}
	}
	for (int i = 0; i < 10; i++)
		printf("%d ", array[i]);
	return 0;
}

 

 

 

내가 생각했던 문제 풀이 방법

- 배열 인덱스 i의 값을 가지구 배열 맨 앞부터 비교를 하면서 맞는 위치를 찾았을 때

그 위치에 값을 대입해주려고 했다. 문제가 발생했던 점은 그 뒤에 이미 정렬이 완료되었다고

가정한 인덱스가 남아있다면 이 값들은 또 계속 뒤로 밀어줘야하나? 라는 생각이 들었다.

 

간단하게 문제 해결한 것은 인덱스가 만약 5라면 5부터 0까지 내려가면서 자신의 값이 앞 인덱스의 값 보다

작을 경우에 계속 값을 스왑하면서 간다는 것이다. 그럼 아까 위에 문제점도 해결하면서 정렬도 되는 것이다.