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

선택정렬(Selection Sort)

1. 주어진 데이터 중, 최소값을 찾음
2. 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함
3. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함

=> 최소값을 찾아서 앞쪽에 갖다놓는 거군!!

 

 

[연습]

데이터 4개일 때 선택정렬

[5, 4, 3, 1]

[#1]

기준: 5, 나머지 4, 3, 1 중 가장 작은 값을 찾는다(1) -> 5와 바꾼다 => [1, 4, 3, 5]

[#2]

기준: 4, 나머지 3, 5 중 가장 작은 값을 찾는다(3) -> 4와 바꾼다 => [1, 3, 4, 5]

[#3]

기준: 4, 나머지 5.. >> 가장 큰 데이터가 마지막에 위치하므로 비교할 게 없음

 

 

오늘도 노트에 적어보면서 생각해보고, Swift로 직접 작성해봤다.

테스트도 성공!!

func selectionSort(array: [Int]) -> [Int] {
    var resultArray = array
    for standard in 0..<resultArray.count-1 {
        var smallest = standard
        for index in standard+1..<resultArray.count {
            if resultArray[smallest] > resultArray[index] {
                smallest = index
            }
        }
        resultArray.swapAt(smallest, standard)
    }
    
    return resultArray
}

 

선택정렬 시간복잡도

• 반복문이 두 개 O(𝑛²)
  • 상세하게 계산될 경우, n * (n-1) / 2

 

노트에 직접 적어본 사진 ㅎㅎ 글씨 너무 못쓴당;;

 

선택정렬은 이해하기에도, 코드로 구현하기에도 크게 어렵지 않았다. ㅎㅎ

강의 보고 원리 이해하고 직접 Swift로 코드 작성해보고 테스트해보고 강의를 이어봤다.

 

오늘은 추석 당일~~!!~

명절에 공부하다니 수능준비할 때 이후로 처음인듯 ㅎ;;

명절연휴에도 잘 듣고 있으니까 끝까지 열심히 들어야지..

 

https://bit.ly/37BpXiC

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

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