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

Jay·2021년 3월 7일
0

알고리즘-Concept

목록 보기
7/15
post-thumbnail

삽입 정렬 !?

  • 손 안의 카드를 정렬하는 방법과 같다.
  • 새로운 카드를 기존의 정렬된 카드 사이에 올바른 위치게 끼워 넣는다.
  • 2번째 원소부터 시작해서 그 앞(원소)와 비교하며 삽입할 위치를 찾고, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다.
  • 최선의 경우, O(N)이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될만큼 좋은 정렬 알고리즘이다.

로직

  1. 정렬은 2번째 위치의 값을 standard에 저장한다.
  2. standdard와 이전에 있는 원소들과 비교하여 자리를 바꾸며 삽입해 나간다.
  3. 1번으로 돌아가서 다음 위치의 값을 standard로 지정하고 이 과정을 반복한다.
private static void insertionSort(int[] arr){
	for(int i=1; i<arr.length; i++){
    	int standard = arr[i];
        int index = i-1;
        
        //넣을 위치를 찾았으니 그 뒤의 원소들을 한칸씩 뒤로 미는 과정
        while((0<=index) && standard < arr[index]){
        	arr[index+1] = arr[index];
            index--;
        }
        
        arr[index+1] = standard;        
    }

}
  • 첫 번째 원소 앞(왼쪽)에는 원소가 없기에 두번째 원소부터 탐색을 시작한다.
  • standard에 임시로 기준 위치 값을 저장하고, index에는 기준 위치 이전의 위치를 저장한다.
  • 이전 위치를 가리키는 index는 음수가 되지 않고, 이전 위치 값이 1번에서 선택한 기준 위치의 값보다 크다면 오른쪽으로 한 칸씩 이동 시켜준다. 그리고 index가 더 이전 위치를 가리키도록 한다.
  • 2번에서 반복문이 끝나고 난 뒤, index에는 standard가 들어갈 위치의 인덱스-1의 위치를 가리키게 된다.
  • 2번의 반복문에서 standard보다 큰 값들의 위치를 한 칸씩 오른쪽으로 밀었기에..!
  • 그래서 (index+1) 위치에 standard가 들어갈 위치이기에 삽입해준다.

시간복잡도

  • 최악의 경우(역으로 정렬되어 있을 경우), 선택 정렬과 마찬가지로 (n-1)+(n-2)+...+2+1 -> n(n-1)/2 즉, O(N^2)이다.
  • 하지만, 모두 정렬 되어 있는 경우, 한 번씩만 비교하므로 O(N)의 시간 복잡도를 갖게 된다. 또한, 이미 정렬되어 있는 배열에 자료를 하나씩 삽입/제거하는 경우에는 현실적으로 최고의 정렬 알고리즘이 되는데 탐색을 제외한 오버헤드가 매우 적기 때문이다.
  • 최선의 경우 : O(N)
  • 평균과 최악의 경우 : O(N^2)

공간 복잡도

  • 주어진 배열안에서 이루어지기에 O(N).

장점

  • 알고리즘이 단순하다.
  • 대부분의 원소가 이미 정렬되어 있는 경우, 매우 효율적일 수 있다.
  • 정렬하고자 하는 배열안에서 교환하는 방식이기에, 다른 메모리 공간이 필요하지 않다.
  • 선택 정렬이나 버블 정렬에 비해 상대적으로 빠르다.

단점

  • 비교적 많은 수들의 이동을 포함한다.
  • 비교할 수가 많고 크기가 클 경우에 적합하지 않다. (배열의 길이가 길수록 비효율적)
  • 평균화 최악의 시간 복잡도가 O(N^2)으로 비효율적이다.
profile
developer

0개의 댓글