삽입정렬

1. 삽입정렬이란?

삽입정렬은 정렬 안된 부분에 있는 데이터를 정렬 된 부분의 특정 위치에 삽입해가면서 정렬을 진행하는 것이다.

전체적인 원리는 처음 5는 정렬되어있다고 생각하고 3부터 2,4,1을 차례대로 정렬을 진행한다.

이를 위한 구체적인 다른 예시를 봐보자

아래와 같이 데이터를 한 칸씩 뒤로 밀면서 삽입할 위치를 찾는것이다.

2. 삽입정렬 구현

구현설명은 코드 주석을 봐보자

public class InsertionSort 
{
    public static void main(String[] args) 
    {
        int[] arr = {3, 2, 4, 1};
 
        SelSort(arr, arr.length);
 
        for(int i=0; i<arr.length; i++) 
            System.out.print(arr[i]);
    }
    static void SelSort(int[] arr, int n) 
    {
        int i, j;
        int temp;
 
        for(i=1; i<n; i++)//i는 1부터시작 맨첫번째 값은 정렬완료된거로 하자.
        {
            temp = arr[i];   // 정렬 대상을 temp에 저장
 
            for(j=i-1; j>=0 ; j--)
            {
                if(arr[j] > temp)//데이터간 비교 연산
                    arr[j+1] = arr[j]; //데이터간 이동 연산 , 비교 대상 한 칸씩 계속 뒤로 밀기
                else
                    break; // 삽입 위치 찾았으니 탈출!
            }
 
            arr[j+1] = temp; // 찾은 위치에 정렬 대상 삽입!
        }
    }
}

3. 성능 평가

비교횟수는 다음 반복문 안에 위치한 if문의 실행 횟수를 기준으로 계산할 수 있다.

if(arr[j] > temp) 

         arr[j+1] = arr[j];

4개의 데이터를 3단계에 걸쳐서 정렬하였다. 최악의경우 비교의 횟수를 더한 결과는 1+2+3 이었다.

이렇듯 버블 정렬의 데이터의 수가 n개일때 진행되는 비교의 횟수는 다음과 같다.

 1 + 2+...+(n-2) + (n-1)

그리고 이 역시 등차수열의 합에 해당하므로 앞서본 선택정렬,버블정렬과 마찬가지로

빅-오는 O(n^2) 이다.