[알고리즘] O(n2) 3가지 기본 정렬 알고리즘 : 버블 정렬, 선택정렬, 삽입정렬 Kotlin 구현

목차

개요

정렬할 때 O(n²) 속도를 가진 알고리즘은 성능 면에서 효율적이지는 않지만, 정렬 알고리즘에서 우리가 이해하기 쉬운 방법입니다. O(n²) 알고리즘은 공간면에서는 효율적입니다 왜냐하면, O(1)만 필요하기 때문입니다. 

 

이번 포스트에서는 버블 정렬(Bubble sort), 선택 정렬(Selection sort), 삽입 정렬(Insertion sort)을 다뤄보겠습니다.

 

 

비교 기반 알고리즘

버블 정렬(Bubble sort), 선택 정렬(Selection sort), 삽입 정렬(Insertion sort) 이 세 가지 알고리즘 모두 비교 기반 정렬 알고리즘입니다. 즉, 이들은 비교 메서드에 의존합니다. 그리고 이 비교 메서드가 얼마나 불리느냐가 이 알고리즘들의 성능을 좌우합니다. 

 

버블 정렬(Bubble Sort)

버블 정렬GIF

버블 정렬은 가장 근접한 값과 비교하면서 순서를 바꿔가며 정렬하는 방법입니다. 아래 그림으로 예시를 들어보겠습니다. 

버블 정렬을 이용해서, 오름차순으로 카드를 정렬하려 합니다. 

• 먼저 9를 가장 가까운 카드인 4와 비교합니다. 9는 4보다 크기 때문에 뒤로 가야 합니다. [ 4, 9, 10, 3]
• 이제 9와 10을 비교합니다. 올바른 순서이기 때문에, 다음으로 넘어갑니다. 
• 10과 3을 비교합니다. [ 4, 9, 3, 10 ]
• 다음으로 정렬할 값이 없기 때문에 멈춥니다. 

마지막으로 정렬된 값을 보면 완전히 정렬되지 않은 것을 확인할 수 있습니다. 오름차순으로 정렬되려면 3이 가장 앞으로 와야 합니다. 이렇게 하려면 더 이상 정렬이 진행되지 않을 때까지 반복되어야 합니다. 

정렬은 마지막에 위치한 카드를 제외하고 다시 반복됩니다. 가장 최악의 상황에서는 정렬을 n-1 번해야 합니다. n은 collection안에 데이터 개수입니다. 이번 예제는 4개이기 때문에 4-1 = 3번이 최악의 상황에서 정렬 횟수입니다. 

 

버블 정렬 구현

위에서 봤던 예제처럼, 위치 전환이 많습니다. 그러므로 구현하기 앞서 ArrayList에 swapAt extension을 연결해주겠습니다. 

 

swapAt 익스텐션 연결

fun <T>ArrayList<T>.swapAt(first: Int, second: Int){
	val aux = this[first]
    	this[first] = this[second]
    	this[second] = aux
}

이제 버블 정렬 함수를 구현하겠습니다. 

 

버블 정렬 함수

fun <T: Comparable<T>> ArrayList<T>.bubbleSort(showPasses:Boolean = false){
	//1
    if(this.size < 2) return
    //2
    for(end in (1 until this.size).reserved()) {
    	var swapped = false
    }
    //3
    for(current in 0 until end){
    	if(this[current] > this[ current + 1 ]){
        	//4
            this.swapAt(current,current+1)
            swapped = true
        }
    }
    //5
    if(showPasses) println(this)
    //6
    if(!swapped return) return
}

 

위 코드를 설명해 보겠습니다. 

1. 리스트 안에 2개 이하가 있다면 정렬할 필요가 없습니다. 

2. 첫 번째 정렬 후 가장 큰 값은 마지막에 위치하게 됩니다. 그러므로 한번 반복될 때마다 가장 끝에 있는 값은 체크하지 않아도 되게 됩니다. 

3. 이반 복문은 첫 element부터 정렬되지 않은 끝 element까지 정렬하게 됩니다. 

4. 위치를 바꿔야 할 게 있다면 바꿉니다. 얼마나 빨리 정렬될 부분을 찾느냐에 따라 언제 반복문이 끝날지 정해집니다. 

5. 이 부분은 매 정렬마다 어떻게 바뀌는지 보여줍니다. 

6. 만약 정렬된 element가 없다면 정렬이 완료된 array로 간주하게 됩니다. 

 

이제 메인 문에서 실행해보겠습니다. 

"bubble sort" example{
    val list = arrayListOf(9, 4, 10, 3)
    println("Original: $list")
    list.bubbleSort(true)
    println("Bubble sorted: $list")
}

결과는 아래와 같습니다. 

---Example of bubble sort---
Original: [9, 4, 10, 3]
[4, 9, 3, 10]
[4, 3, 9, 10]
[3, 4, 9, 10]
Bubble sorted: [3, 4, 9, 10]

정리: 거의 모든 상황에서 O(n²)을 가집니다. 단 이미 정렬된 자료에서 한 번만 실행하면 최고의 성능을 보입니다. 가장 손쉽게 만들 수 있지만 가장 비효율적인 코드입니다. 

 

선택 정렬(Selection Sort)

선택정렬 GIF

선택 정렬은 버블 정렬을 기초로 하지만 swap오퍼레이션을 줄여서 좀 더 발전시킨 알고리즘입니다. 선택 정렬 특징으로는 각 Loop마다 가장 낮은 값을 찾고 swap 할 위치에 넣어줍니다. 아래 카드를 선택 정렬로 정렬해보겠습니다. 

정렬되지 않은 위에 카드 4개를 선택 정렬 방식으로 정렬해보겠습니다. 

과정은 아래와 같습니다. 

1. 주어진 카드 중 3이 가장 낮은 값인지 알아냈기 때문에 맨 앞자리인 9와 자리를 바꿉니다. 

2. 다음으로 낮은 값은 4입니다. 이미 맞는 자리에 있기 때문에 따로 건드리지 않습니다. 

3. 이제 9와 10을 바꿉니다. 

 

선택 정렬 구현

이제 선택 정렬을 코드로 구현해보겠습니다. 

 

선택 정렬 함수 

fun <T: Comparable<T>> ArrayList<T>.selectionSort(showPasses: Boolean = false){
	
    if(this.size < 2 ) return
    
    //1
    for(current in 0 until (this.size -1 )){
    	var lowest = current
    
    //2
        for(other in (current + 1) until this.size){
        	if(this[lowest] > this[other]){
            	lowest = other
            }
        }
    //3
        if(lowest != current){
            this.swapAt(lowest, current)
        }
    //4
        if(showPasses) println(this)
           
    }
}

 위 코드를 설명하겠습니다. 

1. 만약 마지막 element를 제외한 모든 element가 정렬되었다면 마지막 element도 정렬돼있다는 의미이기 때문에, 마지막 element는 반복문에 포함하지 않습니다. 

2. 남은 collection element 중 가장 낮은 값을 반복해서 찾습니다. 

3. 가장 작은 값이 현재 element가 아니면 현재 element와 위치를 바꿉니다. 

4. 정렬되고 어떻게 리스트가 바뀌는지 확인할 수 있습니다. 

 

메인 문에서 실행해보도록 하겠습니다. 

"selection sort" example {
    val list = arrayListOf(9, 4, 10, 3)
    println("Original: $list")
    list.selectionSort(true)
    println("Bubble sorted: $list")
}

결과 값은 아래와 같습니다. 

---Example of selection sort---
Original: [9, 4, 10, 3]
[3, 4, 10, 9]
[3, 4, 10, 9]
[3, 4, 9, 10]
Bubble sorted: [3, 4, 9, 10]

 

정리: 버즐 정렬이 비교하고 바로 바꿔 넣는 걸 반복한다면 선택 정렬은 첫 번째부터 훑어서 가장 작은 게 첫 번째, 다시 두 번째부터 끝까지 훑어서 가장 작은 게 2번째로이동...이걸 n-1번을 반복합니다. 인간이 정렬할 때 사용하는 방식과 가장 많이 닮았습니다.  버블 정렬보다 두배 빠르고, 어떻게 정렬되어있든 일관성 있게 n(n-1)에 비례하여 걸린다는 게 특징입니다.

 

삽입 정렬(Insertion sort)

삽입 정렬 GIF

삽입 정렬 또한 O(n²) 평균속도를 가지고 있습니다. 많이 정렬돼있으면 돼있을수록 시간이 적게 걸립니다. 모든 값이 정렬되어있다면 최고속도로 O(n)까지 나올 수 있습니다. 

 

다시 정렬되지 않은 카드 4개를 삽입 정렬로 정렬해보겠습니다. 

위 과정을 설명해보겠습니다. 

1. 비교할 전 카드가 없기 때문에 첫 번째 카드는 넘어갑니다. 

2. 다음으로 4와 9를 비교한 후 4를 왼쪽으로 이동시키기 위해 4와 9위 치를 바꿔줍니다. 

3. 10의 위치는 바뀌지 않아도 됩니다.

4. 3은 10 9 4 순서로 비교 후에 가장 앞으로 오게 됩니다. 

 

삽입 정렬 구현

삽입 정렬 함수

fun<T: Comparable<T>> ArrayList<T>.insertionSort(showPasses: Boolean = false){
	if(this.size < 2) return
    //1
    for (current in 1 until this.size) {
    //2
        for(shifting in (1..current.reversed())){
    //3 
            if (this[shifting] < this[shifting - 1]){
            	this.swapAt(shifting, shifting -1)
            } else {
            	break
            }
        }
    //4
        if(showPasses) println(this)
    }
}

1. 왼쪽부터 오른쪽까지 반복하는 코드입니다. 

2. 다시 뒤로 돌아가는 반복문입니다. 왼쪽으로 현재 element를 옮겨줘야 할 때를 위함입니다. 

3. 필요한 만큼 element를 왼쪽으로 옮겨줍니다. element가 원하는 위치에 왔을 때 루프를 끝냅니다. 

4. 정렬되고 어떻게 리스트가 바뀌는지 확인할 수 있습니다. 

 

메인 문에 위 함수를 삽입 정렬하는 함수를 구현해보겠습니다. 

"insertion sort" example{
	val list = arrayListOf(9, 4, 10, 3)
    println("Origial: $list")
    list.insertionSort(true)
    println("Bubblesorted: $list")
}

아래 코드는 위 코드를 실행한 값입니다.

---Example of insertion sort---
Original: [9, 4, 10, 3]
[4, 9, 10, 3]
[4, 9, 10, 3]
[3, 4, 9, 10]
Bubble sorted: [3, 4, 9, 10]

 

정리: 배열이 작거나 이미 정렬돼 있을 경우 매우 효율적입니다. 사이즈가 크면 고성능인 O(Log n) 속도를 가진 알고리즘을 쓰다가 정리해야 할 부분이 작을 때는 삽입 정렬로 쓰는 것도 효과적입니다.