1. Epic GamesDeveloper
  3. Verse의 정렬 알고리즘

Verse의 정렬 알고리즘

정렬 알고리즘을 사용하여 오브젝트 목록을 정렬하는 방법을 알아봅니다.

Verse의 정렬 알고리즘

정렬은 간단하지만 강력한 콘셉트입니다. 정리되어 있지 않은 아이템 목록을 가져와서 알고리즘을 사용하면 특정 순서로 정렬할 수 있습니다. 이 아이디어가 기초적인 것으로 보일 수 있지만, 정렬은 다양한 양상과 여러 가지 형태로 컴퓨터 과학 전반에서 등장합니다. 가장 중요한 적용 방식 중 하나는 검색 속도를 높이는 것입니다. 예를 들어 컴퓨터에서 이름과 크기별로 파일을 정렬하면 필요한 파일을 빠르게 찾을 수 있습니다. UEFN에서는 아웃라이너(Outliner) 의 오브젝트를 타입(Type) 별로 정렬하여 항목을 그룹화하고 프로젝트를 정리할 수 있습니다. 포트나이트에서 게임 내 점수판의 플레이어는 처치와 랩타임과 같은 다양한 통계별로 정렬되므로, 모든 플레이어가 누가 상위를 차지하고 있는지 알 수 있습니다.

Verse 코드에 정렬을 적용하면 게임플레이 수준을 높일 수 있으며, 개발의 여러 측면을 강화할 수 있습니다. 예를 들어 각 라운드 후 득점이 가장 낮은 플레이어가 탈락하는 토너먼트에서 플레이어 배열을 점수별로 정렬하는 경우를 생각해 보겠습니다. 각 라운드가 끝나는 시점에 이 배열을 정렬함으로써, 가장 점수가 낮은 플레이어를 빠르게 찾아 관전자로 설정할 수 있습니다. 반대로 가장 높은 점수를 획득한 플레이어를 그만큼 빠르게 찾을 수 있어, 다음 라운드에서 보너스 보상을 줄 수 있습니다. 이러한 정렬된 목록을 사용해서 퍼시스턴스 로컬 리더보드를 만들 수도 있으며, 플레이어는 게임 중에 누구를 주목해야 할지 알 수 있게 됩니다. 또한 섬에서 알리고자 하는 플레이어 목록이 있으면 알파벳순으로 이름을 정렬하여 쉽게 표시할 수 있습니다.

다음 각 예시에서는 다양한 방식으로 정렬을 사용하지만, 자세히 살펴보면 모든 예시가 목표를 달성하기 위해 정렬 알고리즘 을 사용합니다. 정렬 알고리즘은 목록을 정렬해 주는 로직을 구현하며, 필요에 따라 선택할 수 있는 다양한 타입의 알고리즘이 있습니다. 정렬은 강력한 툴이지만, 정렬을 프로젝트에 통합하려는 경우 그 작동 방식을 이해하는 게 중요합니다. 이 페이지에서는 정렬에 대한 주요 아이디어와 프로젝트에 가장 적합한 알고리즘을 선택하는 방법을 설명합니다. 특정 정렬 알고리즘 구현에 대한 내용은 이 페이지 끝에 있는 링크를 확인하세요.

병합 정렬

병합 정렬은 분할 정복 정렬 알고리즘입니다. 분할 정복 정렬이란 더 작은 그룹으로 정렬해야 하는 엘리먼트 그룹을 나눈 다음, 그러한 더 작은 그룹을 정렬하는 방식입니다. 그런 다음 더 작은 그룹이 이미 정렬되어 있다는 것을 알고 있는 상태에서 해당 그룹을 결합합니다.

병합 정렬 구현하기

다음 구현은 분할된 배열을 병합 정렬하도록 자신을 호출합니다. 따라서 이는 재귀 함수가 됩니다. 재귀 함수를 사용할 경우 무한 재귀를 방지하기 위해 베이스 케이스를 지정해야 합니다. 이 알고리즘은 매번 배열을 절반으로 분할하고 베이스 케이스는 하나의 엘리먼트만 있는 배열입니다. 따라서 배열은 하나의 엘리먼트로 시작하면 정렬된 것으로 간주되며, 그러면 다른 단일 엘리먼트 배열과 병합할 수 있게 됩니다. 이 과정을 계속하여 전체 엘리먼트 배열로 거슬러 올라갈 수 있습니다.

아래 구현한 예시는 파라미터에 파라미터 타입을 사용한 일반 예시입니다. 엘리먼트에 원하는 타입을 사용할 수 있으며, 실행인자로 자체적인 비교 함수를 사용할 수 있습니다. 따라서 정렬할 정수 배열을 사용하거나, 정렬할 수 있는 클래스와 같이 더 복잡한 타입의 배열을 사용할 수 있습니다. Compare 함수는 자체 커스텀 함수를 전달할 수 있는 또 다른 파라미터입니다. 가장 작은 것에서 가장 큰 것으로 정렬하거나 클래스의 특정 필드를 기준으로 정렬하려는 경우, 이러한 일반 함수 구현을 수정하지 않고도 커스텀 함수에 해당 방식을 지정할 수 있습니다.

