알고리즘 [Algorithm] - 삽입 정렬 (3) (C, Python)

삽입정렬

이번에는 삽입 정렬에 대해 알아보자. 삽입정렬이란 각 숫자를 적절한 위치에 삽입하는 것이다. 먼저 소스코드를 확인해보자.

---

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요.

1 10 5 8 7 6 4 3 2 9

---

 

#include <stdio.h>

int main(void){
	int i,j,temp;
    int array[10] = {1,10,5,8,7,6,4,3,2,9};
    for(i=0;i<9;i++){
    	j=i;
    	while(j >=0 && array[j] > array[j+1]){
        	temp = array[j];
            array[j] = array[j+1];
            array[j+1] = temp;
            j--;
        }
    }
	
    for (i=0;i<10;i++){
    	printf("%d",array[i]);
    }
    return 0;
}

삽입 정렬은 기본적으로 '정렬이 되어있다고 가정'한다는 점에서 특정한 경우에 따라서 굉장히 빠른 속도를 자랑한다. 반복문이 두 번 들어가 있으므로 삽입 정렬의 시간 복잡도는 O(N^2)이다. 

i=0일때, 10은 1의 앞과 뒤, 즉 _ 1 _ 두 곳에 들어갈 수 있는데 오른쪽 자리에 삽입되어야 오름차순 정렬이 된다.i=1일때, 5는 _ 1 _ 10 _ 세 곳에 들어갈 수 있는데 1과 10 사이에 들어가야 한다.

 

거의 정렬이 되어있는 경우를 생각해보자.

---

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요.

2 3 4 5 6 7 8 9 10 1

---

삽입정렬은 필요한 경우에만 삽입을 진행하므로 데이터가 거의 정렬된 상태에 한해서는 어떤 알고리즘보다도 빠르다는 특징을 가지고 있다.

 

파이썬

a = [1,10,5,8,7,6,4,3,2,9]

for i in range(len(a)-1):
  j = i
  while(a[j]>a[j+1]):
    temp = a[j]
    a[j]= a[j+1]
    a[j+1] = temp
    j -=1
a

 

---

이 글은 나동빈님의 실전 알고리즘 강좌 (Algorithm Programming Tutorial)를 참고해 작성하였습니다.

https://www.youtube.com/watch?v=qQ5iLNjpxSk&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz