이전 포스팅에서는 선택 정렬에 대해 알아보았다.
https://ayaan-dev.tistory.com/6
이번 포스팅에서는 선택 정렬보다 구현하기 좀 더 복잡하지만 시간복잡도가 더 빠른 삽입 정렬에 대해 알아보겠다.
마찬가지로 아래 사이트에서 삽입 정렬 알고리즘을 시각화한 영상을 확인할 수 있다.
https://visualgo.net/en/sorting
array=[7,5,9,0,3,1,6,2,4,8]
for i in range(1,len(array)):
for j in range(i,0,-1):
if array[j]<array[j-1]: # 부등호를 반대로 하면 내림차순으로 정렬 할 수 있다.
array[j],array[j-1]=array[j-1],array[j]
else:
break
print(array)
인덱스 1부터 시작하여 왼쪽 요소들과 비교하면서 본인자리를 찾아가는 알고리즘이다.
STEP 0: i=1, j=1
array[1]<array[0] 이므로 SWAP(array[1],array[0])을 수행한다.
현재 array=[5,7,9,0,3,1,6,2,4,8]
STEP 1: i=2, j=2~1
array[2]>array[1] 이므로 swap을 진행하지 않고 끝낸다.
현재 array=[5,7,9,0,3,1,6,2,4,8]
STEP 2: i=3, j=3~1
array[3]<array[0] 이므로 0을 맨 앞으로 옮긴다.
현재 array=[0,5,7,9,3,1,6,2,4,8]
STEP 3: i=4,j=4~1
array[4]>array[0] and array[4]<array[1]이므로 array[4]를 0과 5 사이로 옮긴다.
현재 array=[0,3,5,7,9,1,6,2,4,8]
이와 같은 방식으로 마지막 인덱스 까지 첫 번째 반복문을 돌면서 숫자가 낑겨 들어갈 자리를 찾아 넣는 정렬방법이다.
포스팅과 첨부한 링크를 보고도 이해가 잘 되지 않는다면 아래 유튜브 링크를 참고하길 바란다.
시간 복잡도의 경우 이중 for문 임으로 O(N2)이다.
다만, 삽입 정렬의 시간복잡도는 큰 특징이 있다. 최선의 경우 O(N)이라는 것이다.
최선의 경우란 배열이 모두 이미 정렬되어 있는 경우다.
이미 정렬이 되어 있는 경우 이중 for문의 안쪽 for문에서(for j in range(i,0,-1)) if array[j]<array[j-1]이 매번 false가 나오기 때문이다.
따라서 삽입 정렬의 경우에는 주어지는 배열이 거의 정렬이 되어있는 상태로 주어져서 몇가지 인덱스에 대해서만 위치수정이 행해지면 될 경우 매우 효율적인 알고리즘이 될 수 있다.
일반적으로 빠르다고 알려진 퀵 정렬보다도 더 빠를 수 있다.(퀵정렬의 경우 O(NlogN))
선택 정렬(Selection Sort) (0) | 2022.12.31 |
---|
댓글 영역