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)

 

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

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;     }

 

 다른 정렬 알고리즘 공부하기 !!

2017/11/07 - [Study/알고리즘] - 07 정렬 알고리즘 - 힙 정렬 (Heap Sort)

2017/09/29 - [Study/알고리즘] - 06 정렬 알고리즘 - 기수 정렬(Radix Sort)

2017/09/25 - [Study/알고리즘] - 05 정렬 알고리즘 - 병합 정렬 (Merge Sort)

2017/09/21 - [Study/알고리즘] - 04 정렬 알고리즘 - 퀵 정렬 (Quick Sort)

2017/09/17 - [Study/알고리즘] - 03 정렬 알고리즘 - 버블 정렬 (Bubble Sort)

2017/09/14 - [Study/알고리즘] - 01 정렬 알고리즘 - 선택 정렬(Selection Sort)