다음 단계를 따라 Verse에서 병합 정렬을 구현합니다.

  1. 일단 배열에 엘리먼트가 하나만 있는 베이스 케이스를 작성해 보겠습니다. 엘리먼트가 하나 이하인 경우 함수로 전달된 배열 실행인자를 반환합니다.

     MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
     Length:int = Array.Length
     if:
         Length > 1 # 배열에 엘리먼트가 두 개 이상 있는지 확인합니다. 하나 이하면 베이스 케이스에 도달한 것입니다.
     else:
         # 베이스 케이스에 도달했기 때문에 전달된 배열을 반환합니다.
         Array

  2. 그런 다음 배열을 절반으로 분할합니다.

     MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
     Length:int = Array.Length
     if:
         Length > 1 # 배열에 엘리먼트가 두 개 이상 있는지 확인합니다. 하나 이하면 베이스 케이스에 도달한 것입니다.
         Mid:int = Floor(Length / 2) # 배열의 중간 인덱스를 가져옵니다.
         Left:[]t = Array.Slice[0, Mid] # 배열을 절반으로 분할합니다. 여기에 시작부터 Mid - 1 인덱스까지의 엘리먼트가 있습니다.
         Right:[]t = Array.Slice[Mid] # 배열을 절반으로 분할합니다. 여기에 Mid 인덱스부터 배열 끝까지의 엘리먼트가 있습니다.
     else:
         # 베이스 케이스에 도달했기 때문에 전달된 배열을 반환합니다.
         Array

  3. 초기 배열의 각 절반에서 MergeSort 를 호출한 다음 나눠진 두 부분을 Merge 합니다.

     MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
     Length:int = Array.Length
     if:
         Length > 1 # 배열에 엘리먼트가 두 개 이상 있는지 확인합니다. 하나 이하면 베이스 케이스에 도달한 것입니다.
         Mid:int = Floor(Length / 2) # 배열의 중간 인덱스를 가져옵니다.
         Left:[]t = Array.Slice[0, Mid] # 배열을 절반으로 분할합니다. 여기에 시작부터 Mid - 1 인덱스까지의 엘리먼트가 있습니다.
         Right:[]t = Array.Slice[Mid] # 배열을 절반으로 분할합니다. 여기에 Mid 인덱스부터 배열 끝까지의 엘리먼트가 있습니다.
     then:
         # 배열의 왼쪽 절반에서 MergeSort를 호출합니다.
         LeftSorted:[]t = MergeSort(Left, Compare)

         # 배열의 오른쪽 절반에서 MergeSort를 호출합니다.
         RightSorted:[]t = MergeSort(Right, Compare)

         # 두 배열을 결합한 다음 결과를 반환합니다.
         Merge(LeftSorted, RightSorted, Compare)
     else:
         # 베이스 케이스에 도달했기 때문에 전달된 배열을 반환합니다.
         Array

  4. 분할된 두 부분을 다시 병합할 때, 각 배열의 엘리먼트를 비교한 다음 양쪽 배열의 모든 엘리먼트가 추가될 때까지 결과로 생성되는 배열에 엘리먼트를 추가합니다. 이렇게 하려면 각 배열에서 위치를 추적하는 인덱스 변수가 있어야 합니다. 매번 Compare 함수가 성공할 때마다 왼쪽 배열 엘리먼트를 추가해야 합니다. 그런 다음 인덱스 변수를 배열의 다음 위치로 이동하거나, 아니면 오른쪽 배열 엘리먼트에서도 동일한 작업을 수행해야 합니다. 배열 중 하나의 엘리먼트가 모두 추가되었으면 나머지 배열의 남은 엘리먼트를 추가합니다. 나머지 배열이 이미 정렬되었으므로 이렇게 추가할 수 있습니다.

     # 비교 함수에 따라 분할된 배열을 순서대로 결합하는 MergeSort의 헬퍼 함수입니다.
 Merge(Left:[]t, Right:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
     var LeftIndex:int = 0
     var RightIndex:int = 0
     var MergedArray:[]t = array{}
    
     # 배열의 모든 엘리먼트에서 루프하여 엘리먼트를 MergedArray 변수에 추가합니다.
     loop:
         if (LeftElement := Left[LeftIndex], RightElement := Right[RightIndex]):
             # 왼쪽 절반 배열의 엘리먼트를 오른쪽 절반 배열의 엘리먼트와 함께 확인합니다.
             # 전달된 비교 함수를 실행인자로 사용합니다.
             if (Compare[LeftElement, RightElement]):
                 set MergedArray += array{LeftElement}
                 set LeftIndex += 1
             else:
                 set MergedArray += array{RightElement}
                 set RightIndex += 1
         else:
             # 여기까지 배열 중 하나의 엘리먼트를 모두 추가했습니다.
             # 이제 병합할 엘리먼트가 아직 있는 배열을 확인하고 남은 엘리먼트를 모두 추가합니다.
             if (LeftIndex >= Left.Length):
                 option{set MergedArray += Right.Slice[RightIndex]}
             else:
                 option{set MergedArray += Left.Slice[LeftIndex]}
             # 모든 엘리먼트를 추가했으므로 루프를 종료합니다.
             break

     # 병합된 배열을 반환합니다.
     MergedArray

전체 스크립트

    # 한 배열을 둘로 분할하여 분할된 각 배열을 정렬한 다음, 다시 병합하는 분할 정복 정렬 알고리즘입니다.
    # 이는 함수가 자신을 호출하여 분할된 배열을 병합 정렬하는 재귀 구현 예시입니다.
    # 베이스 케이스(재귀를 중단하는 조건)는 배열에 엘리먼트가 하나만 있는 경우입니다.
    # 이는 파라미터 타입을 사용한 일반 구현 예시로, 원하는 타입을 입력하고 자체적인 비교 함수를 실행인자로 사용할 수 있습니다.
    MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
        Length:int = Array.Length
        if:
            Length > 1 # 배열에 엘리먼트가 두 개 이상 있는지 확인합니다. 하나 이하면 베이스 케이스에 도달한 것입니다.
            Mid:int = Floor(Length / 2) # 배열의 중간 인덱스를 가져옵니다.
            Left:[]t = Array.Slice[0, Mid] # 배열을 절반으로 분할합니다. 여기에 시작부터 Mid - 1 인덱스까지의 엘리먼트가 있습니다.
            Right:[]t = Array.Slice[Mid] # 배열을 절반으로 분할합니다. 여기에 Mid 인덱스부터 배열 끝까지의 엘리먼트가 있습니다.
        then:
            # 배열의 왼쪽 절반에서 MergeSort를 호출합니다.
            LeftSorted:[]t = MergeSort(Left, Compare)

            # 배열의 오른쪽 절반에서 MergeSort를 호출합니다.
            RightSorted:[]t = MergeSort(Right, Compare)

            # 두 배열을 결합한 다음 결과를 반환합니다.
            Merge(LeftSorted, RightSorted, Compare)
        else:

            # 베이스 케이스에 도달했기 때문에 전달된 배열을 반환합니다.
            Array

    # 비교 함수에 따라 분할된 배열을 순서대로 결합하는 MergeSort의 헬퍼 함수입니다.
    Merge(Left:[]t, Right:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
        var LeftIndex:int = 0
        var RightIndex:int = 0
        var MergedArray:[]t = array{}

        # 배열의 모든 엘리먼트에서 루프하여 엘리먼트를 MergedArray 변수에 추가합니다.
        loop:
            if (LeftElement := Left[LeftIndex], RightElement := Right[RightIndex]):
                # 왼쪽 절반 배열의 엘리먼트를 오른쪽 절반 배열의 엘리먼트와 함께 확인합니다.
                # 전달된 비교 함수를 실행인자로 사용합니다.
                if (Compare[LeftElement, RightElement]):
                    set MergedArray += array{LeftElement}
                    set LeftIndex += 1
                else:
                    set MergedArray += array{RightElement}
                    set RightIndex += 1
            else:
                # 여기까지 배열 중 하나의 엘리먼트를 모두 추가했습니다.
                # 이제 병합할 엘리먼트가 아직 있는 배열을 확인하고 남은 엘리먼트를 모두 추가합니다.
                if (LeftIndex >= Left.Length):
                    option{set MergedArray += Right.Slice[RightIndex]}
                else:
                    option{set MergedArray += Left.Slice[LeftIndex]}
                # 모든 엘리먼트를 추가했으므로 루프를 종료합니다.
                break

        # 병합된 배열을 반환합니다.
        MergedArray

알고리즘 선택하기

많은 정렬 알고리즘이 유사한 아이디어를 따르지만, 몇 가지 사항으로 인해 서로 차이가 있으며 이는 알고리즘 성능에 큰 영향을 미칠 수 있습니다.

시간 복잡도

알고리즘은 시간을 사용하며, 수행해야 하는 작업이 많아질수록 그러한 시간은 늘어납니다. 알고리즘이 해결하려는 문제의 복잡도에는 여러 요소가 영향을 미치는데, 이를 처리하는 데 걸리는 시간을 시간 복잡도 라고 합니다.

알고리즘 완료에 걸리는 정확한 시간을 계산하는 건 컴퓨터 하드웨어, 다른 실행 코드 또는 작업 중인 데이터 타입과 같은 다양한 요소로 인해 거의 불가능하므로, 시간 복잡도는 알고리즘 완료에 필요한 작업의 수인 연산으로 대신 측정됩니다. 각 알고리즘이 다르기 때문에 데이터세트를 처리하는 데 걸리는 시간은 빅-오(Big O) 표기법을 사용하여 표현합니다. 빅-오 표기법은 필요한 연산의 정확한 수를 설명하는 게 아니라, 알고리즘에 입력하는 목록의 크기가 증가함에 따라 그 수가 어떻게 변하는지를 설명합니다.

예를 들어 목록에서 가장 작은 수를 찾는 알고리즘을 작성한다고 가정해 보겠습니다. 목록이 순서대로 되어 있는지 알 수 없기 때문에 알고리즘은 모든 숫자를 확인해야 가장 작은 숫자를 알 수 있습니다. 목록에 아이템이 세 개 있으면 알고리즘이 확인을 3회 하고 아이템이 열 개 있으면 알고리즘이 확인을 10회 합니다. 연산 수는 목록의 입력 크기에 따라 선형으로 증가하므로 시간 복잡도는 선형인 O(n) 이며, 여기서 n은 목록의 아이템 수입니다. 알고리즘이 각각 확인 후에 아이템을 다른 목록에 복사하는 경우와 같이 아이템당 두 번의 연산을 수행해야 하면, 연산 수가 2 * 아이템 수이므로 시간 복잡도는 O(2n) 이 됩니다.

알고리즘으로 목록에 아이템이 있는지만 확인하고 싶다면 어떻게 해야 할까요? 알고리즘은 입력 크기에 관계없이 한 번의 연산만 수행하므로 시간 복잡도는 상수인 O(1) 이 됩니다. 2차 시간(O(n^2)) 또는 계승 시간(O(n!))과 같은 많은 다른 예가 있지만, 중요한 건 이들 각각이 입력 크기에 따라 수행되는 연산 수가 어떻게 증가하는지를 설명해 준다는 것입니다.

정렬 복잡도

정렬 알고리즘의 시간 복잡도를 측정하는 것은 정렬 전 목록의 다양한 상태 때문에 훨씬 더 복잡해집니다. 이미 정렬이 된 경우에는 어떻게 해야 할까요? 역으로 정렬이 된 경우에는 어떻게 해야 할까요? 정렬 알고리즘의 성능은 이러한 요소에 따라 크게 달라질 수 있으므로, 정렬 알고리즘은 일반적으로 최상, 최악 및 평균 케이스 시간 복잡도로 측정합니다.

예를 들어 버블 정렬 알고리즘을 살펴보겠습니다. 최상의 케이스에서 이미 정렬된 목록이 주어진 경우, 버블 정렬은 모든 엘리먼트 쌍을 확인하기만 하면 되며 대체할 필요가 없습니다! 따라서 최상의 케이스에서는 시간 복잡도가 O(n) 이 되어 좋은 결과가 나옵니다! 하지만 목록이 역으로 정렬된 반대 시나리오는 어떨까요? 이 경우 버블 정렬은 확인을 n 회 수행해야 하고 목록에서 모든 엘리먼트를 n 회 대체해야 합니다. 따라서 최악의 케이스에서는 시간 복잡도가 n * n, 즉 O(n^2) 가 됩니다. 이는 다른 정렬 알고리즘에 비해 느린 것으로 간주되며, 10개의 엘리먼트 목록을 처리하는 데 최소 100회의 연산이 필요하기 때문에 이내 작업을 관리하기 어려워집니다. 엘리먼트가 100개가 된다면 얼마나 많은 연산을 해야 할까요? 1,000개는 또 어떨까요?

정렬 알고리즘은 최상의 케이스와 최악의 케이스가 아닌, 보통 평균 케이스에 가까운 성능을 보입니다. 예를 들어 병합 정렬의 평균 케이스 복잡도는 O(nlogn) 입니다. 이 복잡도가 좋은 벤치마크로 간주되는 이유는, 다른 많은 일반적인 정렬 알고리즘이 이 수준이거나 이에 매우 근접한 최상, 최악, 평균 케이스 복잡도를 가지기 때문입니다. 위에 나온 버블 정렬은 평균 케이스 복잡도가 O(n^2) 이므로 평균 케이스 기준으로도 여전히 상대적으로 느린 것입니다.

입력 타입에 관계없이 코드가 빠르게 실행되고 비슷한 성능을 내야 하므로, 알고리즘을 선택할 때 시간 복잡도를 알고 있는 것이 중요합니다. 흔히 알려진 효율적인 정렬 알고리즘의 몇 가지 예는 병합 정렬과 퀵 정렬을 확인하세요. 두 알고리즘 모두 동일한 최상, 최악 및 O(nlogn) 평균 케이스 복잡도를 가지며, 모든 정렬 상황에 있어 좋은 출발점이 됩니다.

공간 복잡도

시간 복잡도 외에도, 정렬을 완료하기 위해 알고리즘이 얼마나 많은 항목을 만들어야 하는지도 고려해야 합니다. 이를 공간 복잡도 라고 하며, 이에 따라 알고리즘을 실행할 때 생성되는 추가 데이터의 양이 결정됩니다. 시간 복잡도와 마찬가지로 공간 복잡도는 빅-_오_ 표기법으로 측정되며, 이는 알고리즘마다 달라집니다. 예를 들어 병합 정렬은 목록을 n 개의 하위 목록으로 나누기 때문에 O(n) 의 공간 복잡도를 가집니다. 오브젝트를 제자리에서 정렬하는 알고리즘은 공간 복잡도가 O(1) 입니다(새로운 데이터를 만들지 않고 기존 데이터만 수정하므로). 매우 큰 목록을 작업하는 경우 알고리즘을 선택할 때 공간 복잡도에 주의해야 합니다.

Verse는 함수 프로그래밍 언어이므로 데이터 구조 API 연산은 입력으로 전달된 원본 아이템의 수정된 버전을 반환합니다. 예를 들어 Insert() 및 RemoveElement() 배열 함수 모두 원본 배열을 수정하지 않는 대신, 함수가 실행된 후에 새 배열을 만들고 반환합니다. 따라서 새로운 엘리먼트의 생성을 처리할 수 있도록, 더 많은 시간과 더 큰 공간 복잡도를 요구할 수 있습니다.

안정성

정렬 시 알고리즘은 종종 동점을 마주하게 됩니다. 예를 들어 각각 5점을 득점한 두 명의 플레이어가 주어지면, 알고리즘은 이들을 어떻게 정렬해야 할까요? 이 시나리오에서 안정 알고리즘 은 정렬 후 목록에서 동일한 엘리먼트가 나타나는 순서를 유지합니다. 따라서 정렬 전에 플레이어 1이 플레이어 2보다 먼저 목록에 전달된 경우, 정렬된 목록에서 여전히 플레이어 1이 플레이어 2 앞에 있게 됩니다.

하지만 불안정 알고리즘 은 이러한 순서를 유지하지 않으며, 플레이어 2가 플레이어 1보다 먼저 나타날 수 있습니다. 이는 코드가 목록에서 처음 몇 개 엘리먼트를 고려해야 하는 경우에 중요한데, 리더보드에 점수별로 상위 3명의 플레이어를 표시하도록 하려는 경우가 이에 해당합니다. 그러한 상황에서는 안정 알고리즘을 사용하여 해당 점수를 먼저 달성한 사람이 리더보드에 남아 있도록 해야 합니다.

알고리즘 테스트 및 프로파일링하기

주어진 시간 및 공간 복잡도에서 알고리즘이 어떻게 실행될지 알고 있는 것도 좋지만, 실제 입력에서 알고리즘이 실제 어떤 성능을 내는지 측정하는 것이 훨씬 더 중요합니다. 정렬 알고리즘을 개발하는 건 어려울 수 있으며, 코드가 모든 입력에서 일관되게 작동하는지 파악하기 어려울 수 있습니다. 이 때문에 테스트가 필요한 것입니다. 테스트 함수를 설정하면 코드의 정확도를 측정하고 코드를 개발하면서 코드가 어떻게 작동하는지 확인할 수 있습니다. 또한 테스트하고 있는 알고리즘의 구현을 변경할 경우 성능 저하가 있는지도 확인할 수 있습니다. 다음 단계를 따라 정렬 알고리즘에 대한 테스트 파일과 성능에 대한 출력 데이터를 설정합니다.

  1. RunArrayTest 로 명명된 실패 가능 함수를 생성합니다.

     # 배열을 정렬하고 코드를 프로파일링하기 위한 테스트 함수입니다.
 RunArrayTest()<decides><transacts>:void=

  2. 정렬을 실행할 배열의 실행인자와 사용할 비교 함수를 추가합니다.

     # 배열을 정렬하고 코드를 프로파일링하기 위한 테스트 함수입니다.
 RunArrayTest(ActualArray:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:subtype(comparable))<decides><transacts>:void=
     # 병합 정렬 수행
     ResultArray := SortingAlgorithms.MergeSort(ActualArray, Compare)

  3. 이제 정렬된 배열을 원하는 예상 배열과 비교해야 합니다. 예상 배열의 실행인자를 추가하여 정렬된 실제 배열과 비교한 후 결과가 올바른지 확인합니다.

    ResultArray 의 엘리먼트와 ExpectedArray 의 엘리먼트를 비교합니다. RunArrayTest 함수는 실패 가능하므로 엘리먼트가 일치하지 않으면 테스트 함수가 실패합니다.

     # 배열을 정렬하고 코드를 프로파일링하기 위한 테스트 함수입니다.
 RunArrayTest(ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:subtype(comparable))<decides><transacts>:void=
     # 병합 정렬 수행
     ResultArray := SortingAlgorithms.MergeSort(ActualArray, Compare)

     # 테스트를 통과하고 예상대로 배열을 정렬하는지 확인합니다.
     for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]):
         Result = Expected

  4. 각 단계에서 배열을 출력할 실행인자 함수를 추가하여 테스트에 실패한 경우 배열을 비교합니다. 그러면 테스트 중인 코드를 수정할 방법을 알 수 있습니다.

     # 배열을 정렬하고 코드를 프로파일링하기 위한 테스트 함수입니다.
 RunArrayTest(ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t, ArrayToString(:[]t)<transacts>:string where t:subtype(comparable))<decides><transacts>:void=
     # 병합 정렬 수행
     ResultArray := SortingAlgorithms.MergeSort(ActualArray, Compare)

     # 문제 해결을 위해 실제, 예상 및 결과 배열을 출력합니다.
     ProjectLog("Actual: {ArrayToString(ActualArray)}")
     ProjectLog("Expected: {ArrayToString(ExpectedArray)}")
     ProjectLog("Result: {ArrayToString(ResultArray)}")

     # 테스트를 통과하고 예상대로 배열을 정렬하는지 확인합니다.
     for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]):
         Result = Expected

  5. 테스트 함수는 결과의 정확도를 확인하지만, 테스트를 통해 더 많은 정보를 얻을 수도 있습니다. 프로파일 표현식을 사용하면, 알고리즘이 완료되는 데 걸리는 시간을 기록하여 알고리즘 성능을 측정할 수 있습니다.

    이는 서로 다른 정렬 알고리즘의 성능을 비교하거나 서로 다른 입력이 주어졌을 때 알고리즘이 어떻게 실행되는지 테스트하려는 경우에 유용합니다. 개별 알고리즘은 최상의 입력과 최악의 입력에 따라 매우 다른 성능을 보일 수 있으며, 프로파일링을 사용하면 그러한 케이스를 찾고 테스트하여 무엇을 주의해야 할지 알 수 있습니다. 테스트를 여러 번 반복해 알고리즘의 평균 성능을 측정하고 주어진 크기의 입력에서 알고리즘이 어떠한 성능을 보일지 추정할 수 있습니다.

  6. Description 으로 명명한 문자열 실행인자를 추가합니다. 이는 테스트에서 집중하는 부분이 무엇인지를 설명합니다. 이를 profile 표현식에 추가하면 시간이 지정된 값과 함께 설명을 로그에 기록할 수 있습니다.

     # 배열을 정렬하고 코드를 프로파일링하기 위한 테스트 함수입니다.
 RunArrayTest(Description:string, ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t, ArrayToString(:[]t)<transacts>:string where t:subtype(comparable))<decides><transacts>:void=

     # 병합 정렬을 수행하고 코드를 프로파일링합니다.
     ResultArray := profile(Description):
         SortingAlgorithms.MergeSort(ActualArray, Compare)

     # 문제 해결을 위해 실제, 예상 및 결과 배열을 출력합니다.
     ProjectLog("Actual: {ArrayToString(ActualArray)}")
     ProjectLog("Expected: {ArrayToString(ExpectedArray)}")
     ProjectLog("Result: {ArrayToString(ResultArray)}")
    
     # 테스트를 통과하고 예상대로 배열을 정렬하는지 확인합니다.
     for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]):
         Result = Expected

