swift 알고리즘 - 선택정렬 한방에 이해하기

swift 알고리즘 - 선택정렬 한방에 이해하기

 

선택정렬이란 정렬되지 않은 데이터들 가운데서 가장 작은 데이터를 차아 가장 앞의 데이터와 교환해 나가는 알고리즘 입니다.

배열 7, 4, 5, 1, 3 이라는 정렬되지 않은 데이터를 가지고 선택 정렬로 오름차순으로 정렬해 보겠습니다.

 

먼저 반복문은 총 몇개가 필요하며 필요한 준비물(변수)들은 어떤것들이 있을까요?

 

아래 그림을 보면서 하나씩 정해봅시다.

 

일단 선택정렬은 정해진 범위(데이터)에서 최소값을 찾을 찾는 것이 1차 목표이고 

이 1차 목표를 달성하기 위해서 비교라는 것을 해야 합니다.

 

비교라는 것을 하기 위해서는 두개의 무언가가 필요합니다. 그래야 비교를 할 수 있겠죠?

1회 전에서는 7 부터 4, 5, 1, 3 을 각각 비교 해서 최소 값을 계속 업데이트 합니다.

 

예를 들면 1회전에서 최소값을 7(기준숫자)로 정하고 4와 비교합니다. 7보다 4가 작으므로 최소값에는 4가 할당됩니다. [비교 1번]

 

그 다음 최소값인 4와 5를 비교합니다. 4가 여전히 작기 때문에 최소값을 업데이트 하지 않습니다. [비교 2번]

 

그 다음은 최소값인 4와 1을 비교합니다. 4보다 1이 작으므로 최소값에는 1을 업데이트 합니다.[비교 3번]

 

그리고 마지막으로 최소값인 1과 3을 비교 합니다. 최소값 1이 더 작기 때문에 최소값을 업데이트 하지 않습니다.[비교 4번]

 

1회전에서 최소값 1을 찾았습니다.

그럼 최소값 1의 위치와 배열의 첫번째 요소 7 위치를 서로 변경해줍니다.

이로써 1회전이 종료 되었습니다.

 

여기서 우리가 주목해야할 부분은 하나의 회전(반복문)이 완료될 때마다 하나의 숫자가 정렬이 완료된다는 것입니다. 그리고 이 정렬된 숫자는 다음 회전에서는 비교 대상에서 제외 됩니다. - [반복문 1]

 

그리고 하나의 회전(반복문)안에서 비교를 여러번 (n번)합니다. - [반복문 2]

 

 

 

1회전 7(기준숫자), 4, 5, 1, 3 

7 비교 4 => 4

4 비교 5 => 4

4 비교 1 => 1

1 비교 3 => 1

 

7과 최소값 1 위치 변경

 

결과 1,4,5,7,3

 

-------------------

 

2회전 1,4(기준숫자),5,7,3

(1은 정렬이 완료되었으므로 제외)

 

4 비교 5 => 4

4 비교 7 => 4

4 비교 3 => 3

 

4와 최소값 3위치 변경

 

결과 1,3,5,7,4

 

------------------------

 

[바깥쪽 반복문] - 기준숫자를 스캔

위처럼 1회전, 2회전을 하는데 배열안 숫자의 개수 -1 번까지 반복을 합니다. 

아래 처럼 배열의 개수가 5개라면 4번만 반복해도 마지막 숫자는 자동으로 정렬이 되기 때문입니다.

그래서 바깥쪽 반복문은 배열안의 숫자 개수 - 1 번 반복합니다.

7, 4, 5, 1, 3 

 

[안쪽 반복문] - 비교대상 숫자를 스캔

그럼 안쪽 반복문은 몇번 반복을 할까요?

1회전에서는 총 4번 비교를 했고,

2회전에서는 총 3번 비교를 했습니다. 그럼

3회전에서는 2번 비교를 할 것이고

4회 전에서는 1번 비교를 할 것입니다.

 

그리고 더 이상 비교 할 숫자가 없기 때문에 안쪽 반복문은 종료가 됩니다.

 

그럼 바깥족 반복문과 안쪽 반복문이 계속 반복할 수 있는 조건은 각각 어떻게 될까요?

 

[바깥쪽 반복문의 조건]

바깥쪽 반복문은 배열의 길이 - 1 번 반복하기 때문에 아래 처럼 변수를 선언하고 while문을 작성합니다.

var outterLength = array.count - 1

//[바깥쪽 반복문]
while (0 < outterLength){

    outterLength -= 1

}

 

[안쪽 반복문의 조건]

안쪽 반복문은 1회전에서 4번 , 2회전에서 3번... 쭉 반복하다가 배열길이 -1 회전에서 1번 반복하고 종료됩니다.

그래서 위에서 선언한 바깥쪽 반복문의 길이를 이용해서 안쪽 반복문을 돌리고 반복문을 돌때 마다 - 1 해줍니다.

    var innerLength = outterLength
    while(0 < innerLength){
        
        print("innerLength : \(innerLength)")
        innerLength -= 1
    }

 

