삽입 정렬(Insertion Sort)

동빈나 실전 알고리즘 강좌(Algorithm Programming Tutorial) 참고

https://www.youtube.com/playlist?list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz

실전 알고리즘 강좌 (Algorithm Programming Tutorial)

삽입 정렬(Insertion Sort)

각 숫자를 적절한 위치에 삽입하자

다른 정렬방식들은 무조건 위치를 바꾸는 방식이었다면 삽입 정렬은 필요할 때만 위치를 바꿈

시간 복잡도 : O(N^2)

시간 복잡도는 선택 정렬, 버블 정렬과 같으나 거의 정렬된 상태라면 삽입 정렬이 훨씬 효율적으로 동작

 

만약 1 5 10 8 ... 의 숫자가 있고, 8의 위치를 결정할 경우라면 8은 _1_5_10_ 총 4 곳에 들어갈 수 있으며 5와 10 사이에 결과적으로 들어가게 된다. 여기서 8 앞의 원소들은 이미 코드를 수행하면서 이미 정렬된 상태이므로 8만 잘 끼워넣으면 됨. 8의 적절할 위치는 왼쪽값이 자신보다 작을 경우를 만날 때까지(j--) 반복문을 수행하면서 자리를 결정하면 됨

 

package algorithmProgramming;

public class Insertion {

    public static void main(String[] args) {

        int[] numbers = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 }; // 1 5 8 10 7 6 ...

        for (int i = 0; i < numbers.length - 1; i++) { 
            int j = i; 
            while (j >= 0 && numbers[j] > numbers[j + 1]) { 
                int tmp = numbers[j]; 
                numbers[j] = numbers[j + 1]; 
                numbers[j + 1] = tmp; 
                j--; 
            }
        }

        for (int i = 0; i < numbers.length; i++) {
            System.out.print(numbers[i] + " ");
        }

    }

}

 

오름차순 정렬 완료