테스트 케이스 작성하기

단순하게 시작하는 것이 좋습니다. 테스트하는 항목을 분리하세요. 정수 배열을 테스트하여 가장 작은 값에서 가장 큰 값으로 정렬합니다.

  1. 정수 비교 함수를 생성합니다.

     # 정수를 가장 작은 수부터 가장 큰 수까지 정렬하기 위한 실행인자로 사용할 비교 함수입니다.
 IsIntSmallerThan(Left:int, Right:int)<decides><transacts>:int=
     Left < Right

  2. 정수 배열을 문자열로 변환할 헬퍼 함수를 생성합니다.

     # 정수 배열을 문자열로 변환하는 헬퍼 함수입니다.
 IntArrayToString(Array:[]int)<transacts>:string=
     var ConvertedToString:string = "["
     for (Index -> Element : Array):
         set ConvertedToString += "{Element}"
         if (Index < Array.Length - 1):
             set ConvertedToString += ", "
     set ConvertedToString += "]"

  3. Verse 장치를 생성해 테스트를 실행합니다.

     # 이 파일에는 정렬 알고리즘이 예상대로 동작하는지 확인하기 위한 테스트가 포함되어 있습니다.
 # 또한 테스트에는 알고리즘의 성능을 확인하기 위한 코드 프로파일링 부분도 있습니다.

 using { /Fortnite.com/Devices }
 using { /UnrealEngine.com/Temporary/Diagnostics }
 using { /Verse.org/Simulation }
 using { /Verse.org/Random }

 my_log_channel<public> := class(log_channel):

 # 로그가 있는 클래스에 존재하지 않는 함수에서 메시지를 출력하기 위한 프로젝트 단위 '로거'입니다.
 # 비로거 출력은 <no_rollback>이므로, <transacts> 함수에서 사용할 수 없습니다.
 ProjectLog<public>(Message:[]char, ?Level:log_level = log_level.Normal)<transacts>:void=
     Logger := log{Channel := my_log_channel}
     Logger.Print(Message, ?Level := Level)

 # 레벨에 배치할 수 있는 Verse로 제작된 포크리 장치입니다.
 # 테스트 및 프로파일 코드를 실행할 레벨에 배치합니다.
 test_sorting := class(creative_device):

     # 실행 중인 게임에서 장치가 시작되면 실행됩니다.
     OnBegin<override>()<suspends>:void=
         # 테스트에 사용할 예시 배열입니다.
         Test1ExpectedIntArray:[]int = array{}
         Test1ActualIntArray:[]int = array{}

         # 테스트를 실행하고 실패 또는 성공 여부를 보고합니다.
         if:
             RunArrayTest["Integer array in order from smallest to largest", Test1ActualIntArray, Test1ExpectedIntArray, IsIntSmallerThan, IntArrayToString]
         then:
             ProjectLog("All tests passed.")
         else:
             ProjectLog("One or more tests failed.")

  4. 이제 테스트 배열을 값으로 채웁니다.

     var ArrayLength:int = GetRandomInt(10, 100)
         Test1ExpectedIntArray:[]int =
             for (Count := 0..ArrayLength):
             	수
         Test1ActualIntArray:[]int = Shuffle(Test1ExpectedIntArray)

  5. Verse 장치를 레벨로 드래그하여 테스트를 실행합니다.

