[알고리즘 수업] 정렬

삽입정렬

• 기본 원리

1. 리스트를 두 부분으로 나눈다.
1. 정렬된 부분/ 미정렬 부분

2. 미정렬 부분에서 첫번째 요소를 선택한다.

3. 선택한 요소를 이미 정렬된 부분의 올바른 위치에 삽입한다.
1. 이때, 이미 정렬된 부분의 마지막 원소부터 비교하며 삽입할 위치를 찾아간다.

4. 올바른 위치에 삽입되면, 그다음 미정렬 부분의 첫번째 요소를 선택하여 이 과정을 반복한다.

5. 모든 원소가 정확한 위치에 삽입될 때까지 이 과정을 반복한다.

• 시간 복잡도 O(n)

• 평균 및 최악 시간 복잡도 O(n^2)

• 거의 정렬된 상태에서는 효율적임, but, 큰 규모의 리스트에서는 비효율적임.

def insertion_sort(A):
    N = len(A)
    for i in range(1, N):  
        newItem = A[i]
        loc = i - 1
        while loc >= 0 and newItem < A[loc]: 
            A[loc + 1] = A[loc]
            loc -= 1
        A[loc + 1] = newItem 
				if loc+1 != i:
					A[loc+1] = newItem
    return A