[Algorithm] 정렬 알고리즘 2 ~ 퀵, 쉘, 버블 정렬 ~ (Kotlin)

퀵 정렬

 

https://en.wikipedia.org/wiki/Quicksort

Quicksort - Wikipedia

퀵 정렬은 범용 정렬 알고리즘이다. 정렬에 일반적으로 쓰이는 알고리즘이다. 특히 큰 분포의 무작위 데이터에 대해 병합 정렬, 힙 정렬보다 약간 빠르다. 퀵 정렬은 분할 정복 알고리즘이다. 배열에서 피벗 요소를 선택하고 다른 요소들이 피벗보다 작거나 큰지에 따라 2개의 하위 배열로 분할하는 식으로 작동한다. 그래서 파티션 교환 정렬이라고도 한다. 그 다음 하위 배열이 재귀적으로 정렬된다. 이 작업은 제자리에서 수행할 수 있어서 정렬 수행에 추가 메모리가 조금만 필요하다
퀵 정렬은 비교 정렬이라 보다 작은 관계(공식적으론 전체 순서)가 정의된 모든 유형의 항목을 정렬할 수 있다. 이전 비교 결과의 전이적 종결에서 상대 순서를 얻은 때에만 요소 a, b가 교체되므로 비교 기반 정렬이다. 대부분의 퀵 정렬 구현은 불안정적이므로 같은 정렬 항목의 상대 순서가 유지되지 않는다. 퀵 정렬의 수학적 분석에 따르면 알고리즘은 평균적으로 O(n log n) 비교를 수행해서 n 항목을 정렬하는 것으로 나타났다. 최악의 경우엔 O(n^2) 비교를 수행한다...(중략)...퀵 정렬은 파티셔닝 루틴을 기반으로 배열을 정렬하는 일종의 분할 정복 알고리즘으로 이 파티셔닝의 세부사항은 다를 수 있으므로 퀵 정렬은 실제로 밀접하게 관련된 알고리즘의 계열이다. 최소 2개 요소로 구성된 범위에 적용하면 파티셔닝은 첫 번째 하위 범위의 요소가 2번째 하위 범위의 요소보다 크지 않도록 비어있지 않은 2개의 연속 하위 범위로 분할을 만든다. 이 분할을 적용한 후 퀵 정렬은 하위 범위를 재귀적으로 정렬하는데 이 때 분할 지점에서 이미 최종 위치에 있는 것으로 알려진 요소를 제외할 수도 있다. 재귀적 특성으로 인해 퀵 정렬은 궁극적인 목표가 전체 배열을 정렬하는 것이라도 더 큰 배열 안의 범위에 대해 호출할 수 있도록 공식화(formulated)해야 한다...(중략)

 

피벗이라는 생소한 말이 나오는데, 문맥상 유추한 사람도 있겠지만 피벗은 배열을 2개로 나누기 위한 기준값이다.

피벗 기준으로 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽에 위치시킨다. 때문에 피벗은 배열 안에서 항상 정렬된 위치에 놓이게 되고 그 위치는 이후에 변경되지 않는다.

또한 피벗을 기준으로 나뉜 두 부분은 다시 각각 독립적으로 정렬된다. 이 때 피벗은 그 자리 그대로 고정된 상태로 움직이거나 하지 않는다. 왼쪽, 오른쪽의 두 부분으로 나누는 건 분할 과정이라고 불린다.

예시 코드의 [64, 34, 25, 12, 22, 11, 90]에서 피벗을 25로 선택한 경우는 아래와 같이 작동한다.

 

• 피벗을 25로 선택
• 분할 작업을 통해 피벗보다 작은 요소는 왼쪽, 큰 요소는 오른쪽 배치한다. i는 피벗보다 작은 요소들의 인덱스를 추적하는 포인터고 j는 배열을 순회하면서 현재 요소를 피벗과 비교하는 포인터다
• 초기 상태
  • 배열 : [64, 34, 25, 12, 22, 11, 90]
  • i = -1, j = 0
• 1번째 비교(j = 0)
  • arr[0] = 64는 25보다 크다 -> 스왑하지 않는다
  • 상태 변화 없음
• 2번째 비교(j = 1)
  • arr[1] = 34는 25보다 크다 -> 스왑하지 않는다
  • 상태 변화 없음
• 3번째 비교(j = 2)
  • arr[2] = 25는 피벗 자체다 -> 생략
