[알고리즘] 삽입 정렬

삽입 정렬

선택, 버블, 삽입 정렬 다음으로 세번째 순서, 삽입 정렬입니다.

삽입 정렬은 아래와 같이 이해하였습니다.

 

"원소를 이전 순서에 이미 정렬된 원소들과 비교해 작은 수가 되는 위치에 넣는다."

 

 

최악의 경우 O(N^2) 시간 복잡도를 갖지만 이전 인덱스의 수들이 정렬이 되어있다는 가정 때문에 모든 원소를 비교하지 않아 정렬 중 성능이 좋은편이라고 합니다.

 

나동빈 님의 알고리즘 강좌를 보고 구현해보았습니다.

구현

#include <stdio.h>
#include <iostream>

using namespace std;

int main() {

	int j, temp;

	int arr[10] = { 1,10,5,8,7,6,4,3,2,9 };

	//비교 횟수 == 원소 갯수 -1 ==  i = 9
	for (int i = 0; i < 9; i++) {
		j = i;

		//현재 원소가 다음 원소 보다 크면 위치를 바꿈
		while (arr[j] > arr[j + 1]) {

			temp = arr[j];
			arr[j] = arr[j + 1];
			arr[j + 1] = temp;
			j--; //이전 인덱스와 비교
			
		}
	}

	for(int k =0; k< 10;  k++){
		std::cout << arr[k] << "\n";
	}
	return 0;
}

 

마치며

삽입 정렬을 알아보았습니다. 선택 정렬과 버블 정렬을 공부할 때 무조건 비교연산이 들어가는데에 연산이 불필요하다고 느꼈었는데, 이를 필요한 부분에서만 비교 연산하도록 바꾸어 성능이 많이 올라갈 것 같네요

이후에 더 성능이 좋은 정렬을 공부하여 올리도록 하겠습니다!

 

읽어주셔서 감사합니다 C: