[알고리즘/삽입정렬] #Insertion_Sort / in Python

삽입 정렬

- 숫자를 오름차순으로 정렬하는 프로그램 

---

arr = [3, 4, 5, 1, 2]이라는 리스트가 있을 때 이것을 어떻게 오름차순으로 정렬할까? 

삽입정렬은
앞의 있는 원소들이 이미 정렬되어있다고 가정을 한다 라는 특성이 있다.

즉, 하나의 원소를 선택 후 삽일 할 위치에 보내는 방법을 삽입 정렬이라고 한다.

#1 [1, 3, 4, 5, 2] #1 선택해 맨 처음 자리로 이동
[(1) _, 3, 4, 5, (1), 2] 빈 공간이 있다고 생각하고 이동
#2 [1, 2, 3, 4, 5] #2 선택해 공간의 위치에 이동 1과 3 사이
[_, 1, (2)_, 3, _, 4, 5, (2)]
#3 [1, 2, 3, 4, 5] #3 선택해 자리 이동 //변화 없음...
#4 [1, 2, 3, 4, 5] #4 선택해 자리 이동 //변화 없음... >>>

순서로 진행된다.

---

코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

''' i, j >>> 배열에 있는 원소 반복적으로 탐색 '''   def insetion_sort(arr):     for i in range(len(arr)-1):         j = i         while arr[j] > arr[j+1]:             arr[j], arr[j+1] = arr[j+1], arr[j]             j -= 1     return print(arr)   if __name__ == '__main__':     arr = [1,10,4,2,9,8,3,5,6,7]     insetion_sort(arr)

선택 정렬의 코드는 조건이 붙어서 생각보다 난해했지만, 버블 정렬과 삽입 정렬은 직관적이다.

 빈 공간에 넣어준다는 생각으로 알고리즘이 진행된다.
#집합의 크기가 1씩 줄어든다
#10 + 9 + ... + 2 + 1
#N * (N+1) / 2
#N^2
#실제 수행 결과는 선택 정렬과 버블 정렬보다 빠르다
#이미 앞은 정렬되어 있다고 가정되었기 때문에
#정렬 중 이미 정렬되어있는 것 이 있을 수 있다.
#"#"거의 정렬된 상태" 라면 가장 효율적이다.

 시간 복잡도는 선택 정렬과 버블 정렬과 같으나 정렬되어 있는 상태가 있다면,
연산을 하지 않음으로 상대적으로 빠르다고 할 수 있다.

 #빅오(Big O) 표기법
삽입 정렬의 시간 복잡도는 O(N^2)가 된다.