삽입정렬Insertion Sort

삽입정렬Insertion Sort

삽입정렬Insertion Sort알고리즘의 특징

**gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html 많은부분 참고했습니다.

• 손안의 카드를정렬하는 방법과 유사.

• 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 부분과 비교하여 자신의 위치를 찾아서 삽입한다. 

• 매순서마다 원소를 삽입할 수 있는 위치를 찾아서 해당 위치에 넣는다. 

  • 두번째 자료(index = 1 )부터 시작한다

  • 1번째 값이 0번째값보다 작으면 1번째 값을 0번째에 넣고 0번째 값을 1번째 자리에 넣는다.

  • 여기까지하면 인덱스 0,1이 정렬된 자료가된다. 

  • 2번째 값을 0,1번째 값과 비교한후 적절한 자리에 넣고 해당 자리의원소들은 뒤로 한칸씩 밀린다. 

  • 여기까지하면 인덱스 0,1,2가 정렬된 자료가 된다. 

  • 3번째 값을 정렬된 자료와 비교하여 적절한 자리에 넣고 원래 자리에있던 원소들은 한칸씩 뒤로간다. 

  • 여기까지하면 0,1,2,3이 정렬된 자료가된다. 

  • n까지 반복하면 0부터 n까지 정렬이 완료된다.

• 장점

  • 안정한 정렬방법이다.
  • 자료의 수가 적을경우 알고리즘이 매우 간단하다. 
  • 대부분 정렬이 된 상태일경우 효율적이다. 

• 단점

  • 자료의 이동이 많다. 
  • 자료가 많은 경우 적절하지못하다. 

알고리즘 예제

31      25     12    22     11 처음 상태.
31     [25]    12    22    11 두 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다.
<25> 31    [12]    22    11 세 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다.
<12> 25    31    [22]    11 네 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다.
12    <22>  25    31    [11] 마지막 원소를 부분 리스트에서 적절한 위치에 삽입한다.
<11>    12    22    25    31 종료.}

삽입정렬Insertion Sort 코틀린 코드

fun insertionSort(arr: IntArray) : IntArray{
    var j = 0
    var key = 0


    for (i in 1 until arr.size) { //0번째 자료는 정렬된것으로 간주한다.
        key = arr[i]

        j = i
        while (--j >= 0 && key < arr[j]) {
            arr[j+1] = arr[j]
            arr[j] = key
        }


    }

    return arr
}

• 시간복잡도
  • 최선의경우
    • 비교횟수
      • 이동이 없이 1번의 비교만 이루어진다.
    • O(n)
  • 최악의 경우
    • 비교횟수
      • 모든 자료를 비교해야하기때문에 n개의 자료를 정렬할경우 n, n-1, n-2 ... 1 번의 비교를해야한다.
      • 비교는 O(n^2)번이라고할 수 있다.  
    • 교환횟수
      • 매번 교환이 이루어지기때문에 n, n-1, n-2 ... 1번의 교환이이루어진다. 
      • 교환이 O(n^2)번 이루어진다고할 수 있다.
    • 시간복잡도
      • O(n^2)