swift 알고리즘 - 삽입정렬 한방에 이해하기

swift 알고리즘 - 삽입정렬 한방에 이해하기

 

삽입정렬 정의

삽입 정렬이라고 하면 어떤 데이터를 어디에 삽입을 하면서 정렬을 할까? 라는 생각을 할 수 있습니다.

먼저 어떤 데이터를 삽입을 할까요? 바로 정렬이 안된 데이터 입니다. 삽입 정렬에서 정렬이 안된 데이터를 key라고 부릅니다.

그럼 어디에 데이터를 삽입할까요? 바로 정렬이 된 데이터(배열) 입니다.

 

삽입정렬을 한마디로 정의하면 정렬이 안된 데이터를 정렬이 된 배열 속으로 삽입하는 것이라고 할 수 있습니다.

 

그럼 아래와 같이 정렬이 안된 [5,3,4,7,2] 라는 배열 데이터가 주어졌습니다.

이 데이터를 이제 삽입 정렬을 이용해서 정렬해야 합니다. 

 

어떻게 해야 할까요?

삽입 정렬에서 데이터를 정렬하기 위해 몇 가지 규칙을 정합니다.

 

[1] 배열의 제일 첫번째 데이터는 정렬이 완료되었다고 가정! 한다. 네, 그렇습니다. 삽입 정렬은 정렬이 안된 데이터를 정렬된 배열에 삽입하는 것인데 최초 1회전때는 정렬된 데이터가 하나도 없기 때문에 배열의 첫번째 요소를 정렬이 되었다고 가정을 하는것입니다.

 

[2] 그럼 정렬을 해야 될 데이터는 두번째요소 부터 시작을 한다. (key가됨)

 

[3] key 숫자가 왼쪽의 정렬된 숫자와 비교를 진행합니다. key 숫자가 더 작으면 서로 위치를 변경하고, key 숫자가 더 크면 그대로 둡니다.

 

 

[바깥쪽 반복문]

자 그럼 위의 내용을 토대로 코드를 작성해 보도록 하겠습니다.

먼저 배열의 숫자들을 처음부터 끝까지 비교를 해야 되므로 반복문을 써야 합니다. 위 그림에서 1회전, 2회전, 3회전에 해당되는 바깥쪽 반복문이라고 할 수 있습니다. 배열의 제일 앞에 위치한 숫자는 정렬이 된것으로 가정하므로 5를 제외한 3,4,7,2 총 4개의 숫자가 삽입 정렬의 대상이 되므로 바깥쪽 반복문은 총 4번 스캔이 됩니다. 

 

그럼 바깥쪽 반복문은 배열의 개수 - 1 이라는 식으로 구할 수 있습니다. 이 반복문은 0 보다 클때까지 반복하고 1번 반복할 때마다 - 1 씩 해주면 될것 같네요. 바깥쪽 반복문이 반복하는 횟수는 outterLength 변수에 지정했습니다. print 문으로 찍어보면 총 4번 반복이 되는것을 알 수 있습니다.

 

func selectionSort(arr:[Int])->[Int]{
    
    var resultArr = arr
    var outterLength = arr.count - 1
    
    while 0 < outterLength {
        print("outterLength : \(outterLength)")
        outterLength -= 1
    }
    
    return []
}

var arr = [5,3,4,7,2]
print(selectionSort(arr: arr))
 
 //출력
 //outterLength : 4
 //outterLength : 3
 //outterLength : 2
 //outterLength : 1

 

[안쪽 반복문]

이어서 코드를 생각해 보겠습니다.

주어진 배열 [5,3,4,7,2] 에서 첫번째 요소 5를 제외한 3,4,7,2를 한번씩 스캔해서 총 4번 스캔을 하게되었습니다.

그럼 이제 각각의 key 숫자를 왼쪽의 정렬된 숫자와 비교를 진행하는 반복문을 작성해야 합니다. 이 반복문은 안쪽 반복문이라고 하겠습니다.

1회전에서 5 : 3,4,7,2 

5는 정렬이 되었고, 3이 key 숫자가 되어서 왼쪽의 5와 1번 비교를 진행합니다.

 

2회전에서 3,5 : 4,7,2

3,5는 정렬이 되었고, 4는 key 숫자가 되어서 왼쪽의 5, 3과 2번 비교를 진행합니다.

 

쭉 진행해서 마지막...

 

4회전에서는 3,4,5,7 : 2

3,4,5,7 은 정렬이 되었고 2는 key 숫자가 되어서 왼쪽의 3,4,5,7과 총 4번 비교를 합니다.

 

정리해보면 바깥쪽 반복문 1회전에서는 안쪽 반복문이 1번 

바깥쪽 반복문 2회전에서는 안쪽 반복문이 2번

....

바깐쪽 반복문 4회전에서는 안쪽 반복문이 4번

 

안쪽 반복문은 바깥쪽 반복문이 1회전씩 더해갈때마다 1회씩 추가 됩니다.

 

 

안쪽 반복문의 반복 길이는 var keyIndex = 1 key 숫자의 위치값을 innerLength 에게 할당해줍니다.(var innerLength = keyIndex)

안쪽 반복문이 끝나고 바깥쪽 반복문이 시작되기전에 keyIndex 는 다음 숫자를 key 숫자로 만들어야 되기 때문에 + 1을 해주고 

