[Algorithm] 삽입정렬(Insertion Sort)

설명

• 이웃에 있는 작은 값을 큰 값 앞에 삽입하여 정렬하는 방식
• 거의 정렬된 상태라면 굉장히 효율적인 방식
• 시간 복잡도 : O(N^2)
• 참고
  • https://youtu.be/16I9Z7bS1iM

예시

• 초기값
  • 5 1 8 10 7
• 5(i)(j) 1 8 10 7
  • j가 j+1보다 크므로 위치 변경 : 1(i)(j) 5 8 10 7
  • j-- 값은 0보다 작으므로 패스 
• 1 5(i)(j) 8 10 7
  • j가 j+1보다 작으므로 패스
• 1 5 8(i)(j) 10 7
  • j가 j+1보다 작으므로 패스
• 1 5 8 10(i)(j) 7
  • j가 j+1보다 크므로 위치 변경 : 1 5 8 7(i)(j) 10
  • j-- : 1 5 8(j) 7(i) 10
  • j가 j+1보다 크므로 위치 변경 : 1 5 7(j) 8(i) 10
  • j-- : 1 5(j) 7 8(i) 10
  • j가 j+1보다 작으므로 패스
• 1 5 7 8 10

코드

public class Solution {
    public int[] sort(int[] data) {
        for (int i = 0; i < data.length - 1; i++) {
            int j = i;

            while (j >= 0 && data[j] > data[j + 1]) {
                int temp = data[j];
                data[j] = data[j + 1];
                data[j + 1] = temp;
                j--;
            }
        }

        return data;
    }
}

class SolutionTest extends Specification {
    @Unroll
    def "#data -> #result"() {
        expect:
        new Solution().sort(data as int[]) == result as int[]

        where:
        data                            | result
        [5, 1, 8, 10, 7]                | [1, 5, 7, 8, 10]
        [1, 10, 5, 8, 7, 6, 4, 3, 2, 9] | [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    }
}