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

Insertion Sort란?

• 2번째 원소부터 시작하여 앞의 원소들과 크기 비교 후 삽입할 위치를 선정하고 원소를 뒤로 옮기면서 정렬하는 알고리즘 
• 안전정렬이다
• 선택,버블 정렬보다 상대적으로 빠름
• 배열이 길어질수록 비효율

Insertion Sort 과정

1. 2번째에 위치한 원소를 temp로 저장
2. temp와 이전 원소를 비교하여 삽입
3. 1-2 반복 

삽입정렬 과정

Insertion Sort Code

public void insertionSort(int[]arr){
    for(int i=1; i<arr.length;i++){ //2번째 원소부터 시작
        int temp=arr[i]; //temp에 index값을 저장
        int pre = i-1; //해당 index의 이전 index 저장
        while((pre>=0) && (arr[pre]>temp)){ //이전위치의 값이 더 클 경우
            arr[pre+1]=arr[pre]; //값을 교환
            pre--;
        }
        arr[pre+1]=temp;
    }
}

 

시간 복잡도

• 최악의 경우(역으로  정렬되어 있을 경우) => O(n^2)
• 모두 정렬이 되어있는 경우 => O(n)

최악	평균	최선
O(n^2)	O(n^2)	O(n)

 

 

[참고 자료]

• 링크