Sort() 를 보다 깊이있게 이해하기

C# 에서 정렬할 땐 당연히 Sort()를 쓴다. 그런데 그 안에서는 무슨 일이 일어날까? 이번 글에서는 Sort() 함수의 원형부터, 비교 기준을 전달하는 방식, 그리고 구조체 배열을 정렬하는 방법까지 하나씩 짚어보며 정렬의 구조를 제대로 파헤쳐 보겠습니다.

 

Sort() 함수의 원형

public static void Sort<T>(T[] array, Comparison<T> comparison);

 

public static
정적(static) 메서드이기 때문에, 어디서든 인스턴스없이 접근이 가능합니다. Array.Sort()

 

T [ ] array
정렬할 배열입니다.

제네릭 타입 <T> 이기 때문에 int[], string[], Item[]  등 어떤 자료형이건 상관이 없습니다.

 

Comparison<T> comparison 

비교 방식을 정해주는 대리자(delegate) 입니다.

 

Sort() 는 대리자를 통해서, 사용자가 원하는 방식으로 데이타를 정렬시킬 수 있는 함수입니다. 

내부적으로는 로직을 수행하다가 비교 판단이 필요할 때, 사용자가 만든 함수를 대리자를 통해 호출합니다.

그럼 이 대리자가 어떻게 생겼는지 알아보겠습니다. 

 

Comparison 대리자의 원형

public delegate int Comparison<in T>(T x, T y);

 

( T x, T y )

비교할 두 객체 입니다. 둘 다 동일한 타입 T 입니다. 

그리고 Sort() 의 원형에서 알 수 있듯이, 배열 변수 array 의 자료형과 동일합니다.

즉, 배열이 int [ ] 라면, 비교 함수의 매개 변수도 int 형이 됩니다. 

 

반환값 int

비교 결과는 정수형이며, 반환값에 따라 Sort() 는 다음과 같이 처리합니다.

•  양수 ( > 0 ) : 0 보다 크다면, 두 수 ( x, y) 의 자리를 교환.

•  음수 ( < 0 ) : 0 보다 작으면, 교환하지 않음

•  0 이면 두 수가 같다고 판단

 

< in T >
입력 전용 매개변수임을 의미합니다. 즉, x와 y를 참조하되 수정할 수는 없습니다. (값은 복사되지 않고 읽기 전용 참조로 전달됩니다.)

 

대리자에 대입할 수 있는 함수는 반환값이 int 이고, 매개 변수는 2개 이며, 자료형이 배열의 자료형과 동일한 함수입니다. 이 형태를 가진 함수를 구현한 후에 Sort() 함수에 인자로 넣어줍니다. 이제 delegate 에 대입할 수 있는 사용자 정의 함수를 직접 만들어 보겠습니다. 

 

사용자 정의 비교 함수 만들기 #1

Item 이라는 구조체 배열을 선언하고, Item 가격을 가지고 정렬하는 예제입니다.

// Item 구조체 정의
public struct Item
{
    public string name;
    public int price;
}

Item[] items =
{
    new Item { name = "Apple", price = 300 },
    new Item { name = "Banana", price = 100 },
    new Item { name = "Orange", price = 400 }
};

// 가격 기준으로 오름차순 정렬
Array.Sort(items, CompareByPrice);


// 가격 기준으로 비교하는 함수 (오름 차순)
public static int CompareByPrice(Item a, Item b)
{
    // a가 b보다 크면 자리 바꿈
    if (a.price > b.price)
        return 1;           
        
    // a가 더 작으면 그대로 둠    
    else if (a.price < b.price)
        return -1;          
        
    // 같으면 변화 없음
    return 0;               
}

 

CompareByPrice()

이 함수는 대리자 Comparison<T> comparison 과 정확히 일치합니다.

반환값은 int 이며, 배열 변수 items 의 자료형인 Item 구조체를 매개 변수 (Item a, Item b) 로 받습니다.

 

Array.Sort( items, CompareByPrice )

이 함수는 내부에서 비교 판단이 필요할 때마다, CompareByPrice()를 호출하며, 그 결과에 따라 items 배열을 정렬합니다. 앞에 위치한 a 의 가격 (a.price) 이, 뒤에 위치한 b 의 가격 (b.price) 보다 크면, 1 (양수) 을 돌려주기 때문에 두 객체 ( a, b ) 의 자리를 바꿉니다. 즉 가격을 오름차순으로 정렬합니다. 

 

가격 내림차순으로 정렬

Sort() 함수의 장점은 사용자 정의 함수를 어떻게 구현하느냐에 따라 정렬 방식이 바뀐다는 점입니다. 이번에는 CompareByPrice() 를 가격의 내림 차순으로 정렬해보겠습니다.

// 가격 기준으로 비교하는 함수 (내림 차순)
public static int CompareByPrice(Item a, Item b)
{
    // b가 a보다 크면 자리 바꿈
    if (b.price > a.price)
        return 1;           
        
    // b가 더 작으면 그대로 둠    
    else if (b.price < a.price)
        return -1;          
        
    // 같으면 변화 없음
    return 0;               
}

 

뒤에 위치한 b 의 가격이 앞에 놓인 a 의 가격보다 크다면, 자리를 바꾸면 됩니다.

 

간단한 비교식은 람다식으로도 가능

Array.Sort(items, (a, b) => a.price.CompareTo(b.price));

 

•  비교식이 간단하다면, CompareByPrice() 함수를 만들지 않고, 한 줄의 람다식으로도 가능합니다.

•  람다식 (a, b) => a.price.CompareTo(b.price) 는 Comparison<Item> 타입으로 자동 변환됩니다.

 

사용자 정의 비교 함수 만들기 #2

Npc 라는 구조체 배열을 선언하고, 거리를 기준으로 정렬하는 예제입니다.

public struct Npc
{
    public string name;
    public int x;
    public int y;
}

Npc[] npcs =
{
    new Npc { name = "Slime", x = 1, y = 1 },
    new Npc { name = "Orc", x = 5, y = 3 },
    new Npc { name = "Goblin", x = 2, y = 2 },
    new Npc { name = "Dragon", x = 10, y = 10 }
};

// 원점으로부터 떨어진 거리를 기준으로 정렬 (오름 차순)
Array.Sort(npcs, CompareByDistance);


public static int CompareByDistance(Npc a, Npc b)
{
    int distA = a.x * a.x + a.y * a.y;
    int distB = b.x * b.x + b.y * b.y;

    if (distA > distB)
        return 1;
    else if (distA < distB)
        return -1;
    return 0;
}

 

CompareByDistance()

거리는 항상 양수이고, 단순 비교이므로 Math.Sqrt() 를 하지 않았습니다. 

(Math.Sqrt() 는 계산 부하가 있는 함수이기 때문에, 생략 가능하다면 생략하는 것이 좋습니다)

 

핵심 요약

•  구조체 배열은 기본 정렬이 불가능하므로 비교 기준 함수가 필요합니다.

•  대리자는 int 를 반환하고, 매개 변수 (T, T) 를 갖는 함수를 요구합니다. 

•  Array.Sort() 또는 List<T>.Sort()에 이 대리자를 넘기면 사용자 정의 타입도 정렬이 가능합니다.

•  단순한 경우에는 람다식을 사용하면, 훨씬 간결하게 구현할 수 있습니다.