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

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

삽입 정렬 (Insetion Sort)

 

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

 

 

정렬 방식

 

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

 

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

 

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

 

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

 

 

 

: 정렬이 완료 된 상태

 

 

 

: 비교되는 배열 요소들

 

 4

 3

 2

 1

 

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

 

 

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

 

4

5

 

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

 

4

5

 

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

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

 

 

 3

     

4

 

5

 

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

 

 4

 5

 2

 1

 

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

 

 

특징

 

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

 

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

 

소스코드 (Source Code)

 

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)


댓글(0)

Designed by JB FACTORY