[알고리즘] 패스트캠퍼스 챌린지 17일차

삽입정렬(Insertion Sort)

• 삽입 정렬은 두 번째 인덱스부터 시작
• 해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사
• 이를 key 값이 더 큰 데이터를 만날때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동

 

[연습]

데이터 4개일 때 삽입정렬

[5, 3, 2, 4]

[#1]

기준: 3, 3 앞의 데이터들(5)과 비교 -> 5와 바꾼다 => [3, 5, 2, 4]

[#2]

기준: 2, 2 앞의 데이터들(5, 3)과 비교 -> 5보다 작음, 3보다 작음, 3은 맨 앞이므로 비교 끝 => [2, 3, 5, 4]

[#3]

기준: 4, 4 앞의 데이터들(5, 3, 2)과 비교 -> 5보다 작음, 3보다 큼 => [2, 3, 4, 5]

 

규칙 찾아서 직접 Swift로 함수 만들고 테스트도 해봤다.

강사님과 코드가 조금 다르지만 결과는 동일하다.

기준이 되는 데이터의 index부터 그 앞쪽의 데이터와 비교해야 된다는 것이 조금 구현하기 까다로운 정도..?!

덕분에 오랜만에 stride(from:;to:;by:) 사용해봤다. ㅎㅎ

 

func insertionSort(array: [Int]) -> [Int] {
    var resultArray: [Int] = array
    
    for standard in 1..<resultArray.count {
        for index in stride(from:standard, to:0, by:-1) {
            if resultArray[index] < resultArray[index-1] {
                resultArray.swapAt(index, index-1)
            } else {
                break
            }
        }
    }
    
    return resultArray
}

 

삽입정렬 시간복잡도

• 반복문이 두 개 O(𝑛²)
  • 상세하게 계산될 경우, n * (n-1) / 2
• 완전정렬되어있는 경우에는 O(n)

 

정렬 알고리즘의 시간복잡도는 다 비슷비슷한 것 같다.

 

강의 인증샷!!

 

오늘까지 버블정렬, 선택정렬, 삽입정렬까지 해서 정렬 알고리즘 세가지 강의 끝!

추석 연휴지만 빠짐없이 강의 다 들었다.

처음 시작할 때 추석연휴때면 30일 데일리 챌린지 실패할 줄 알았는데.. ㅎ... 신기하다.

내일부터는 재귀용법.

 

 

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.