• 4번째 비교(j = 3)
  • arr[3] = 12는 25보다 작다
  • i++ -> i = 0
  • swap(arr[0], arr[3]) 호출 -> [12, 34, 25, 64, 22, 11, 90]
• 5번째 비교(j = 4)
  • arr[4] = 22는 25보다 작다
  • i++ -> i = 1
  • swap(arr[1], arr[4]) 호출 -> [12, 22, 25, 64, 34, 11, 90]
• 6번째 비교(j = 5)
  • arr[5] = 11은 25보다 작다
  • i++ -> i = 2
  • swap(arr[2], arr[5]) 호출 -> [12, 22, 11, 64, 34, 25, 90]
• 이제 피벗(25)보다 작은 값들은 입력 배열과 비교해서 피벗보다 왼쪽에 위치하고 큰 값들은 오른쪽에 위치한다. 그리고 피벗은 현재 arr[5]에 있다
• 현재 i는 2기 때문에 피벗을 i + 1 = 3 위치로 옮겨야 한다. 그래서 arr[5]와 arr[3]을 서로 스왑한다
• 스왑 후 배열 = [12, 22, 11, 25, 34, 64, 90]
• 이후 재귀적으로 정렬하는 과정을 거쳐 완전히 정렬되지 않은 배열을 정렬되게 한다
  • 피벗 기준 왼쪽 배열 [12, 22, 11]
    • 피벗을 22로 선택
    • 분할 후 배열은 [12, 11, 22]가 되고 재귀적으로 [12, 11]을 정렬 (예제의 quicksort())
    • [12, 11]에서 피벗을 11로 선택해 정렬하면 [11, 12]가 된다
    • 결과 : [11, 12, 22]
  • 피벗 기준 오른쪽 배열 [34, 64, 90] : 이미 정렬돼 있어서 더 이상 정렬하지 않음
• 최종 결과 = [11, 12, 22, 25, 34, 64, 90]

 

쉘 정렬

 

https://en.wikipedia.org/wiki/Shellsort

Shellsort - Wikipedia

쉘 정렬은 제자리 비교 정렬이다. 교환 정렬(버블 정렬)이나 삽입 정렬을 일반화한 것으로 볼 수 있다. 이 방법은 서로 멀리 떨어진 요소 쌍을 정렬하는 것으로 시작한 다음 비교 대상 요소 사이의 간격을 점차 줄여나간다. 멀리 떨어진 요소부터 시작하면 단순히 가장 가까운 이웃 요소 교환보다 더 빨리 제자리에 있지 않은 요소를 제자리로 옮길 수 있다. 쉘 정렬의 실행 시간은 사용하는 간격 순서에 따라 크게 달라진다. 많은 실용적인 변형의 경우 시간 복잡성을 고려하는 건 여전히 미해결 문제로 남아 있다
쉘 정렬은 멀리 떨어진 항목을 교환할 수 있게 하는 삽입 정렬의 최적화 기능이다. 이 개념은 요소 리스트를 정렬해서 어느 위치에서 시작해 모든 h번째 요소를 가져가면 정렬된 리스트가 생성되게 하는 것이다. 이런 리스트를 h 정렬 리스트라고 한다. 이는 각각 개별적으로 정렬된 h interleaved list로 생각할 수도 있다. 큰 값의 h로 시작하면 요소가 원래 리스트에서 먼 거리를 이동할 수 있으므로 많은 무질서가 빠르게 줄어들고 더 작은 h 정렬 단계가 수행할 작업이 줄어든다. 그 다음 리스트가 더 작은 정수 k로 정렬되면 리스트는 h 정렬된 상태로 유지된다. h = 1로 최종 정렬하면 리스트가 마지막에 완전히 정렬되지만 h값의 감소 시퀀스를 신중하게 선택하면 이 최종 패스에서 해야 할 작업이 거의 남지 않는다...(중략)...쉘 정렬은 퀵 정렬보다 더 많은 작업을 수행하고 캐시 누락률이 더 높다. 그러나 적은 코드로 구현 가능하고 콜 스택을 쓰지 않아서 임베디드 시스템을 대상으로 하는 C 표준 라이브러리의 일부 구현에선 퀵 정렬 대신 qsort()를 사용한다. 또한 쉘 정렬은 짧은 하위 배열을 정렬하고 재귀 깊이가 주어진 한계를 초과할 때 속도 저하를 방지하기 위해 내성 정렬(introspective sort)의 하위 알고리즘으로 쓸 수 있다

 