실행해 볼 수 있는 테스트를 위한 아이디어가 아래에 더 나와 있습니다.

* 정수 배열을 가장 큰 수부터 가장 작은 수로 정렬합니다.

        # 정수를 가장 큰 수부터 가장 작은 수까지 정렬하기 위한 실행인자로 사용할 비교 함수입니다.
        IsIntGreaterThan(Left:int, Right:int)<decides><transacts>:int=
            Left > Right

* 반복되는 값이 있는 정수 배열을 정렬합니다.

        Test3ExpectedIntArray:[]int = array{0, 1, 1, 2, 3, 3}
        Test3ActualIntArray:[]int = Shuffle(Test3ExpectedIntArray)

* 클래스 필드 중 하나를 기준으로 클래스를 정렬합니다.

        # 정렬을 테스트하기 위한 예시 클래스입니다.
        player_stats := class<unique>:
            Wins:int = 0
            RoundsPlayed:int = 0

        # 승리를 가장 작은 값부터 가장 큰 값까지 정렬하기 위한 실행인자로 사용할 비교 함수입니다.
        IsWinsSmallerThan(Left:player_stats, Right:player_stats)<decides><transacts>:player_stats=
            Left.Wins < Right.Wins
            Left

        # 플레이어 통계 비교 값을 문자열로 변환하는 헬퍼 함수입니다.
        PlayerStatsWinsArrayToString(Array:[]player_stats)<transacts>:string=
            var ConvertedToString:string = "["

            for (Index -> Element : Array):
                set ConvertedToString += "{Element.Wins}"
                if (Index < Array.Length - 1):
                    set ConvertedToString += ", "
            set ConvertedToString += "]"

