Algorithm

[Sort] Insertion

빠빠담 2020. 7. 7. 00:07
반응형

- 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함.

- 배열의 두 번째 데이터 부터 연산을 시작함.

- 시간복잡도 : O(n^2)

 

 

package algorithm.sort;

public class Insertion {

    public static void main(String[] args) {

        int[] arr = {3,6,1,9,2,   7,4,8,5,0,   14,23,98,45,76,   34};

        insertionSort(arr);

        System.out.println("===========================");
        for(int item : arr){
            System.out.print(item);
            System.out.print("|");
        }
        System.out.println();
        System.out.println("===========================");

    }

    private static void insertionSort(int[] arr){

        int j = 0;

        for(int i = 1 ; i < arr.length ; i++){

            int tmp = arr[i];

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

                if(arr[j] > tmp){
                    arr[j+1] = arr[j];
                }else{
                    break;
                }

            }

            arr[j+1] = tmp;
            
        }

    }

}
반응형

'Algorithm' 카테고리의 다른 글

[Sort] Quick  (0) 2020.07.12
[Sort] Merge  (0) 2020.07.07
[Sort] Bubble  (0) 2020.07.06
[Sort] Selection  (0) 2020.07.05