쉘 정렬은 삽입 정렬의 일반화된 버전으로 배열을 일정 간격(gap)으로 나눠서 부분 정렬한 뒤 간격을 점차 줄여가면서 정렬하는 방식이다. 결국 간격은 1이 되서 배열 전체를 삽입 정렬로 마무리한다. 쉘 정렬의 주요 개념은 아래와 같다.

 

• 간격 선택 : 배열을 나눌 간격을 선택한다. 일반적으로 간격을 배열 길이의 절반부터 시작해 점차 줄여간다
• 부분 배열 정렬 : 간격에 따라 떨어진 요소들을 삽입 정렬 방식으로 정렬한다
• 간격을 줄임 : 간격을 절반으로 줄이며 배열을 더 세세하게 정렬해간다
• 완료 : 간격이 1이 되면 배열 전체를 마지막으로 삽입 정렬해 정렬을 마친다

 

코틀린으로 쉘 정렬을 구현한 예시는 아래와 같다.

 

fun shellSort(arr: IntArray) {
    var n = arr.size

    // 초기 간격을 배열 크기의 절반으로 설정
    var gap = n / 2

    // gap이 0이 될 때까지 반복
    while (gap > 0) {
        // gap 간격만큼 떨어진 요소들을 삽입 정렬
        for (i in gap until n) {
            val temp = arr[i]
            var j = i

            // 삽입 정렬과 같은 방식으로 배열 내 요소들을 비교하여 교환
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap]
                j -= gap
            }

            // 적절한 위치에 temp를 삽입
            arr[j] = temp
        }

        // 간격을 반으로 줄임
        gap /= 2
    }
}

fun main() {
    val arr = intArrayOf(64, 34, 25, 12, 22, 11, 90)
    println("정렬 전 : ${arr.joinToString()}")

    shellSort(arr)

    println("정렬 후 : ${arr.joinToString()}")
}

// 정렬 전 : 64, 34, 25, 12, 22, 11, 90
// 정렬 후 : 11, 12, 22, 25, 34, 64, 90

 

배열 크기를 구해서 초기 간격(gap)을 배열 크기의 절반으로 설정한다. 7이면 3이 되고 8이면 4가 될 것이다. 이후 gap이 0이 될 때까지 while문을 반복한다. 각 반복에서 gap에 따라 떨어진 요소들을 삽입 정렬한다. while 안의 for 루프가 현재 gap에 따라 요소를 순차적으로 삽입 정렬하는 코드다.

현재 선택된 요소(arr[i])보다 큰 요소가 있는 동안 그 요소를 오른쪽으로 이동시키며 위치를 찾고, 그 후 적절한 곳에 선택된 요소인 temp를 삽입한다.

여기까지 진행되면 배열은 어느 정도 정렬된다. 이후 gap을 다시 반으로 줄이며 gap이 1이 될 때까지 다시 while문을 반복한다. 아래는 단계별 작동 과정이다.

 

• 초기 배열 = [64, 34, 25, 12, 22, 11, 90]
• gap = 3
• 간격 3을 기준으로 떨어진 요소들을 정렬. 배열 안에서 간격이 3만큼 떨어진 요소들끼리 비교하며 정렬한다
  • 간격이 3인 요소들끼리 비교한다
    • 인덱스 0, 3, 6인 요소끼리 비교 (64, 12, 90) -> [12, 64, 90]
    • 인덱스 1, 4 요소끼리 비교 (32, 22) -> [22, 34]
    • 인덱스 2, 5 요소끼리 비교 (25, 11) -> [11, 25]
    • 결과 = [12, 64, 90, 22, 34, 11, 25]
