삽입 정렬 알고리즘

public static List<Integer> insertSort(List<Integer> numbers) {
   List<Integer> sortedList = new LinkedList<>();

   originalList: for (Integer number : numbers) {
      for(int i=0; i < sortedList.size(); i++) {
         if (number < sortedList.get(i)) {
            sortedList.add(i, number);
            continue originalList;
         }
      }
      sortedList.add(sortedList.size(), number);
   }

   return sortedList;
}

 

 - 삽입 정렬은 새로운 리스트를 생성하고 해당 리스트를 반환

- ArrayList 클래스를 사용 했다면 중간에 원소를 추가할 경우 처리 속도가 많이 느렸을 것이다. ArrayList는 배열을 이용하므로 리스트의 앞이나 중간에 원소를 삽입하면 그 뒤에 있는 모든 원소들을 한칸씩 뒤로 이동시켜야 한다.

 - 버블정렬보다 좋은점은 순서대로 리스트를 확인하느라 불필요한 정렬을 할 필요가 없다.

 - 삽입 정렬 알고리즘은 새로운 리스트를 반환하므로 정렬하려는 리스트의 두배 정도 되는 저장 공간이 필요 반변에 버블정렬은 스왑할 때 사용하는 임시 변수만 이용하면 된다.

 

참고서적

 - JAVA 프로그래밍 면접 이렇게 준비한다  - 저 노엘 마크엄, 역 정원천