[python]파이썬 삽입정렬 알고리즘 (insertion sort)

Insertion Sort

삽입 정렬은 자료배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열부분과 비교하여, 자신의 위치를 찾아 삽입하는 정렬 알고리즘이다. 

삽입 정렬은 배열이 길어질수록 효율이 떨어지지만 구현이 간단하다는 장점이 있다. 

시간 복잡도는 O(n^2)이다. 

 

과정

1. 정렬이 안된 배열에서 제일 앞에 것을 선택 arr[i]
2. 정렬된 배열의 가장큰 원소부터 작은 원소 순으로 비교 arr[j]
3. 만약 arr[i]가 arr[j]보다 크다면  j+1위치에 arr[i] 삽입 
4. 만약 arr[j]가 arr[i]보다 크다면 arr[j+1]위치에 arr[j]를 옮겨서 한칸씩 뒤로 옮김 

 

파이썬 코드로 구현하면 이와 같다. 

def insesrtionSort(arr, n):
    for i in range(1,n):
        value = arr[i]
        j = i-1
        while(j >= 0):
            if(arr[j] > value):
                arr[j+1] = arr[j]
            else: 
                break
            j-=1
        arr[j+1] = value