그럼 아래와 같이 이중 반복문을 작성할 수 있습니다.

 

var array = [7,4,5,1,3]
var outterLength = array.count - 1
// 기준이 되는 숫자
var outterIndex = 0

//[바깥쪽 반복문]
while (0 < outterLength){
    
    print("outterLength : \(outterLength)")
    
    //[안쪽 반복문]
    var innerLength = outterLength
    while(0 < innerLength){
        
        print("innerLength : \(innerLength)")
        innerLength -= 1
    }
    
    print("------- 끝 ---------\n")
    
    outterLength -= 1
}

 

출력을 해보면 outterLength 는 전체적으로 4번에 innerLength는 outterLength -1 번씩 반복 되는 것을 볼 수 있습니다.

 

outterLength : 4

innerLength : 4

innerLength : 3

innerLength : 2

innerLength : 1

------- 끝 ---------

 

outterLength : 3

innerLength : 3

innerLength : 2

innerLength : 1

------- 끝 ---------

 

outterLength : 2

innerLength : 2

innerLength : 1

------- 끝 ---------

 

outterLength : 1

innerLength : 1

------- 끝 ---------

 

 

 

이제 이어서 비교를 위한 기준 숫자와 비교 숫자들을 구하기 위해서 index를 구해야 한다. 왜냐면 배열에 직접 접근해서 숫자들을 가져와서 비교해야 되기 때문입니다.

 

기준이 되는 숫자는 바깥쪽 반복문에 아래 처럼 작성해준다. outterIndex를 작성해 주었습니다.

// 기준이 되는 숫자
var outterIndex = 0

 

비교 대상이 되는 숫자는 안쪽 반복문 밖에서 아래와 같이 작성해줍니다

innerIndex를 작성해 주었다. 여기서 주목할 점은 처음에는 outterIndex + 1 결과 값을 innerIndex에 할당해주고 안쪽 반복문을 돌때마다 innerIndex += 1 해주었다는 점입니다.

 

1회전에서 기준 숫자는 7입니다.

outterIndex 는 0 이므로 배열의 0번째에는 7이 있는것이 맞습니다.

그리고 비교 대상숫자들은 7보다 오른쪽에 있는 숫자들이므로, innerIndex = outterIndex + 1 ... innerIndex +=1 해주면서 배열의 오른쪽으로 이동 시키면서 비교 대상 숫자들에 접근합니다.

 

   var innerIndex = outterIndex + 1

    while(0 < innerLength){

        innerIndex += 1
    }

 

이어서 최소값을 찾아야 하므로 제일 처음의 최소 값은 기준 숫자로 할당하고 

그 후 비교하면서 최소 값을 업데이트 해줍니다.

최소 값을 찾으면 최소 값이 위치해 있는 index 값을 업데이트 해주고  바깥쪽 반복문이 끝날때 최소 값이 있는 위치와 기준 숫자의 위치를 변경해줍니다.

 

    // 최소값은 기준 숫자로 초기화
    var minNum = array[outterIndex]

    // 기준 숫자보다 작은 값이 존재하면 양수
    var minIndex = -1

    while(0 < innerLength){

        //비교 대상 숫자
        let compareNum = array[innerIndex]
        
        //최소값보다 비교 대상 숫자가 더 작으면
        //최소값 업데이트+최소값이 위치한 index 업데이트
        if(minNum > compareNum){
            minNum = compareNum
            minIndex = innerIndex
        }

        innerLength -= 1
        innerIndex += 1
    }

    //기준 숫자와 최소값 위치 변경
    if minIndex != -1 {
        let targetIndex = array[outterIndex]
        array[outterIndex] = minNum
        array[minIndex] = targetIndex
    }

 

전체 소스

var array = [7,4,5,1,3]
var outterLength = array.count - 1

// 기준이 되는 숫자
var outterIndex = 0


while (0 < outterLength){

    print("outterLength : \(outterLength)")

    var innerLength = outterLength
    var innerIndex = outterIndex + 1

    // 최소값은 기준 숫자로 초기화
    var minNum = array[outterIndex]

    // 기준 숫자보다 작은 값이 존재하면 양수
    var minIndex = -1

    while(0 < innerLength){

        //비교 대상 숫자
        let compareNum = array[innerIndex]
        
        //최소값보다 비교 대상 숫자가 더 작으면
        //최소값 업데이트+최소값이 위치한 index 업데이트
        if(minNum > compareNum){
            minNum = compareNum
            minIndex = innerIndex
        }

        innerLength -= 1
        innerIndex += 1 //비교 대상 숫자 오른쪽으로 한칸 이동
    }

    //기준 숫자와 최소값 위치 변경
    if minIndex != -1 {
        let targetIndex = array[outterIndex]
        array[outterIndex] = minNum
        array[minIndex] = targetIndex
    }


    print("------- 끝 ---------\n")

    minIndex = -1
    outterIndex += 1 //기준 숫자 위치 오른쪽으로 한칸 이동
    outterLength -= 1
}


print("array : \(array)")

 

결과

array : [1, 3, 4, 5, 7]