amsminn님의 면접 결과

안정정렬이란 정렬 후에 같은 대소관계(우선순위)를 가진 값, cmp(a, b), cmp(b, a) 모두 거짓인 a, b 쌍들이 정렬 후에도 같은 순서를 유지하는 정렬을 의미합니다. 대표적으로 머지소트가 있습니다. 결론적으로 quick sort는 안정 정렬이 아닙니다. 피봇보다 작은값, 큰값을 스왑시켜주는 과정에서 대소관계의 변형이 있을 수 있기 때문입니다. 하지만 퀵소트를 안정정렬로 구현하는 것이 불가능한가를 생각하면 그렇지 않습니다. 피봇 기준 왼쪽 구간과 오른쪽 구간을 스왑하는 방식 대신, 구간 크기만큼 메모리를 더 사용해서 작은값을 한쪽에 순서대로 밀어넣고, 큰값을 반대쪽에순서대로 밀어넣는 과정을 반복하면 안정정렬 구현이 가능합니다. 공간복잡도를 O(n)만큼 더사용하는 방법이고, 트레이드 오프가 있습니다. 또 공간복잡도를 같은 크기만큼 더사용하는 방법 하나가 ㅇ더 있습니다. 배열의 복사본을 하나 만들어주는데, 값을 pair(원본, 인덱스)로 지정한 후에 정렬하고 결과를 반환해주면, 실제 내부 동작은 안정정렬이 아니지만, 같은 값이 존재하지 않게되어 안정정렬과 같이 수행됩니다.

여러 기준으로 정렬하는 방법이 2가지 존재합니다. 첫번째로는 비교함수에서 여러 기준을 순차적으로 검사하는 방법, 그리고 두번째로는 우선순위가 낮은 기준부터 stable sort를 한번씩 수행하는 과정입니다. 그리고 알고리즘적인 결과외에도 유저 경험을 생각해보았을 때도 영향을 미칩니다. 만약 유저가 쇼핑몰에서 여러 기준으로 상품을 정렬해보았을때, 최대한 변화가 적으면서 각 기준으로 변경된다면 ux에 매우 좋을 것입니다.

radix sort가 대표적인 그 예시입니다. 기준이 log개 존재하는 다중 기준 정렬이죠. 가장 큰 장점을 생각하면 구현이 쉽습니다. 그리고 단점으로는 여러번 수행하기 때문에 키의 개수만큼 오버헤드가 존재합니다. 결국 같은 횟수의 비교가 아니냐 하면 맞지만, 하나의 연산을 하는 반복문을 5개 돌리는 것과, 반복문 하나 안에서 simple operation을 5번 수행하는 것의 최적화 차이는 매우 큽니다. 성능에 있어서 좋은 경우는 radix sort와 같은 경우입니다. radix sort에서는 각 기준마다 카운팅소트를 수행할 수 있는 조건을 만족하기 때문에 전체 시간복잡도에서 오히려 같은 수준이며, 캐시히트에서는 월등합니다. 또한 연속적으로 순회하기 때문에 simd 또는 버킷 기반의 최적화에도 열려있습니다.