• 간격을 1로 축소
  • 간격 1로 전체 배열을 삽입 정렬 수행
  • [12, 22, 11, 64, 34, 25, 90]에서 1씩 간격을 두고 삽입 정렬
    • 1단계 (인덱스 1 = 64) : 이미 정렬된 상태라 변화 없음
    • 2단계 (인덱스 2 = 90) : 이미 정렬된 상태라 변화 없음
    • 3단계 (인덱스 3 = 22)
      • 22는 90보다 작다 -> 90을 오른쪽으로 이동하고 64도 오른쪽으로 이동
      • 22는 적절한 곳에 삽입
      • 결과 = [12, 22, 64, 90, 34, 11, 25]
    • 4단계 (인덱스 4 = 34)
      • 34는 90보다 작다 -> 90을 오른쪽으로 이동하고 64도 오른쪽으로 이동
      • 34를 적절한 곳에 삽입
      • 결과 = [12, 22, 34, 64, 90, 11, 25]
    • 5단계 (인덱스 5 = 11)
      • 11은 90, 64, 34, 22보다 작다 -> 4개 숫자들을 전부 오른쪽으로 이동
      • 11을 맨 앞에 삽입
      • 결과 = [11, 12, 22, 34, 64, 90, 25]
    • 6단계 (인덱스 6 = 25)
      • 25는 90, 64, 34보다 작다 -> 3개 숫자들을 오른쪽으로 이동
      • 25를 적절한 곳에 삽입
      • 결과 = [11, 12, 22, 25, 34, 64, 90]
  • 최종 결과 = [11, 12, 22, 25, 34, 64, 90]

 

버블 정렬

 

https://en.wikipedia.org/wiki/Bubble_sort

Bubble sort - Wikipedia

sinking sort라고도 하는 버블 정렬은 입력 리스트를 요소별로 반복 순회하면서 현재 요소와 그 뒤의 요소를 비교하고 필요하면 값을 바꾸는 정렬 알고리즘이다. 이런 리스트 통과는 통과하는 동안 스왑하지 않아도 될 때까지 반복하며 이는 리스트가 완전히 정렬됐음을 의미한다. 비교 정렬인 이 알고리즘은 큰 요소가 리스트 맨 위로 버블되는 방식에서 이름이 붙여졌다. 이 알고리즘은 실제 성능은 좋지 않으며 주로 교육용으로 사용된다. 퀵 정렬, 팀 정렬, 병합 정렬 같은 더 효율적인 알고리즘은 파이썬, 자바 등 널리 쓰이는 프로그래밍 언어에 내장된 정렬 라이브러리에서 쓰인다. 그러나 병렬 처리가 허용되면 버블 정렬은 O(n) 시간 안에 정렬되서 병렬화되지 않는 삽입 정렬, 선택 정렬의 병렬 구현보다 훨씬 빠르다...(중략)...버블 정렬은 최악의 경우 평균 복잡도는 O(n^2)다. n은 정렬되는 항목의 수다. 종종 O(n log n)이다. 삽입 정렬 등 다른 정렬 알고리즘도 일반적으로 버블 정렬보다 빨리 실행되며 더 복잡하지 않다. 그래서 버블 정렬은 실제론 거의 쓰이지 않는다. 버블 정렬은 적응형이라 빠른 정렬과 같은 알고리즘보다 유리할 수 있다. 즉 리스트가 이미 대부분 정렬된 경우(반전 횟수가 적은 경우)엔 평균 시간 복잡도가 더 나쁘더라도 이런 알고리즘보다 더 성능이 우수할 수 있다
요소는 서로 다른 속도와 방향으로 이동하기 때문에 정렬 중 요소가 이동해야 하는 거리, 방향에 따라 버블 정렬의 성능이 결정된다. 리스트 끝으로 이동해야 하는 요소는 연속 스왑에 참여할 수 있어서 빨리 이동할 수 있다. 리스트에서 가장 큰 요소는 모든 스왑에서 승리하므로(win) 처음 근처에서 시작하더라도 첫 번째 패스에서 정렬된 위치로 이동한다. 반면 리스트 시작 부분으로 이동해야 하는 요소는 패스당 한 단계보다 빨리 이동할 수 없어서 요소가 시작 부분을 향해 매우 느리게 이동한다. 가장 작은 요소가 리스트 끝에 있으면 이걸 시작 부분으로 옮기는데 n-1회 패스한다. 이 때문에 토끼와 거북이라고 불린다
버블 정렬의 속도 개선을 위해 거북이를 없애기 위한 노력이 이뤄졌다. 칵테일 정렬은 양방향 버블 정렬로, 처음부터 끝까지 이동했다가 다시 역방향으로 이동해서 끝에서 시작으로 이동하는 방식이다. 최악의 경우 O(n^2) 복잡도를 유지한다
빗 정렬(comb sort)은 큰 간격으로 구분된 요소를 비교하며 거북이를 빠르게 이동시키고 점점 더 작은 간격으로 이동해서 리스트를 매끄럽게 만들 수 있다. 평균 속도는 퀵 정렬 같은 더 빠른 알고리즘들과 비슷하다...(중략)
버블 정렬은 수가 적은 리스트에선 효율성이 급격히 떨어진다. 단순한 O(n^2) 정렬 알고리즘 중에서도 삽입 정렬 같은 알고리즘이 일반적으로 더 효율적이다...(중략)...오웬 아스트라찬의 실험 결과에서도 삽입 정렬이 무작위 리스트에서도 훨씬 더 나은 성능을 보인다는 것이 밝혀졌다. 이런 이유로 최신 알고리즘 교과서에선 버블 정렬을 쓰지 않고 삽입 정렬을 선호한다...(중략)

 

