[Sort] 프로그래밍 언어들의 sort 함수에 대한 user-defined function에 대한 이야기

개요

요즘 언어들은 정렬 함수 정도는 기본적으로 제공하고 있다.대부분 정렬에 대해서 이해하기 시작하는 단계는 코딩 테스트가 아닐까 싶다. 문제마다 정렬 함수가 굳이 있는데, 매 경우마다 새로운 함수를 만들 필요는 없다.

 

sort 함수들은 대부분 compare 혹은 key 등의 이름들로 사용자 정의 함수를 이용하여, 정렬할 수 있도록 도와준다. 개념을 알고 있다가도, 복잡한 정렬이 필요할때마다 기억이 잘 안나서 정리 해 둔다.

 

사용자 정의 함수(user-defined function, customize function)

대부분의 언어에서 sort함수가 사용하는 사용자 정의 함수는 true, false 혹은 < 0, 0, > 0 등의 값을 return 하도록 설계한다.

c

void qsort (void* base, size_t num, size_t size, int (*comparator)(const void*,const void*));

c++

void sort( ExecutionPolicy&& policy, RandomIt first, RandomIt last, Compare comp );

python3

sorted(words, key=cmp_to_key(strcoll))

nodejs

sort((a, b) => { /* … */ } )

 

 

대부분의 언어들이 다음과 같은 룰을 따른다. 피연산자로 a, b가 입력되었다고 가정한다. 이때 a, b의 정렬 기준은 다음과 같다.

// C 예시코드
#include <stdio.h>      /* printf */
#include <stdlib.h>     /* qsort */

int values[] = { 40, 10, 100, 90, 20, 25 };

int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

int main ()
{
  int n;
  qsort (values, 6, sizeof(int), compare);
  for (n=0; n<6; n++)
     printf ("%d ",values[n]);
  return 0;
}

 

 

• a - b의 값이 0 보다 작으면(<0), a가 b보다 작다는 뜻임으로 a가 b요소 앞에 위치 시킨다.
• a - b의 값이 0 과 같으면(=0), a와 b가 같다는 뜻임으로, a와 b요소는 원래 위치에 그대로 있다.
• a - b의 값이 0 보다 크면(>0), a가 b보다 크다는 뜻임으로 a가 b요소 뒤에 위치 시킨다.

한번 이해하면 쉬운데, 한동안 안보다가 보면 긴가민가 싶다. 그때마다 공식 문서를 보면 되지만, 이번 기회에 머릿속에 박아 넣기를 빈다.

 

복잡한 정렬(예시)

이중 리스트나 , 이중 배열이나 복잡한 자료구조에서 복잡한 조건식에 의해서 정렬을 시키고 싶다면, 당연하게도 사용자 정의 함수를 사용하면 된다. 코드는 약식으로만 적었다.

 

a를 기준으로 오름차순 정렬을 하되, a가 같으면 b를 기준으로 오름차순 정렬하는 방법

c

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int x;
    int y;
} row;

int compare(const void *a, const void *b) {
    row A = *(row *)a;
    row B = *(row *)b;
    
    if (A.x > B.x)
        return 1;
    else if (A.x == B.x) {
        if (A.y > B.y)
            return 1;
        else
            return -1;
    } else{
    	return -1;
    }  
}

int main(){
	qsort(arr, n, sizeof(row), compare);
}

python3

result = [
    [123, 234],
    [1, 3],
    [2, 4],
    [1, 5]
]

result.sort(key=lambda data: (data[0], data[1]))
# python은 둘다 오름차순 기준일 때
# result.sort()만 호출해도, 정렬이 가능하다.

nodejs

let result = [
    [123, 234],
    [1, 3],
    [2, 4],
    [1, 5]
];

result.sort((a, b) => {
  return a[0] === b[0] ? a[1] - b[1] : a[0] - b[0];
});

 

references

https://cplusplus.com/reference/cstdlib/qsort/

https://docs.python.org/3/howto/sorting.html

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort