[JAVA] 삽입정렬(Insertion Sort) 알고리즘

삽입정렬(Insertion Sort)

삽입정렬은 아직 정렬되지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입해 가며 정렬하는 방식입니다.

삽입정렬 또한 앞의 두 알고리즘과 같이 시간복잡도O(n^2)를 갖습니다. (for문이 2번 있기 때문입니다. )

왼쪽원소부터 정렬되며 오른쪽 원소들을 왼쪽 정렬된 원소들과 비교하며 적절한 위치에 삽입합니다.

//삽입정렬(insertion sort)
 public void insertionSort(int[] array) {
     int size = array.length;
      
     for(int i=1; i < size; i++) {
         int k = i;
          
         for(int j=i-1; j >= 0; j--) {
             if(array[k] < array[j]) {
                 swap(array, k, j);
                 k = j;
             }
         }
     }
 }
  
 public void swap(int[] array, int i, int j) {
     int temp = array[i];
     array[i] = array[j];
     array[j] = temp;
 }

public void insertionSort2(int a[], int size) {
            
 
        for (i = 1; i < size; i++) {
            j = i;
            temp = a[i];
            while ((j > 0) && (a[j - 1] > temp)) {
                a[j] = a[j - 1];
                j--;
            }
            a[j] = temp;
            System.out.printf("\n 삽입정렬 %d 단계 : ", i);
            for (t = 0; t < size; t++) {
                System.out.printf("%3d", a[t]);
            }
            System.out.println();
        }
    }

-------------------- append ---------------------

더 좋은코드가 있어서 추가합니다.

public List<Integer> insertSort(final List<Integer> numbers){
        final 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;
    }

이 삽입정렬코드에서 살펴봐야할 점은 새로운 리스트를 생성하고 해당 리스트를 반환한다는 점과 삽입정렬에서 반환하는 리스트는 LinkedList 클래스의 인스턴스라는 것입니다.

ArrayList를 사용했더라면 리스트 중간에 원소를 추가할 경우 처리 속도가 많이 느리므로 LinkedList를 사용하였습니다.

(ArrayList는 중간에 원소를 삽입하면 모든 원소를 한 칸씩 뒤로 이동시켜야 합니다.)

최악의 경우

=> O(n^2)

최선의 경우

=> O(n)

버블 정렬과 마찬가지로 최악의 경우 알고리즘의 성능은 O(n^2)이 됩니다. 이미 정렬된 리스트를 다시 정렬하는 경우라면 매번 원소를 삽입할 때마다 새 리스트의 끝까지 반목문을 실행해야 되기 때문입니다. 반대로 역순으로 정렬된 리스트를 정렬하는 경우라면 앞에있는 원소를 새리스트에 넣으므로 O(n)의 성능을 가집니다.