이래저래 평가가 안 좋은 버블 정렬이다. 실용적 가치가 없어서 알고리즘 교육용으로 쓰이는 정도의 알고리즘이지만 병렬 처리가 허용된다는 조건이 붙으면 속도가 어느 정도 나오는 듯하다.

아래는 코틀린으로 버블 정렬은 구현한 예시다.

 

fun bubbleSort(arr: IntArray) {
    val n = arr.size
    for (i in 0 until n - 1) {
        // 이미 정렬된 요소는 다시 비교하지 않음
        for (j in 0 until n - i - 1) {
            // 인접한 요소들을 비교해서 더 큰 값이 오른쪽으로 이동
            if (arr[j] > arr[j + 1]) {
                // 요소를 서로 교환
                val temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }
    }
}

fun main() {
    val arr = intArrayOf(64, 34, 25, 12, 22, 11, 90)
    println("정렬 전 배열 : ${arr.joinToString()}")
    bubbleSort(arr)
    println("정렬 후 배열 : ${arr.joinToString()}")
}

// 정렬 전 배열 : 64, 34, 25, 12, 22, 11, 90
// 정렬 후 배열 : 11, 12, 22, 25, 34, 64, 90

 

bubbleSort() 안의 첫 번째 for문은 배열을 돌면서 매번 가장 큰 값을 배열 끝으로 이동시킨다. 이미 정렬된 요소는 비교하지 않기 때문에 매번 끝에서 1칸씩 비교 범위를 줄이는(n - i - 1) 걸 볼 수 있다.

그 안의 2번째 for문에선 배열 안의 인접 요소를 비교하면서 더 큰 값을 오른쪽으로 이동시킨다. 이 때 arr[j]가 arr[j + 1]보다 큰 경우에는 스왑 처리로 둘을 바꾼다.

위 코드의 작동 순서는 아래와 같다.

 

• 1번째 패스(i = 0)
  • 64와 34를 비교한다. 64가 더 커서 두 값의 위치를 서로 바꾼다 = [34, 64, 25, 12, 22, 11, 90]
  • 64와 25를 비교한다. 64가 더 커서 두 값의 위치를 서로 바꾼다 = [34, 25, 64, 12, 22, 11, 90]
  • 이런 식으로 계속 진행하다 64와 90을 비교한다. 90이 더 크므로 위치를 바꾸지 않고 그대로 둔다
  • 결과 = [34, 25, 12, 22, 11, 64, 90]
• 2번째 패스(i = 1)
  • 34와 25를 비교한다. 34가 더 커서 두 값의 위치를 서로 바꾼다 = [25, 34, 12, 22, 11, 64, 90]
  • 1번째 패스와 같이 계속 비교 후 위치 변경 or 넘기기를 반복한다. 이 때 마지막 요소인 90은 비교대상이 아님에 주의한다
  • 결과 = [25, 12, 22, 11, 34, 64, 90]
• i가 5가 될 때까지 반복문이 작동하고, i가 5일 땐 11과 12를 비교한다. 11이 더 작기 때문에 위치를 바꾸지 않는다
• 최종 결과 = [11, 12, 22, 25, 34, 64, 90]

 

이 순서를 바탕으로 버블 정렬의 작동 방식을 요약하면 아래와 같다.

 

• 비교, 교환 : 배열의 각 요소를 인접한 요소(=서로 붙어있는 요소)와 비교하고 크기 순서가 안 맞음녀 두 요소의 위치를 바꿈
• 가장 큰 값을 오른쪽으로 이동 : 한 번의 패스가 끝날 때마다 가장 큰 값이 배열 끝(=맨 오른쪽)으로 이동한다
• 다시 반복 : 배열 안의 요소들이 모두 정렬될 때까지 위 과정을 반복