삽입 정렬 insertionsort with swift

삽입 정렬은 적절한 인덱스에 삽입해주는 정렬입니다.

 

삽입 정렬은 두 번째 원소부터 시작해서 그 앞의 원소들과 비교해 삽입할 위치를 지정한 후, 지정한 자리에 원소를 삽입해 정렬합니다. 

또한 앞에 있는 원소는 이미 정렬되어 있다고 가정합니다.

 

코드를 살펴봅시다.

 

insertionsort with swift

arr는 우리가 정렬해야 할 배열이며, 1부터 7까지 정렬되지 않은 상태로 존재합니다.

arr의 크기는 7이고 인덱스는 0부터 6까지 입니다.

 

두 번째 원소부터 시작한다 했으니 for문은 인덱스 1부터 6까지 돌기 위한 용도이며,

while문은 for문의 i보다 아래 인덱스 중 큰 값이 있으면 swap하기 위한 용도입니다.

y는 아래 인덱스까지 모두 탐색하기 위한 변수입니다.

 

그럼 차근차근 살펴봅시다.

for loop에서 i가 1일 때 y가 1인 경우를 살펴봅시다.

while 조건문을 살펴보면 y>0, a[y] < a[y-1]이 있습니다.

(스위프트에서 콤마(,)는 &&와 동일합니다.)

 

y는 1이니 0보다 크고, a[1] < a[0]이 만족합니다.

그래서 1과 4를 즉 인덱스 1과 0을 swap 시켜줍니다.

그리고 y를 -1해 줍니다.

 

y가 0이 되어 while 조건문을 만족하지 않습니다. 

 

더 이상 while문이 실행되지 않으며, 두 번째 for loop가 실행됩니다.

 

for loop에서 i가 2일 때 y가 2인 경우를 살펴봅시다.

while 조건문을 살펴보면 y>0, a[y] < a[y-1]이 있습니다.

 

y는 2이니 0보다 크지만 a[2] < a[1]이 만족하지 않습니다.

여기서 바로 아래만 살펴보고 while문을 실행시키지 않아도 되는 이유는 앞에 있는 원소는 이미 정렬되어 있다고 가정하기 때문입니다.

 

더 이상 while문이 실행되지 않으며 세 번째 for loop가 실행됩니다.

for loop에서 i가 3일 때 y가 3인 경우를 살펴봅시다.

while 조건문을 살펴보면 y>0, a[y] < a[y-1]이 있습니다.

 

y는 3이니 0보다 크고 a[3] < a[2]이 만족합니다.

그래서 3과 5를 즉 인덱스 3과 2를 swap 시켜줍니다.

그리고 y를 -1해 줍니다.

 

y는 2이니 0보다 크고 a[2] < a[1]이 만족합니다.

그래서 3과 4를 즉 인덱스 2과 1을 swap 시켜줍니다.

그리고 y를 -1해 줍니다.

 

y는 1이니 0보다 크지만, a[1] < a[0]이 만족하지 않습니다.

 

더 이상 while문이 실행되지 않으며 네 번째 for loop가 실행됩니다.

 

위와 동일하게 작동합니다.

여기선 처음부터 while문에 조건문이 만족하지 않습니다.

 

더 이상 while문이 실행되지 않으며 다섯 번째 for loop가 실행됩니다.

위와 동일하게 작동합니다.

 

여섯 번째 for loop가 실행됩니다.

마지막 for loop에서도 처음부터 while문에 조건문이 만족하지 않아 어떠한 변화가 없습니다. 

 

여기까지 모든 for loop가 끝났습니다.

 

위 이미지는 각 for loop를 돌 때 array의 변화를 나타낸 것입니다.

앞은 정렬되어있다 가정하고 인덱스 1부터 시작해 알맞은 위치에 삽입해주는 게 보이시나요.

이것이 insertionsort의 핵심입니다.

 

간단한 정렬 알고리즘이지만, 시간 복잡도는 O(n^2)입니다.

하지만 앞은 이미 정렬되어있다 가정하기 때문에 거의 정렬되어 있는 배열이면 while문을 거치지 않아 다른 정렬들에 비해 비교적 더 빠르다는 장점도 가집니다.

 

 

2019/09/04 - [Development/Algorithm] - 선택 정렬 selectionsort with swift