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

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

 

이번 포스트에서는 삽입 정렬을 알아보겠습니다.

 

 

삽입 정렬이란?

 

삽입정렬이란 버블, 선택 정렬처럼 데이터를 정렬하기 위한 방법중 하나로, 다음과 같은 과정을 걸치게 됩니다.

 

두번째 정렬부터 시작하여, 시작된 요소의 앞에있는 요소들과 비교하며 

 

선택된 요소의 값이 더 작다면 위치를 바꾸고,

 

해당 과정을 자신보다 값이 작은 요소를 만나기 전까지 반복한다.

 

 

자 글보다는 쉽게  에시로 알아봅시다. 이전 포스팅과 마찬가지로 아래와 같은 배열이 있습니다.

 

 

 

1. 두 번째 요소인 3부터 시작하여서 앞의 값 4와 비교 -> 4 > 3 이므로 위치 변경

 

2. 시작 지점인 3이 제일 앞 위치에 도착하여서 루프 종료

 

3. 세 번째 지점인 9부터 시작 앞의 값 4와 비교 -> 4 < 9 이므로 위치 변경 x

 

4. 시작 지점인 9가 자신보다 값이 작은 요소를 만났으므로 루프 종료

 

5. 네 번째 지점인 1 부터 시작 앞의 값 9와 비교 -> 9 > 1 이므로 위치 변경

 

6. 시작 값인 1과 그 다음 인접 요소인 4와 비교 -> 4 > 1 이므로 위치 변경

 

7. 시작 값인 1과 그 다음 인접 요소인 3와 비교 -> 3 > 1 이므로 위치 변경

 

8. 시작 값인 1이 배열의 제일 앞으로 이동했으므로 루프 종료

 

9. 다섯 번째 지점(마지막)인 6부터 앞의 값 9와 비교 -> 9 > 6 이므로 위치 변경

 

10. 시작 값인 6과 다음 인접 요소인 4와 비교 -> 4 < 6 이므로 위치 변경 x

 

11. 시작 값인 6이 자신보다 값이 작은 요소를 만나서 루프 종료 -> 마지막 배열의 요소까지 루프가 실행됐으므로 정렬 종료

 

 

우와.. 진짜  이처럼 자신보다 작은 값을 만날때 까지 계속 swap이 반복되며 모든 요소가 실행되면 종료됩니다.

 

실행과정을 보면 너무 길고 복잡해보이지만 코드로 보면 버블, 선택 정렬처럼 2중for문을 사용하면서 간단합니다 :)

 

물론 똑같이 시간복잡도는 O(n^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는 처음 보신 분들이 계실탠데 간단하게 설명하자면

 

stride(from: a, to: b , by: c)는 a에서 b까지 c만큼 단계별로 이동하는 것입니다. (b에 도착 전까지 반복합니다.)

 

따라서

 

stride(from: stand, to: 0, by: -1) 는 stand부터 1번째 인덱스까지 인덱스를 1씩 감소 시킨다는 뜻입니다.