[자료구조] 삽입정렬(InsertSort) with JAVA

[자료구조] 삽입정렬(InsertionSort) with JAVA

 

 

* 삽입정렬이란?

 삽입정렬은 정렬되어 있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방법이다. 

 정렬할 자료가 두 개의 부분집합 S와 U로 나뉘어 있다고 가정한다. 맨 앞 원소부터 정렬을 수행하는데 맨 앞 원소는 집합 S, 나머지는 U로 칭한다. U의 첫번째 원소와 맨 앞 원소인 집합 S에 들어있는 원소를 비교하고 집합 S에 있는 원소와 비교하여 정렬한다. 반복적으로 정렬되지 않은 U 집합의 원소들을 S집합의 마지막 원소, 그 앞 원소, 앞앞 원소들과 반복적으로 비교한다.

 

* 예시

 

1) 시작 

 - 첫 번째 원소는 정렬된 부분집합 S로 생각하고 나머지 원소는 정렬 안된 부분 집합 U라고 가정

63

13

28

2

15

7

30

23

 

 S = {63} 

 U = {13, 28, 2, 15, 7, 30, 23}  

 

2) U의 첫번째 원소를 S의 마지막 원소와 비교한다. 이 때, 13<63 이므로 S 집합의 첫번째로 보낸다.

13

63

28

2

15

7

30

23

 

 S = {13, 63} 

 U = {28, 2, 15, 7, 30, 23}  

 

3) U의 첫번째 원소를 S의 두번째(마지막) 원소와 비교한다. 이 때, 28<63 이다.  S의 첫번째 원소와 비교한다. 이 때, 13<28이다.  13은 S의 두번째로 이동한다. 

13

28

63

2

15

7

30

23

 

 S = {13, 28, 63} 

 U = {2, 15, 7, 30, 23}  

 

4) U의 첫번째 원소를 S의 두번째(마지막) 원소와 비교한다. 이 때, 28<63 이다.  S의 첫번째 원소와 비교한다. 이 때, 13<28이다.  13은 S의 두번째로 이동한다. 

13

28

63

2

15

7

30

23

 

 S = {13, 28, 63} 

 U = {2, 15, 7, 30, 23}  

 

... 

 

 

이런식으로 반복한다. *(여유가 생기면 마저 작성해야겠다)*

 

 

 

*삽입정렬 Java 코드

package Sort;

import java.util.Arrays;

public class InsertionSort {

    public static void insertionSort(int[] a, int size) {
        System.out.println("정렬할 원소:"+Arrays.toString(a));
        System.out.println("--------------------삽입정렬 수행----------------------");
        for(int i=1;i<size;i++) {
            int temp = a[i];
            int j = i;
            while((j>0) && (a[j-1]>temp)) {
                a[j] = a[j-1];
                j = j-1;
            }
            a[j] = temp;
            System.out.println(i+"단계 : "+Arrays.toString(a));
        }
    }
    public static void main(String[] args) {
        int[] list = {63, 13, 28, 2, 15, 7, 30, 23};
        int size = list.length;
        insertionSort(list, size);
        
    }

}