#014 삽입 정렬

# 문제)

아래와 같이 정렬되지 않은 배열이 있을때 삽입 정렬을 사용하여 오름차순 정렬하여라.

<초기>

5

2

4

3

1

선택정렬은 방향이 버블과 선택과 다르다.

버블과 선택은 왼쪽에서 오른쪽으로 이동했다면

삽입 정렬은 두번째 부터 시작하여 왼쪽으로 이동하며 삽입될 위치를 찾는다.

만약 왼쪽 값이 더 큰 경우, 왼쪽 값을 현재 인덱스 값에 저장한다. (배열 shift처리)

더이상 왼쪽으로 이동할 수 없거나, 왼쪽값이 더 작다면 삽입할 위치를 찾은 것이므로 해당 위치에 값을 저장한다.

<1회전> int tempValue = 2;

5

2

4

3

1

5

5

4

3

1

2

5

4

3

1

<2회전> int tempValue = 4;

2

5

4

3

1

2

5

5

3

1

2

5

5

3

1

2

4

5

3

1

<3회전> int tempValue = 3;

2

4

5

3

1

2

4

5

5

1

2

4

4

5

1

2

4

4

5

1

2

3

4

5

1

<4회전> int tempValue = 1;

2

3

4

5

1

2

3

4

5

5

2

3

4

4

5

2

3

3

4

5

2

2

3

4

5

1

2

3

4

5

package dataStructure.sort.insertion;

public class InsertionSort {

    private int[] array;

    private int size;

    private int maxSize;

   

    public InsertionSort(int maxSize) {

        // TODO Auto-generated constructor stub

        this.maxSize = maxSize;

        this.array = new int[this.maxSize];

        this.size = 0;

    }

   

   

    public void add(int value) {

        if(size >= maxSize) {

            System.out.println("error. max size..");

            return;

        }

        array[size++] = value;

    }

   

    public void add(int...values) {

        if((this.size + values.length) >= this.maxSize) {

            System.out.println("max size.. so, can't add..");

            return;

        }

       

        for(int i=0; i<values.length; i++) {

            this.array[this.size++] = values[i];

        }

    }

   

    public void sort() {

        int j = 0;

        for(int i=1; i < size; i++) {

            int insertionValue = array[i];

            for(j=i-1; j>=0; j--) {

                if(insertionValue < array[j]) {

                    array[j+1] = array[j];

                }else {

                    break;

                }

            }

            //j가 이미 -1이 된 상태이므로 (증감식이 실행된 후 나옴)

            array[j+1] = insertionValue;

        }

    }

   

    @Override

    public String toString() {

        // TODO Auto-generated method stub

        StringBuilder result = new StringBuilder();

        result.append("[");

        int i = 0;

        while( i < size ) {

            result.append(array[i]);

            if( i != size-1) {

                result.append(",");

            }

            i++;

        }

        result.append("]");

        return result.toString();

    }

   

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        InsertionSort insertion = new InsertionSort(10);

        insertion.add(5,2,4,3,1);

        System.out.println(insertion);

        insertion.sort();

        System.out.println(insertion);

    }

}