[알고리즘] Insertion Sort 삽입 정렬

• 삽입 정렬

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

---

 

어떠한 리스트가 있다고 가정했을 때 두 번째 위치의 값부터 정렬을 시작할 것이다.

이를 key값이라고 부를것이다.

1. 해당 key값의 앞에 있는 데이터부터 비교하여 key값이 더 작다면, 데이터를 key값 뒤 인덱스로 복사
2. 이를 key값이 더 큰 데이터를 만날 때까지 반복
3. 큰 데이터를 만난 위치 바로 뒤에 key값을 이동

말로 풀어쓰면 정확하게 이해가 되지 않아 이를 그림을 보며 설명하겠다.

위 사진을 참고하면 먼저 리스트의 두 번째 값을 key값으로 정하고 이를 이전의 값과 크기를 비교하며 정렬해 주는 모습을 확인할 수 있다. 정렬이 완료되면 key값을 그다음 값으로 바꿔서 다시 정렬을 진행해 주면 된다. 모든 과정이 완료되면 리스트가 최종적으로 정렬된 모습을 볼 수 있다. 

• 파이썬 코드

def insertion_sort(arr):
	n = len(arr)
    for i in range(1,n):
    	j = i
        while j>0 and arr[j-1] > arr[j]:
        	arr[j-1], arr[j] = arr[j], arr[j-1]
            j -= 1
    return arr

 

위 코드에서 arr [j]를 key값이라고 생각하면 된다. 

• 알고리즘 수업 강의자료 슈도 코드

 

삽입정렬의 시간 복잡도는 O(N^2)으로 빠른 시간 복잡도는 아니다. 하지만 데이터가 정렬되어 있는 경우에는 훨씬 빠른 시간 복잡도 O(N)을 가진다. 

 

앞으로 2023 - 2학기 알고리즘 수업 시간에 배운 내용을 정리할 예정이다. 그리고 컴퓨터 네트워크, 운영체제 등 cs에 대해서도 정리하여 블로그에 글을 쓸 계획이다.