전체 스크립트

    # 이 파일에는 정렬 알고리즘이 예상대로 동작하는지 확인하기 위한 테스트가 포함되어 있습니다.
    # 또한 테스트에는 알고리즘의 성능을 확인하기 위한 코드 프로파일링 부분도 있습니다.

    using { /Fortnite.com/Devices }
    using { /UnrealEngine.com/Temporary/Diagnostics }
    using { /Verse.org/Simulation }
    using { /Verse.org/Random }

    my_log_channel<public> := class(log_channel):

    # 로그가 있는 클래스에 존재하지 않는 함수에서 메시지를 출력하기 위한 프로젝트 단위 '로거'입니다.
    # 비로거 출력은 <no_rollback>이므로, <transacts> 함수에서 사용할 수 없습니다.
    ProjectLog<public>(Message:[]char, ?Level:log_level = log_level.Normal)<transacts>:void=
        Logger := log{Channel := my_log_channel}
        Logger.Print(Message, ?Level := Level)

    # 레벨에 배치할 수 있는 Verse로 제작된 포크리 장치입니다.
    # 테스트 및 프로파일 코드를 실행할 레벨에 배치합니다.
    test_sorting := class(creative_device):

        # 실행 중인 게임에서 장치가 시작되면 실행됩니다.
        OnBegin<override>()<suspends>:void= 

            # 테스트에 사용할 예시 배열입니다.
            var ArrayLength:int = GetRandomInt(10, 100)

            Test1ExpectedIntArray:[]int =
                for (Count := 0..ArrayLength):
                	수

            Test1ActualIntArray:[]int = Shuffle(Test1ExpectedIntArray)

            set ArrayLength = GetRandomInt(10, 100)

            Test2ExpectedIntArray:[]int = for (Count := 0..ArrayLength):
                ArrayLength - Count

            Test2ActualIntArray:[]int = Shuffle(Test2ExpectedIntArray)

            Test3ExpectedIntArray:[]int = array{0, 1, 1, 2, 3, 3}

            Test3ActualIntArray:[]int = Shuffle(Test3ExpectedIntArray)

            set ArrayLength = GetRandomInt(10, 100)
            Test4ExpectedPlayerStats:[]player_stats = for (Count := 0..ArrayLength):
                player_stats:
                    Wins := ArrayLength - Count
                    RoundsPlayed := GetRandomInt(Count, Count * 30)

            Test4ActualPlayerStats:[]player_stats = Shuffle(Test4ExpectedPlayerStats)

            # 테스트를 실행하고 실패 또는 성공 여부를 보고합니다.
            if:
                RunArrayTest["Integer array in order from smallest to largest", Test1ActualIntArray, Test1ExpectedIntArray, IsIntSmallerThan, IntArrayToString]
                RunArrayTest["Integer array in order from largest to smallest", Test2ActualIntArray, Test2ExpectedIntArray, IsIntGreaterThan, IntArrayToString]
                RunArrayTest["Integer array in order from smallest to largest with repeats", Test3ActualIntArray, Test3ExpectedIntArray, IsIntSmallerThan, IntArrayToString]
                RunArrayTest["Player stats array in order from largest # wins to smallest", Test4ActualPlayerStats, Test4ExpectedPlayerStats, IsWinsGreaterThan, PlayerStatsWinsArrayToString]
            then:
                ProjectLog("All tests passed.")
            else:
                ProjectLog("One or more tests failed.")

    # 배열을 정렬하고 코드를 프로파일링하기 위한 테스트 함수입니다.
    RunArrayTest(Description:string, ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t, ArrayToString(:[]t)<transacts>:string where t:subtype(comparable))<decides><transacts>:void=

        # 병합 정렬을 수행하고 코드를 프로파일링합니다.
        ResultArray := profile(Description):
            SortingAlgorithms.MergeSort(ActualArray, Compare)

        # 문제 해결을 위해 실제, 예상 및 결과 배열을 출력합니다.
        ProjectLog("Actual: {ArrayToString(ActualArray)}")
        ProjectLog("Expected: {ArrayToString(ExpectedArray)}")
        ProjectLog("Result: {ArrayToString(ResultArray)}")

        # 테스트를 통과하고 예상대로 배열을 정렬하는지 확인합니다.
        for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]):
            Result = Expected

    # 정수 배열을 문자열로 변환하는 헬퍼 함수입니다.
    IntArrayToString(Array:[]int)<transacts>:string=
        var ConvertedToString:string = "["
        for (Index -> Element : Array):
            set ConvertedToString += "{Element}"
            if (Index < Array.Length - 1):
                set ConvertedToString += ", "
        set ConvertedToString += "]"

    # 플레이어 통계 비교 값을 문자열로 변환하는 헬퍼 함수입니다.
    PlayerStatsWinsArrayToString(Array:[]player_stats)<transacts>:string=
        var ConvertedToString:string = "["
        for (Index -> Element : Array):
            set ConvertedToString += "{Element.Wins}"
            if (Index < Array.Length - 1):
                set ConvertedToString += ", "
        set ConvertedToString += "]"

    # 정수를 가장 작은 수부터 가장 큰 수까지 정렬하기 위한 실행인자로 사용할 비교 함수입니다.
    IsIntSmallerThan(Left:int, Right:int)<decides><transacts>:int=
        Left < Right

    # 정수를 가장 큰 수부터 가장 작은 수까지 정렬하기 위한 실행인자로 사용할 비교 함수입니다.
    IsIntGreaterThan(Left:int, Right:int)<decides><transacts>:int=
        Left > Right

    # 정렬을 테스트하기 위한 예시 클래스입니다.
    player_stats := class<unique>:
        Wins:int = 0
        RoundsPlayed:int = 0

    # 승리를 가장 작은 값부터 가장 큰 값까지 정렬하기 위한 실행인자로 사용할 비교 함수입니다.
    IsWinsSmallerThan(Left:player_stats, Right:player_stats)<decides><transacts>:player_stats=
        Left.Wins < Right.Wins
        Left

    # 승리를 가장 큰 값부터 가장 작은 값까지 정렬하기 위한 실행인자로 사용할 비교 함수입니다.
    IsWinsGreaterThan(Left:player_stats, Right:player_stats)<decides><transacts>:player_stats=
        Left.Wins > Right.Wins
        Left

직접 해보기

  • 다른 정렬 알고리즘을 구현해 보세요. 알고리즘을 다르게 구현한 예시를 아래에서 찾아볼 수 있습니다.

  • 테스트 알고리즘의 적용 범위를 늘리려면 테스트 케이스를 더 추가하세요. 현재 테스트 알고리즘을 적용할 수 없는 엣지 케이스를 생각해 낼 수 있나요? 더 복잡한 데이터 타입은 어떻게 해야 할까요?

Ask questions and help your peers Developer Forums

Write your own tutorials or read those from others Learning Library

On this page