[알고리즘] insertionSort 삽입정렬(pseudo-code, 파이썬, Java)

삽입정렬

• 삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 정렬 방법이다.
• 현재 타겟이 되는 숫자와 이전 위치에 있는 원소들을 비교한다. (첫 번째 타겟은 두 번째 원소부터 시작한다.) 타겟이 되는 숫자가 이전 위치에 있던 원소보다 작다면 위치를 서로 교환한다. 그 다음 타겟을 찾아 위와 같은 방법으로 반복한다.

1. 배열을 0인덱스부터 i-1번째가 정렬되어 있을 때 for문을 돌아서 a[i]의 값보다 크다면 인덱스를 한칸씩 뒤로 이동해준다
2. 만약에 a[i]의 값보다 작거나 같다면 배열의 j+1번째 인덱스에 a[i]값을 넣어준다.
3. 이때 a[i]값은 미리 변수에 저장을 해둔다.

Pseudo-code

Algorithm insertionSort(a, n)
   for i = 1 to n
       temp = a[i]
       for  j = i-1 downto 0  
           if (a[j]> temp) then
              a[j+1] = a[j] //temp 값이 앞원소보다 작으므로 뒤로 민다
           else
              break
     // for loop을 끝까지 수행한 경우에 앞의 원소가 temp 보다 작다는 의미이므로 
     // temp 는 j+1 에 위치해야한다.
       a[j+1] = temp

Python

def insertion_sort(arr):
    for i in range(1,n):

Java

public class Insertion{
    public void sort(int[] arr){
        for(int i = 1; i < arr.length; i++){
            temp = arr[i];
            for(int j = i-1; j >= 0; j--){
                if(arr[j] >  temp){
                    arr[j+1] = a[j]; //앞자리 값이 key값보다 크다면 하나씩 이동
                }else{
                    break;
                }
            }
            arr[j+1] = temp //앞 원소가 temp 보다 작다는 의미이므로 비어있는 자리에 삽입
        }
    }
}

수행시간분석

• 최악의 경우

  • W(n): O(n^2) -> 역순으로 정렬되어있을 때

  • T(n) = 1 + 2 + 3 + … + n-1

    n = (n-1)(n)/2 -> O(n^2)

• 최선의 경우

  • B(n) : O(n) -> 정렬되어 있는 입력

평균적인 시간 복잡도 -> Θ(n^2)