[ Algorithm ] Insertion Sort(삽입 정렬)

Insertion Sort

• 버블 정렬, 선택 정렬보다 구현은 아주 조금 힘듦
• 목록을 차례대로 훑으면서 다음 과정을 반복
  • 현재 위치의 요소를 뽑음
  • 이걸 과거에 방문했던 요소들 중에 어디 사이에 넣어야 정렬이 유지되는지 판단
  • 그 위치에 삽입
  • 삽입으로 인해 다른 요소들을 오른쪽으로 밀어야(shift)할 수도 있음
• 평균 수행 시간: O(N^2)
• 최악 수행 시간: O(N^2)
• 메모리(공간 복잡도): O(1)
• 안정성: O

public class InsertionSort {
    public static int[] insertionSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int count = i;
            while (count>0) {
                if (arr[count-1] > arr[count]) {
                    int temp = arr[count];
                    arr[count] = arr[count - 1];
                    arr[count-1] = temp;
                }
                count --;
            }
        }
        return arr;
    }

}