[Algorithm, Swift] 선택정렬, 삽입정렬 소스코드로 이해하기

안녕하세요 이웃님들 ~~

요즘은 제가 정렬을 공부하고 있는데요!

나동빈님의 이것이 코딩테스트다 라는 책을 참고해서 공부를 하고 있어요.

오늘은 가장 원초적인(?) 정렬인 선택정렬과 삽입정렬을 같이 알아보도록 해요~~!!

열정렬정렬정렬??? 한사랑 산악회도 우리민족이었군요

정렬 정렬 정렬 ~!!

정렬 알고리즘이란?

정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것
정렬 알고리즘으로 정렬을 하면 '이진 탐색'이 가능해집니다. 이진 탐색을 하기 위한 전처리 과정입니다.

정렬 알고리즘의 종류

• 선택 정렬
• 삽입 정렬
• 퀵 정렬
• 계수 정렬
• 기타 등등

선택정렬

데이터가 무작위로 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 것을 반복하면 어떻게 될까?

선택정렬 소스코드

for i in 0...array.count - 1 {
    var minIndex = i //가장 작은 원소의 인덱스
    for j in i + 1..<array.count {
        if array[minIndex] > array[j] {
            minIndex = j

        }
    }
    var frontNum = array[i]
    var changeNum = array[minIndex]
    array[i] = changeNum
    array[minIndex] = frontNum
}

결과값을 프린트 해보면 0부터 9까지 정렬된 것을 확인할 수 있다.

선택정렬의 시간복잡도

선택정렬은 N개의 원소가 있는 배열에서 연산횟수가 N +

(N - 1) + (N - 2) + ... + 2 가 되어서
근사치로 N X (N + 1) / 2 로 가정하면 대략적으로 O(N^2)번 정도라고 볼 수 있다. 데이터 개수가 1만개 이상이면 가능하면 선택정렬은 하면 안되겠다.

삽입정렬

데이터를 하나씩 확인해서 적절한 위치에 삽입하면 어떨까? 선택정렬에 비해 실행 시간 측면에서 더욱 효율적일 것이다. 삽입정렬은 특히 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 매우 유리하다. 선택정렬은 데이터의 상태와 상관없이 무조건 모든 원소를 바꾸고, 삽입 정렬은 바꿔야 할 때만 바꾼다.

삽입 정렬 소스코드

삽입정렬은 첫번째 원소는 정렬하지 않고 시작한다. 이미 정렬되어 있다고 가정을 하고 있기 때문이다.

두번째 원소를 첫번째 원소와 비교한다. 더 작다면 앞으로 넣어주고, 더 크면 그대로 둔다. 세번째 원소도 이런식으로 크기를 비교해 들어가야 할 곳에 넣어준다. 이렇게 적절한 위치에 삽입하는 과정을 반복하면 정렬이 완료된다.

특징으로는, 왼쪽으로 옮겨가면서 자신보다 작은 원소를 만나면 그 자리를 자기 자리로 하기 때문에 그 이후에 뒷 부분은 연산할 필요가 없다.

var insertionArray = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in 1..<insertionArray.count {
    for j in stride(from: i, to: 0, by: -1) {
        if insertionArray[j] < insertionArray[j - 1] {
            insertionArray.swapAt(j, j - 1)
        } else {
            break //자기보다 작은 숫자 나오면 멈춤
        }
    }
}

 

 

어떤가요~~ 한번 직접 정렬을 해서 결과값을 출력해서 확인을 꼭 해보세요! 

삽입 정렬을 할 때 필요한 stride, swapAt 메서드도 알아두면 참 좋을 것 같아요~!!

 

프로젝트에서 소스코드를 받아보시려면 제 깃헙에 열려있습니다 :) 

Star 해두시면 도움되는 많은 자료가 올라옵니다! 감사합니다.

GitHub - AnnaBaeTofuMom/TodayILearned: 새롭게 배운 것을 기록합니다, 나의 언어로 새로 씁니다.