예상을 벗어나지 않게 목록을 정렬하고 중복 제거하기

왜 "10"이 "2"보다 앞에 오는지, 움라우트가 독일과 스웨덴에서 어떻게 자리를 바꾸는지, 어떤 중복이 정말 중복으로 세어지는지, 그리고 무작위 비교 함수가 왜 편향된 섞기인지 설명합니다.

정렬과 중복 제거는 목록에 할 수 있는 가장 단순한 두 가지 작업처럼 보이며, 그래서 결과가 그토록 자주 조용히 틀립니다. 둘 다 비교에 기대고 있는데, 두 줄이 같다거나 어느 줄이 먼저 온다는 것이 무엇인지에 대한 단일한 답은 없습니다.

사전식 순서는 숫자 순서가 아닙니다

텍스트의 기본 비교는 두 문자열을 한 글자씩 훑으면서 코드 포인트를 비교하고, 처음 달라지는 지점에서 멈춥니다. 그 안에는 숫자가 무엇인지 아는 것이 하나도 없습니다.

input:   img1.png, img2.png, img10.png
sorted:  img1.png, img10.png, img2.png

img10.png가 두 번째에 오는 이유는 네 번째 글자에서 1(U+0031)이 2(U+0032)보다 작고, 비교가 거기에서 끝나기 때문입니다. 같은 규칙이 버전 1.10을 1.9보다 앞에 놓고, 스크린샷 폴더를 찍은 순서와 다르게 나열합니다.

방식	하는 일	주의할 점
숫자 정렬	각 줄을 숫자로 읽습니다	숫자가 아닌 줄을 어딘가에 두어야 하고, 천 단위 구분자가 파싱을 깨뜨립니다
자연 정렬	연속된 숫자는 숫자로, 나머지는 텍스트로 비교합니다	`01`과 `1`이 같다고 비교되므로 동점 처리 방식이 순서를 결정합니다

숫자 비교는 음수 문제도 해결합니다. 사전식으로는 -10이 -1과 -2 사이에 놓입니다. 마이너스 기호도 코드 포인트를 가진 하나의 문자일 뿐이기 때문입니다.

대문자가 소문자보다 앞에 오는 것 등 코드 포인트가 주는 놀라움

ASCII에서 대문자는 65에서 90, 소문자는 97에서 122를 차지하므로 모든 대문자가 모든 소문자보다 앞에 옵니다.

입력	코드 포인트 순서	대소문자 무시 순서
Zebra, apple, Apricot, banana	Apricot, Zebra, apple, banana	apple, Apricot, banana, Zebra

숫자는 모든 영문자보다 아래에, 공백(32)은 인쇄 가능한 모든 문자보다 아래에, 빈 줄은 그보다도 아래에 놓입니다. 그래서 오름차순 정렬은 빈 줄과 공백으로 시작하는 줄을 맨 위에 모으고, 내림차순 정렬은 맨 아래에 모읍니다.

끝에 붙은 공백은 같은 문제의 보이지 않는 판본입니다. apple 와 apple은 나란히 정렬되어 아무리 해도 제거되지 않는 중복처럼 보입니다. 줄바꿈 없는 공백(U+00A0)은 더 나쁩니다. 보통 공백과 똑같이 그려지지만 모든 영문자보다 위에 정렬되기 때문입니다. Windows 파일을 줄바꿈 문자만으로 나눴을 때 남는 캐리지 리턴도 마찬가지입니다. 두 줄이 똑같아 보이는데도 합쳐지지 않는다면 숨은 문자를 확인하십시오.

같은 목록이 두 나라에서 다르게 정렬됩니다

코드 포인트 순서는 악센트가 붙은 모든 문자를 악센트 없는 모든 문자 뒤에 놓기도 합니다. Zürich는 Zzz 뒤에, Ärger는 zebra 뒤에 정렬됩니다. 자기 알파벳을 그렇게 배열하는 언어는 없습니다. 로캘을 인식하는 콜레이션은 대신 언어 규칙으로 비교하며, 그 규칙들은 서로 어긋납니다.