다음 안쪽 반복문에서는 다시 var innerLength = keyIndex 이렇게 할당을 해줍니다.

 

func selectionSort(arr:[Int])->[Int]{
    
    var resultArr = arr
    var outterLength = arr.count - 1
    var keyIndex = 1
    
    while 0 < outterLength {
        print("outterLength : \(outterLength)")
        
        
        var innerLength = keyIndex
        while 0 < innerLength{
            print("innerLength : \(innerLength), keyIndex : \(keyIndex)")
            innerLength -= 1
        }
        
        outterLength -= 1
        keyIndex += 1
        print("")
    }
    
    return []
}

var arr = [5,3,4,7,2]
print(selectionSort(arr: arr))

 

출력

바깥쪽 반복문 1회전에서 안쪽 반복문 1번, 바깥쪽 반복문 2회전에서 안쪽 반복문 2번 ... 이런식으로 안쪽 반복문은 총 4번 진행이 되는 것을 볼 수 있습니다. 

outterLength : 4
innerLength : 1, keyIndex : 1

outterLength : 3
innerLength : 2, keyIndex : 2
innerLength : 1, keyIndex : 2

outterLength : 2
innerLength : 3, keyIndex : 3
innerLength : 2, keyIndex : 3
innerLength : 1, keyIndex : 3

outterLength : 1
innerLength : 4, keyIndex : 4
innerLength : 3, keyIndex : 4
innerLength : 2, keyIndex : 4
innerLength : 1, keyIndex : 4

 

key 숫자와 왼쪽 숫자들 비교 후 위치 변경 로직

key 숫자의 위치를 지정하는 변수를 위에서 지정을 했습니다. (var keyIndex = 1)

하지만 이 변수는 바깥쪽 반복문에서 스캔되는 key 숫자를 위한 변수이고 안쪽 반복문에서 스캔될 key 숫자의 위치를 위한 변수를 할당해야 합니다.

 

안쪽 반복문에서 스캔될 key 숫자의 위치란!

key숫자는 왼쪽에 정렬된 숫자들과 비교를 통해서 key숫자가 작으면 쭉 왼쪽으로 이동! 합니다. 즉 안쪽 반복문에서는 key 숫자의 위치가 바뀝! 니다. 바뀌어야 되고! 그래야합니다.

 

여기까지 이해가 되셨쥬...??? 예를들면

 

바깥쪽 반복문 1회전에서 5 : 3,4,7,2

5는 정렬이 되었고, 3이 key 숫자가 되어서 왼쪽의 5와 1번 비교(안쪽 반복문)를 진행합니다.

안쪽 반복문의 key 숫자의 위치는 1이었는데 5와 비교후 위치가 변경 되면서 위치는 0이 되었습니다.

 

바깥쪽 반복문 2회전에서 3, 5 : 4,7,2

3,5는 정렬이 되었고, 4는 key 숫자가 되어서 왼쪽의 5, 3과 2번 비교(안쪽 반복문)를 진행합니다.

안쪽 반복문의 key 숫자의 위치는 2인데, 5와 비교를 통해서 key 숫자 4의 위치는 1이 되었다가

3과 비교했을때 key 숫자가 더크므로 안쪽 반복문을 빠져 나옵니다.

 

그래서 안쪽 반복문에서 사용될 key 숫자 위치를 가지고 있을 변수를 지정합니다.

바깥쪽 반복문에서 사용되는 keyIndex을 할당해서 사용하고 안쪽 반복문에서 key숫자보다 왼쪽의 숫자가 크면 innerKeyIndex 에서 - 1을 해주면서 위치 변경을 합니다.

// 안쪽 반복문에서 key 숫자의 위치 지정
var innerKeyIndex = keyIndex

 

이 내용을 전체 코드로 작성해 보도록 하겠습니다.

 

//선택정렬 함수
func selectionSort(arr:[Int])->[Int]{

    var resultArr = arr
    var outterLength = arr.count - 1
    var keyIndex = 1

    while 0 < outterLength {

        // 안쪽 반복문이 몇회 돌아야되는지 길이 지정
        var innerLength = keyIndex
        // 안쪽 반복문에서 key 숫자의 위치 지정
        var innerKeyIndex = keyIndex

        while 0 < innerLength{

            //key 숫자와 key 숫자 왼쪽에 위치한 숫자비교
            let keyNum = resultArr[innerKeyIndex]
            let beforNum = resultArr[innerKeyIndex - 1]

            print("beforNum : \(beforNum), keyNum : \(keyNum)")

            // key 숫자보다 왼쪽에 있는 숫자가 크면 위치 변경
            if keyNum < beforNum {
                print("keyNum이 더 작습니다. 위치 변경.")
                resultArr[innerKeyIndex - 1] = keyNum
                resultArr[innerKeyIndex] = beforNum

                innerKeyIndex -= 1

            // key 숫자가 더 크면 반복문 빠져나가기
            }else{
                print("keyNum이 더 큽니다. break;")
                break
            }

            innerLength -= 1
        }

        outterLength -= 1
        keyIndex += 1
        print("")
    }

    return resultArr
}

var arr = [5,3,4,7,2,56,74,22,34,76,12,11,246,11,23,45,67,21]
print(selectionSort(arr: arr))

 

출력 

[2, 3, 4, 5, 7, 11, 11, 12, 21, 22, 23, 34, 45, 56, 67, 74, 76, 246]

selectionSort.zip

0.02MB