삽입 정렬

삽입 정렬

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다

선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작한다.

삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다.

• 최선의 경우 O(N)

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

 

 

구현 과정

0) 첫 번째 데이터 '7'은 그 자체로 정렬이 되어 있다고 판단하고, 두 번째 데이터인 '5'가 어떤 위치로
들어갈지 판단한다. '7'의 왼쪽으로 들어가거나 오른쪽으로 들어가거나 두 경우만 존재한다.

1) 이어서 '9'가 어떤 위치로 들어갈지 판단한다.

2) 이어서 '0'이 어떤 위치로 들어갈지 판단한다.

3) 이어서 '3'이 어떤 위치로 들어갈지 판단한다.

4) 이러한 과정을 반복하며 정렬이 완료된다.

 

 

예제 코드

import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        int n = 10;
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
 
        for (int i = 0; i < n; i++) {
            // 인덱스 i 부터 1까지 감소하며 반복하는 문법
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    // swap
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                } else {
                    // 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
                    break;
                }
            }
        }
 
        for(int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}