로캘	규칙	결과
독일어, 사전 순서	`ä`는 `a`로, `ö`는 `o`로, `ü`는 `u`로 정렬	Apfel, Ärger, Azubi
독일어, 전화번호부 순서	`ä`는 `ae`로, `ü`는 `ue`로 정렬	`Müller`가 `Mueller`와 같은 자리에 놓임
스웨덴어	`å`, `ä`, `ö`가 `z` 뒤에서 알파벳을 마무리	Apfel, Zebra, Ärger
스페인어	`ñ`은 `n` 뒤에 오는 독립된 글자	`anzuelo`가 `año`보다 앞

JavaScript에서는 이 기능이 Intl.Collator에 있습니다.

const words = ["Zebra", "Ärger", "Apfel"];

words.sort(new Intl.Collator("de").compare);
// Apfel, Ärger, Zebra

words.sort(new Intl.Collator("sv").compare);
// Apfel, Zebra, Ärger

같은 객체가 앞서 나온 문제들도 다룹니다. { numeric: true }는 연속된 숫자를 수로 비교하며 이것이 자연 정렬입니다. 그리고 sensitivity는 무엇을 차이로 볼지를 정합니다. "base"는 대소문자와 악센트를 무시하고, "accent"는 대소문자만 무시하며, "case"는 악센트만 무시합니다. 로캘을 빼면 기기에 설정된 값이 쓰이는데, 같은 코드가 두 노트북에서 서로 다른 순서를 내놓는 이유가 이것입니다. 출력이 어디에서나 같아야 한다면 로캘을 명시하십시오.

어떤 중복이 중복으로 세어지는가

중복 제거는 그 뒤에 있는 동등성 판정만큼만 잘 정의됩니다. 모두 acute 악센트가 붙은 cafe라는 단어로 그려지는 다섯 줄을 봅시다.

#	줄	실제로 저장된 것
1	`café`	미리 결합된 `é` (U+00E9)
2	`café`	`e` 뒤에 결합용 acute (U+0301)
3	`Café`	대문자 C, 결합형
4	`café`	끝에 공백
5	`café`	1번 줄과 완전히 동일

합리적인 규칙 네 가지가 서로 다른 네 가지 답을 내놓습니다.

규칙	남는 줄	개수
정확히 일치	1, 2, 3, 4	4
양 끝 공백 제거 후 정확히 일치	1, 2, 3	3
공백 제거하고 대소문자 통일	1, 2	2
공백 제거, 대소문자 통일, NFC 정규화	1	1

어느 것도 틀리지 않았습니다. 서로 다른 질문에 답하고 있을 뿐입니다. 정규화는 보이는 것보다 더 중요합니다. macOS 파일 이름에서 온 텍스트는 분해형(NFD)으로 도착하는 경향이 있고 Windows와 웹 폼에서 온 텍스트는 결합형(NFC)으로 도착하므로, 두 출처에서 붙여 넣은 목록에는 보이지 않는 쌍둥이가 섞여 들어옵니다. NFKC는 한 걸음 더 나아가 ﬁ 합자 같은 호환 문자를 평범한 대응 문자로 접어버립니다.

관례상 첫 번째로 나온 것이 남으므로, 지저분한 사본을 먼저 붙여 넣었다면 그것이 살아남습니다. 그리고 중복을 제거하는 것과 고유한 항목을 찾는 것은 서로 다른 요청입니다. 중복 줄 제거는 각 항목을 하나씩 남기는 반면, 목록 빈도 도구가 말하는 고유 집합은 정확히 한 번만 나타나는 항목들이라는 더 작은 묶음입니다.

안정성, 그리고 두 개의 키로 정렬하기

안정 정렬은 비교 함수가 같다고 판정한 항목들이 입력에서 가지고 있던 순서를 그대로 유지한다고 보장합니다. 여러 번 정렬해서 다중 키 정렬을 구현할 수 있는 것도 그 덕분입니다. 덜 중요한 키로 먼저 정렬하고 가장 중요한 키로 나중에 정렬하면 됩니다. 이름으로 정렬한 다음 부서로 정렬하면 부서가 순서대로 나오고 각 부서 안에서는 이름이 순서대로 놓입니다. 불안정 정렬은 두 번째 정렬을 하면서 첫 번째 정렬을 흐트러뜨리고, 그 결과는 거의 맞아 보입니다. 명백히 틀려 보이는 것보다 더 나쁩니다.

