SelectionSort with Swift

Description

Selection Sort 는, 배열 차례대로 하나하나 비교해가며 가장 작은 값을 찾은 후,  가장 낮은 인덱스에 있는 수와 바꾸는 방식을 반복하여 정렬을 진행합니다. 아래는 정렬할 array 의 예시입니다. (Bubble Sort 의 경우와 같은 array 를 대상으로 정렬을 진행하겠습니다. 

[4, 3, 5, 2, 1]

1.   먼저 4 ( 0번째 index ) 을 기준으로 한 후 3와 비교합니다. 기준이 아닌 수가 기준보다 작으므로 3 를 기준으로 삼습니다. 

2.   이제, 새로운 기준 3 과 5 를 비교합니다. 기준이 더 작으므로 다음 수로 넘어갑니다.

3.   3과 2 를 비교합니다. 2 가 기준보다 작으므로, 2 를 새로운 기준으로 삼습니다.

4.   2 와 1 을 비교합니다. 1 이 기준보다 작으므로, 1 을 새로운 기준으로 삼습니다.

 

이제 더 비교할 수가 없으므로, 0번 index 와 지금까지 가장 작은 값 1 이 있는 4 번 index 값들을 서로 바꿔줍니다. 

 

// [4, 3, 5, 2, 1]
   [1, 3, 5, 2, 4]

1이 고정되었습니다. 행렬의 모든 수 중 가장 작은 값을 0 번 index 에 위치시켰으므로, 다음 단계는 1번 index 부터 시작합니다.

1.    1 번 index 에 있는 수 3 을 기준으로 삼습니다.   기준 3 과 5 를 비교합니다. 기준이 더 작으므로 다음 수로 넘어갑니다.

2.    기준 3과 2 를 비교합니다. 2 가 기준보다 작으므로, 2 를 새로운 기준으로 합니다.

3.    기준 2 와 4 를 비교합니다. 기준이 더 작고, 더 비교할 수가 없으므로 과정을 종료합니다.

// [4, 3, 5, 2, 1]
// [1, 3, 5, 2, 4]
[1, 2, 5, 3, 4]

1과 2 가 고정되었습니다. 다음으로 2번 index 5 를 기준으로 삼고 비교를 시작합니다.

1.    5와 3 을 비교합니다. 3 이 기준보다 작으므로 3 을 새로운 기준으로 삼습니다. 

2.   3 과 4 를 비교합니다. 기준이 더 작고, 더 비교할 수가 없으므로 과정을 종료합니다.

// [4, 3, 5, 2, 1]
// [1, 3, 5, 2, 4]
// [1, 2, 5, 3, 4]
 [1, 2, 3, 5, 4]

이제 3번 index 에 있는 5 를 기준으로 삼고 비교를 시작합니다. 

1.    5 와 4 를 비교합니다. 4 가 기준보다 작으므로 4를 새로운 기준으로 삼습니다. 더 비교할 수가 없으므로 과정을 종료합니다. 

// [4, 3, 5, 2, 1]
// [1, 3, 5, 2, 4]
// [1, 2, 5, 3, 4]
// [1, 2, 3, 5, 4]
[1, 2, 3, 4, 5]

모든 과정이 종료되었습니다 ! Bubble Sort 와 마찬가지로, 비교하는 횟수는 행렬에 5개의 elements 가 있을 때각 단계별로 4, 3, 2, 1 번의 비교가 필요했습니다. 따라서, n 개의 elements 를 갖는 행렬의 경우 (n)(n-1) / 2 번의 과정이 필요합니다. (Bubble Sort 와 동일)

 

 

Implementation

 

 

SelectionSort 를 For statement 을 사용하여 만들어보았습니다.

func selectionSortWithFor(array: [Int]) -> [Int] {
    var pivotIndex = 0
    var arr = array

    for i in 0 ..< arr.count - 1 {
        pivotIndex = i
        for j in i ..< arr.count - 1 {
            if (arr[pivotIndex] > arr[j+1]) {
                pivotIndex = j
            }
        }
        arr.swapAt(i, pivotIndex)
    }
    return arr
}

위 코드에서, i index Loop 가 시작할 때, pivotIndex = i 로 설정합니다. pivotIndex 는 위 설명에서, 기준이 되는 값이 존재하는 index 입니다. 행렬 [4, 3, 5, 2, 1] 을 놓고 보았을 때, arr.count == 5 이므로, i 는 0 ... 3 의 값을 갖습니다. 

또한, i Loop 내부에 j Loop 가 있고, j 의 값은 i ... 3 입니다. if statement 에서 pivotIndex, (j+1) 번째 index 둘을 비교합니다. 따라서 (j+1) 은   (i+1) ... 4 의 값을 가집니다. if statement 내에서 값을 비교한 후, 더 작은 값을 가진 index 가 pivotIndex 가 됩니다.   

 

j Loop 가 끝나면 pivotIndex 에 행렬 중 가장 작은 값을 가진 수의 index 가 저장되었다고 말할 수 있고, 따라서 i 번째 index 와 pivotIndex 를 서로 바꿔줍니다. 

그 후 pivotIndex 를 새로운 index ( 증가한 i ) 값으로 설정하고, 비교를 계속합니다. 

 

 

 

각 단계별 실행 결과 및 실행 횟수를 다음 코드를 통해 확인할 수 있었습니다. 

let IntArray = [4, 3, 5, 2, 1]
print("\(IntArray)\n")

func selectionSort(array: [Int]) -> [Int] {
    var pivotIndex = 0
    var arr = array
    var count = 0
    // arr.count - 1 = 4, i : 0 ~ 3 ok  . j : i ~ 4 ok
    for i in 0 ..< arr.count - 1 {
        pivotIndex = i
        for j in i ..< arr.count - 1 {
            count += 1
            
            print(count, "th, compare index of ",pivotIndex, "and", j+1)
            if (arr[pivotIndex] > arr[j+1]) {
                pivotIndex = j
            }
        }
        arr.swapAt(i, pivotIndex)
       
        print("\(i)th repetion end !")
        print("result: \(arr)\n")
    }
    print("total count: \(count)")
    return arr
}



selectionSort(array: IntArray)



//[4, 3, 5, 2, 1]
//
//1 th, compare index of  0 and 1
//2 th, compare index of  0 and 2
//3 th, compare index of  0 and 3
//4 th, compare index of  2 and 4
//1th repetion end !
//result: [2, 3, 5, 4, 1]
//
//5 th, compare index of  1 and 2
//6 th, compare index of  1 and 3
//7 th, compare index of  1 and 4
//2th repetion end !
//result: [2, 4, 5, 3, 1]
//
//8 th, compare index of  2 and 3
//9 th, compare index of  2 and 4
//3th repetion end !
//result: [2, 4, 3, 5, 1]
//
//10 th, compare index of  3 and 4
//4th repetion end !
//result: [2, 4, 3, 5, 1]
//
//total count: 10

 

With Generic

 

해당 Sorting function 을 다른 Type 에도 적용하기 위해서는, Int 가 아닌 Generic Type 을 써주도록 합니다. 

func selectionSortWithFor<T: Comparable> (array: [T]) -> [T] {
    var pivotIndex = 0
    var arr = array

    for i in 0 ..< arr.count - 1 {
        pivotIndex = i
        for j in i ..< arr.count - 1 {
            if (arr[pivotIndex] > arr[j+1]) {
                pivotIndex = j
            }
        }
        arr.swapAt(i, pivotIndex)
    }
    return arr
}