삽입 정렬(insertion sort)

버블정렬을 거꾸로 하는거 같다..

삽입정렬이라 하는 이유는 작은 값을 앞에 끼워넣기 때문이라고 한다 근데 실제로 구현은 스왑처리를 한다.

1회차 순회
1번인덱스의 값을 0번인덱스와 비교후 1번이더 작으면 스왑 아니면 break;

2회차 순회
2번인덱스의 값을 1번인덱스와 비교후 2번이 더 작으면 스왑 아니면 break;
1번인덱스의 값을 0번인덱스와 비교후 1번이더 작으면 스왑 아니면 break;

3회차 순회
3번인덱스의 값을 2번인덱스와 비교후 3번이 더 작으면 스왑 아니면 break;
2번인덱스의 값을 1번인덱스와 비교후 2번이 더 작으면 스왑 아니면 break;
1번인덱스의 값을 0번인덱스와 비교후 1번이더 작으면 스왑 아니면 break;

결과

public class InsertionSort {

    ArrayList<Integer>  list;

    InsertionSort()
    {
        list = new ArrayList<>();
    }

    void Add(Integer value)
    {
        list.add(value);
    }

    void Sort()
    {
        for(int i = 0; i < list.size()-1; ++i)
        {
            for(int j = i+1; j > 0; --j)
            {
                if(list.get(j-1) > list.get(j))
                {
                    Collections.swap(list, j-1, j);
                }
                else
                    break;
            }
        }
    }

    @Override
    public String toString() {
        return "InsertionSort{" +
                "list=" + list +
                '}';
    }
}

public class InsertionSortTest {
    public static void main(String[] args) {
        InsertionSort is = new InsertionSort();

        is.Add(10);
        is.Add(9);
        is.Add(8);
        is.Add(7);

        is.Sort();

        System.out.println(is);
    }
}

오랜만에 다시 짜봄.. 1시간30분이나 걸렸다 하..

public class InsertionSort {


    public static void main(String[] args) {

        int[] arr = {78, 5, 2, 15, 7};

        int idx = 0;
        int value = 0;
        for (int i = 0; i < arr.length -1; i++) {
            value = arr[i+1];
            for (int j = i; j >= 0; j--) {
                if(arr[j] > value){
                    arr[j+1] = arr[j];
                }else {
                    idx = j+1;
                    break;
                }
            }

            arr[idx] = value;

        }

        for(int i : arr){
            System.out.println(i);
        }
    }
}