뒤집기에도 같은 함정이 있습니다. 정렬된 목록을 뒤집으면 동점인 묶음들도 함께 뒤집히기 때문입니다. 목록 뒤집기는 전체 순서를 뒤바꾸는 것이 목적일 때 쓰고, 내림차순 정렬의 지름길로 쓰지 마십시오.

구현마다 다릅니다. JavaScript의 Array.prototype.sort는 ES2019에 와서야 안정성이 요구되었습니다. 그 전에는 V8이 배열 크기가 일정 수준을 넘으면 불안정한 퀵소트를 썼기 때문에, 같은 코드가 항목 10개일 때와 1만 개일 때 다르게 동작했습니다. Python의 sorted는 안정적이고, GNU sort는 -s를 주지 않는 한 안정적이지 않습니다.

섞기는 정렬의 한 종류가 아닙니다

한 줄짜리 섞기인 list.sort(() => Math.random() - 0.5)는 편향되어 있습니다. 정렬은 비교 함수가 일관된 순서를 기술한다고 가정하고, 알고리즘이 필요로 하는 일부 쌍에 대해서만 질문합니다. 호출할 때마다 새로운 수를 굴리는 비교 함수는 그 가정을 깨뜨리므로 결과가 알고리즘과 배열 길이에 따라 달라집니다. 항목들은 처음 있던 자리 근처에 머무는 경향이 있고, 어떤 순열은 다른 순열보다 훨씬 자주 나타납니다.

올바른 섞기는 피셔예이츠 방식을 씁니다. 끝에서부터 훑으면서 각 항목을 자기 자신을 포함해 그 앞쪽에서 균등하게 고른 항목과 교환합니다.

for (let i = list.length - 1; i > 0; i--) {
  const j = Math.floor(Math.random() * (i + 1));
  [list[i], list[j]] = [list[j], list[i]];
}

흔히 보이는 잘못된 변형은 반복문 안에서 Math.random() * list.length를 써서 매번 배열 전체에서 뽑습니다. 그러면 똑같이 가능성 있는 뽑기 순서가 n의 n제곱 가지가 되는데, 이 값은 n 팩토리얼 가지의 순서로 정확히 나누어떨어지지 않으므로 어떤 순서는 더 자주 나옵니다.

무작위성과 정렬은 올바르게 결합할 수 있습니다. 각 항목에 무작위 키를 미리 하나씩 부여하고 그 키로 정렬하면 됩니다. 그러면 비교 함수가 일관성을 유지하기 때문입니다. 문제가 되는 것은 비교 안에서 주사위를 굴리는 일입니다.

단계를 밟는 순서

목록에서 생기는 문제의 대부분은 올바른 작업을 잘못된 순서로 수행하는 데서 나옵니다.

먼저 껍질을 벗기십시오. 코드에서 복사한 목록은 "apple", 형태로 도착합니다. 따옴표와 쉼표가 문자열의 일부이므로 apple과는 결코 일치하지 않습니다. 목록 항목 풀기 도구가 그것을 걷어냅니다.
양 끝 공백을 제거하고 정규화하십시오. 그래야 동등성이 생각하는 그 의미가 됩니다.
중복을 제거하십시오. 일치 규칙은 기본값을 그냥 받아들이지 말고 의도적으로 고르십시오.
정렬하십시오. 줄 정렬 도구는 텍스트, 숫자, 길이, 무작위 순서를 지원합니다. 악센트가 있는 데이터에는 로캘을 지정하십시오.
모양 바꾸기는 마지막입니다. 목록 항목 묶기는 요청당 제한에 맞춰 결과를 고정 크기 묶음으로 나누고, 목록 회전은 내부 순서를 바꾸지 않은 채 전체를 밀어냅니다.

공백을 제거하기 전에 중복을 제거하면 거의 같은 항목들이 남고, 중복을 제거하기 전에 정렬하면 곧 버려질 줄들을 정렬하는 셈입니다.