삽입정렬

16 Jan 2021 in Algorithms

알고리즘 설명

IDEA : key 값과 정렬된 리스트를 입력으로 받아 그 값을 알맞은 위치에 삽입하는 정렬

1. key 값을 하나씩 추가하며 정렬
2. n개의 원소를 가진 배열을 정렬한다고 하면, 0개에 배열에 첫번째 원소값 추가, 한개의 배열에 두번째 원소값 추가.. 이렇게 반복

성능 분석

• 최악의 경우 : an^2 +bn + c
• 최선의 경우 : 시간 복잡도 : an+b
• 평균의 경우 : 시간 복잡도 : Θ(n^2), 공간 복잡도 : Θ(n)

JAVA 코드

public static void insertion_sort() {
    int[] ary = {11,3,5,2,12,3,22};

    for(int i =0;i<ary.length-1;i++) {
        int insert = ary[i+1];

        for (int j=0;j<=i;j++){	
            if (insert<ary[j]){
                for(int k=i;k>=j;k--){
                    ary[k+1]=ary[k];
                }

                ary[j]=insert;
                j=i+1; // 이걸 안해줘서 계속 오류남.
            }
        }
    }


    System.out.println(Arrays.toString(ary));
}

PYTHON 코드

ary= [13,24,1,2,734,23,12,5]

for i in range(1,len(ary)-1):
    for j in range(0,i):
        if ary[j]>ary[i+1]:
            tmp = ary[i+1]
            while j<=i:
                ary[i+1]=ary[i]
                i-=1
            ary[j]=tmp
        break;
print(ary)