[알고리즘]삽입정렬(Insertion Sort)

삽입정렬이란?

두번째 수부터 자신 왼쪽의 수와 비교하여

내가 더 작으면 왼쪽으로 이동하고,

크면 오른쪽 위치를 유지합니다.

위치를 유지했으면 그 수에 대한 비교는 종료

왼쪽으로 이동했으면, 다시 자신의 왼쪽 수와 비교를 반복합니다.

 

1. 내 왼쪽과 비교
2. 내가 더 크면 현재 위치 유지
3. 내가 더 작으면 왼쪽 수와 교체(swap)
4. 다시 1번단계부터 비교 반복
5. 마지막 수 까지 비교완료하면 종료

시간복잡도

최악의 경우는 역으로 정렬되어 있는 경우

n-1, n-2, ... 1만큼 비교하여 시간복잡도 O(n^2)입니다.

 

 

소스코드(C++)

#include <iostream>
using namespace std;

void insertion_sort(int arr[],int size){ //삽입정렬
	for(int i = 1;i<size;i++){
		for(int j = i;j>0&&arr[j-1]>arr[j];j--){ //왼쪽이 오른쪽보다 작으면 교환, j = 0이 되면 j-1이 없으므로
			swap(arr[j-1],arr[j]);
		}
	}
}

void swap(int &a,int &b){ //교환
	int temp = a;
	a = b;
	b = temp;
}

int main(){
	int arr[] = {7,2,1,6,4,3,5};
	int size = sizeof(arr)/sizeof(int);

	insertion_sort(arr,size);//삽입정렬

	for(int i = 0;i<size;i++){//출력
		cout<<arr[i]<<' ';
	}
}