Swift) 삽입 정렬(Insertion Sort) 구현 해보기

 

 

 

안녕하세요 :) 소들입니다!!!!

이번 포스팅에선 알고리즘 중에서 삽입 정렬을 Swift로 구현해보려고 해요!

어렵지 않으니 이 또한 후딱 해치웁시다!!!!!!!!!!

모든 포스팅은 편의 말투로 합니다~!!

 

 

 

 

1. 삽입 정렬이 뭐야?

 

삽입 정렬 역시 정렬을 하기 위한 방법 중 하나임!

일단 선택 정렬의 방식은

 

① 정렬은 두 번째 요소부터 시작한다

② 기준이 되는 index와 인접한 index부터 비교하며 삽입한다

③ 삽입이 끝나면, 기준 index의 다음 index를 기준으로 잡는다

 

자 이론은 이게 끝인데..ㅎㅎㅎㅎ

방금까지 버블이고 선택이고 오질라게 쉬웠었음 그쵸...?

근데 이거 읽는 순간 집가고 싶어짐~~ 나 한국말 모르네..

ㄴㅇㄱ 상상도 못한 외국인

 

사실 insert, remove를 이용해서 삽입 삭제를 해도 되지만,

더 간단한 방법은 swap 함수를 이용하는 것임!!

 

 

***

기준 index는 1부터 시작하며, 기준 index에 인접한 이전 index부터,

기준 index의 값보다 작은 놈을 만날 때까지 swap하다가, 작은놈을 만나면 종료

한 번 스캔이 끝나면, 기준 index의 다음 index를 기준으로 잡고 다시 스캔 진행

***

 

 

사실 이론으로 봐서 어려운 거지, 그림으로 봐보자 :)

만약 [5, 3, 8, 1, 2] 라는 배열을 삽입정렬 할 경우,

 

 

 

 

이렇게 동작하는 것임..! 이해가 됐기를.. :)

만약 나보다 큰 값이 없으면 0번째 인덱스까지 swap되고 반복문에 의해 종료될 것임

이번 건 구현 전 생각하기 하면 더 헷갈리실 거 같아서,

바로 코드로 갈게용

 

 

 

 

2. 코드로 구현해보기

 

 

func insertionSort(_ array: inout [Int]) {
    for stand in 1..<array.count {
        for index in stride(from: stand, to: 0, by: -1) {
            if array[index] < array[index - 1] {
                array.swapAt(index, index - 1)
            } else {
                break
            }
        }
    }
}

 

 

이렇게 짜면 됨!!! :)

설명은 대따 어려웠는데 코드는 정말 쉽죠!?????

 

범위를 stride로 준 것은, 만약 stand가 3일 경우에

2번 index ▶ 1번 index ▶ 0번 index

이렇게 내림차순으로 비교를 해야하기 때문에 , 코드를 좀 더 간결하게 하려고 그런 것임!

 

 

 

 

3. 삽입 정렬의 시간 복잡도

 

입력 값 n은 배열의 요소 갯수로 볼 때,

요소 갯수만큼 도는 반복문 안에,

요소 갯수만큼 도는 반복문이 돌기 때문에

 

O(n^2)

 

으로,

구현이 쉽고 간단한 장점이 있지만.. 이또한 느림

근데 버블 정렬, 선택정렬 보단 빠르다고 하나.. 시간 복잡도 상으로는 셋 다 또이또이 함!!

(왜냐면 빅오 표기법은 최악의 경우를 나타내서 그럼)

 

 

 

 

.

.

.

이론은 어렵지만, 실제 구현해보면 쉬운 삽입 정렬 알고리즘 끝! :)

피드백, 궁금증은 언제나 댓글 주세여~~ 20,000!