02 정렬 알고리즘 - 삽입 정렬 (Insetion Sort)

삽입 정렬 (Insetion Sort)

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 입니다.

 

■ 정렬 방식

1. 배열의 첫 번째 요소는 정렬 된 상태라고 가정한다.

2. 배열의 두 번째 요소부터 앞에 정렬된 배열을 차례대로 비교하며 교환한다.

3. 최종적으로 자신의 위치에 맞는 위치에 삽입된다.

4. 다음 배열 요소에 대해서 같은 작업을 반복한다.

: 정렬이 완료 된 상태

: 비교되는 배열 요소들

 

5

4

3

2

1

 

첫 번째 배열요소는 정렬이 완료된 상태라고 가정을 합니다.

 

5

4

3

2

1

 

두 번째 요소부터 비교를 시작합니다. 앞에 정렬된 첫 번째 요소와 비교를 하고 4가 더 작으므로 둘의 위치를 바꿔줍니다.

 

4

5

3

2

1

 

다음은 3번째 배열 요소를 앞에 정렬 된 두개의 배열요소를 차례대로 비교합니다.

 

4

5

3

2

1

 

3번째와 2번째를 비교합니다. 3이 더 작으므로 4를 3의 위치에 옮깁니다.

3은 아직 제 위치를 찾은게 아니므로 계속 이동합니다.

 

	3
4		5	2	1

 

4와 3을 비교합니다. 3이 더 작으므로 최종적으로 첫 번째 위치에 삽입됩니다.

 

3

4

5

2

1

 

3번째까지 정렬이 완료된 상태입니다. 나머지 배열 요소에 대해서도 반복적으로 작업을 수행하게 되면 최종적으로 정렬이 완료 됩니다.

  

■ 특징

1. 비교적 작은 배열에 대해서는 효율이 좋다. 

2. 시간복잡도는 O(n＾2)

 

■ 소스코드 (Source Code)

    public int[] Insertion_Sort(int[] data,int num)
    {
        int tmp,i,j;
        for(i=1;i<data.length;i++)
        {
            tmp = data[i];
            for(j=i-1;tmp>data[j]&&j>=0;j--)
            {
                data[j+1] = data[j];
            }
            data[j+1] = tmp;
        }
        return data;
    }

 

출처 : https://lktprogrammer.tistory.com/28?category=672214