정렬 — 유미위키

정렬은 흩어져 있는 것들을 기준에 맞춰 나란히 놓는 일입니다. 그런데 무엇을 무엇에 맞추느냐에 따라 전혀 다른 작업을 가리킵니다. 데이터를 다룰 때는 값을 크기 순서대로 다시 늘어놓습니다 — 주문 목록을 주문 시각 순서로 내주는 일입니다. 메모리를 다룰 때는 값을 주소의 배수에 맞춰 놓습니다 — 4바이트 정수를 4의 배수 주소에 놓는 일입니다.

쉽고 빠른 이해

무슨 일을 하는 물건인가 — 한 낱말이 서로 다른 두 작업을 가리킵니다. 하나는 값을 크기 순서로 줄 세우는 일입니다. 데이터베이스가 주문 목록을 주문 시각 순서로 내주는 것이 그것입니다. 다른 하나는 값을 메모리 주소의 배수에 맞춰 놓는 일입니다. 영어로는 각각 sort 와 alignment 입니다. 번역이 둘을 한 낱말로 합쳤습니다.

왜 이렇게 하나 — 값을 줄 세워 두면 찾고 묶고 합치는 뒷일이 싸집니다. 주소를 배수에 맞춰 두면 프로세서가 값 하나를 한 번에 읽습니다. 배수가 안 맞으면 한 값을 읽는 데 메모리를 두 번 다녀와야 합니다.

어떻게 도나

값 정렬은 기준으로 삼을 값을 하나 정하고 그 기준으로 전체를 다시 늘어놓습니다
주소 정렬은 값을 놓을 때 시작 주소를 그 값 크기의 배수로 맞춥니다
배수가 안 맞으면 빈 바이트를 끼워 넣어 다음 값을 배수로 밀어 놓습니다

대가 — 값 정렬은 데이터가 늘수록 비용이 붙습니다. 메모리에 다 못 올리면 디스크를 오갑니다. 주소 정렬은 끼워 넣은 빈 바이트만큼 메모리를 더 씁니다. 두 뜻을 섞어 부르면 서로 다른 이야기를 하게 됩니다.

상세

「정렬」이 가리키는 두 작업을 나란히 놓고 봅니다.

정렬이 가리키는 작업들

맥락마다 무엇을 무엇에 맞추는지가 다릅니다. 공통점은 제멋대로 놓인 것을 기준에 맞춰 놓는다는 점입니다.

맥락	정렬이 맞추는 것	예
데이터 처리	값을 크기 순서로 다시 늘어놓습니다	배열 줄 세우기 · 질의 결과 줄 세우기
메모리와 저장	값의 시작 주소를 크기의 배수에 맞춥니다	구조체의 빈 바이트 · 페이지 경계 맞추기
화면과 문서	글과 요소를 한쪽 끝에 맞춥니다	왼쪽 맞춤 · 가운데 맞춤

앞의 둘은 영어로 각각 sort 와 alignment 입니다. 서로 이어지지 않는 두 낱말입니다. 한국어에서는 같은 말이 됐습니다. 백엔드 개발자가 자주 만나는 것도 이 둘입니다.

값을 크기 순서로 늘어놓는 정렬

값 여럿을 기준 하나로 줄 세우는 일입니다. 기준이 되는 값을 정렬 키라고 부릅니다. 주문 목록을 주문 시각으로 줄 세운다면 주문 시각이 정렬 키입니다.

작은 것을 앞에 놓으면 오름차순, 큰 것을 앞에 놓으면 내림차순입니다. 키가 같은 값이 여럿이면 둘째 키를 더 주어 그 안에서 다시 가릅니다.

정렬을 먼저 해 두는 까닭

정렬 자체가 목적인 경우는 드뭅니다. 순서를 미리 만들어 두면 뒤따르는 일이 싸지기 때문에 합니다. 무엇이 어떻게 싸지는지를 아래에 모았습니다.

뒤따르는 일	줄 세워 두면
중앙값 찾기	한가운데를 집으면 끝납니다
중복 지우기	같은 값끼리 이웃하므로 한 번 훑으며 지웁니다
값 하나 찾기	절반씩 접어 들어가며 좁힙니다
두 목록 합치기	양쪽 맨 앞만 견주며 한 번에 합칩니다

마지막 줄이 조인에서 쓰는 병합 방식입니다. 줄 서 있지 않으면 한쪽의 값마다 다른 쪽 전체를 뒤져야 합니다.

무엇이 앞인지 정하는 규칙

수는 크기로 견주면 되지만 글자는 그렇지 않습니다. 한글과 영문과 숫자가 섞인 이름을 어떤 차례로 놓을지는 언어권마다 다르게 정해 두었습니다. 이 규칙을 콜레이션이라고 부릅니다. 같은 데이터라도 콜레이션이 다르면 정렬 결과가 달라집니다.

키가 같은 값들의 원래 순서를 지키는 정렬을 안정 정렬이라고 합니다. 차이는 줄 세우기를 두 번 거칠 때 드러납니다. 이름으로 한 번 줄 세운 다음 부서로 다시 줄 세우는 경우입니다.

flowchart TD
    A["원본 · 순서가 제멋대로다"]
    A --> B["이름으로 줄 세운다 · 이름 순서가 생겼다"]
    B --> C["부서로 다시 줄 세운다 · 안정 정렬"]
    B --> D["부서로 다시 줄 세운다 · 안정이 아닌 정렬"]
    C --> E["부서 안에 이름 순서가 남는다"]
    D --> F["부서 안의 이름 순서가 흩어진다"]

부서별로 묶어 놓고도 그 안이 이름 순서이길 바란다면 두 번째 줄 세우기가 안정 정렬이어야 합니다.

정렬이 치르는 비용

값을 서로 견줘서 줄 세우는 방식은 항목이 n 개일 때 n log n 번 안팎의 비교가 필요합니다. 항목이 열 배가 되면 비교 횟수는 열 배보다 조금 더 늘어납니다.

값을 견주지 않고 줄 세우는 방식도 있습니다. 자릿수나 범위별로 통을 미리 만들어 놓고 값을 통에 나눠 담는 식입니다. 비교보다 적게 드는 대신 값이 어떤 모양인지를 미리 알아야 통을 만들 수 있습니다.

메모리도 씁니다. 원래 배열 안에서 값들을 맞바꿔 가며 끝내는 방식을 제자리 정렬이라고 합니다. 결과를 담을 배열을 따로 잡는 방식은 메모리를 한 벌 더 쓰는 대신 원래 순서를 안 망가뜨립니다.

메모리에 다 안 들어갈 때

정렬할 데이터가 메모리보다 크면 한 번에 올려놓을 수 없습니다. 이때는 메모리에 들어갈 만큼씩 잘라 조각마다 정렬해 디스크에 적어 둡니다. 그다음 조각들의 맨 앞 값만 보면서 작은 것부터 꺼내 하나로 합칩니다. 이 방식이 외부 정렬입니다.

flowchart TD
    입력["정렬할 데이터 · 메모리보다 크다"]
    입력 --> 조각1["조각 1 · 메모리에 올려 정렬"]
    입력 --> 조각2["조각 2 · 메모리에 올려 정렬"]
    입력 --> 조각3["조각 3 · 메모리에 올려 정렬"]
    조각1 --> 병합["세 조각의 맨 앞만 견주며 작은 것부터 꺼낸다"]
    조각2 --> 병합
    조각3 --> 병합
    병합 --> 결과["전체가 정렬된 결과"]

그림에서 조각을 정렬하는 단계까지는 조각마다 따로 돌 수 있습니다. 합치는 단계는 조각 수만큼의 맨 앞 값만 쥐고 있으면 되므로 메모리를 조금 씁니다.

질의에 ORDER BY 를 붙여 결과를 줄 세워 달라고 하면 이 정렬이 일어납니다. 다만 인덱스가 이미 그 순서로 값을 들고 있으면 정렬을 건너뛰고 인덱스를 훑기만 합니다. 실행 계획에 정렬 단계가 보이고 데이터가 많다면, 그 정렬이 메모리를 넘겨 디스크로 새는지 봐야 합니다.

주소를 배수에 맞추는 정렬

값을 메모리에 놓을 때 시작 주소를 그 값 크기의 배수로 맞추는 일입니다. 4바이트 정수라면 0번, 4번, 8번처럼 4의 배수 주소에서 시작하게 놓습니다. 이렇게 놓인 값을 정렬돼 있다고 말합니다. 이 규칙 전체를 메모리 정렬이라고도 부릅니다.

CPU(Central Processing Unit, 중앙 처리 장치), 곧 프로세서는 메모리를 한 바이트씩 읽지 않습니다. 일정한 크기의 덩이를 한 번에 읽고 씁니다. 그 덩이를 워드라고 부릅니다.

값이 워드 하나 안에 들어가면 한 번 읽어 끝납니다. 워드 경계에 걸치면 그렇지 않습니다. 아래 그림이 두 경우를 위아래로 놓은 것입니다. 워드는 4바이트로 놓고 봅니다.

block-beta
columns 8
  w1["워드 1 · 한 번에 읽는 4바이트"]:4 w2["워드 2 · 한 번에 읽는 4바이트"]:4
  a1["4바이트 값 · 0번에서 시작"]:4 a2["다음 값이 온다"]:4
  n1["맞은 경우 · 워드 1만 읽는다"]:8
  b1["0~2번 바이트"]:3 b2["4바이트 값 · 3번에서 시작"]:4 b3["7번 바이트 · 남는다"]:1
  n2["걸친 경우 · 워드 1과 워드 2를 둘 다 읽는다"]:8

걸친 값을 읽으려면 두 워드를 각각 읽어 필요한 바이트만 떼어 이어 붙여야 합니다. 한 번에 끝날 일이 두 번이 됩니다. CPU 에 따라서는 이런 접근을 거부하고 오류를 내기도 합니다.

컴파일러가 끼워 넣는 빈 바이트

값 여러 개를 한 묶음으로 만든 것을 구조체라고 합니다. 그 안의 값 하나하나는 필드라고 합니다. 구조체 안에 크기가 다른 필드를 차례로 늘어놓으면 배수가 저절로 맞지는 않습니다.

컴파일러는 필드 사이에 쓰지 않는 바이트를 끼워 넣어 다음 필드의 시작 주소를 배수로 만듭니다. 이 빈 바이트를 패딩이라고 부릅니다.

struct A {
    char a;   // 0번 바이트
    int  n;   // 4번 바이트
};            // 크기 8바이트

a 는 1바이트라서 0번 바이트 하나만 씁니다. 그런데 n 은 4의 배수에서 시작해야 합니다. 그래서 1번부터 3번까지가 빈 채로 남습니다. 여덟 바이트가 이렇게 나뉩니다.

block-beta
columns 8
  c0["0번"] c1["1번"] c2["2번"] c3["3번"] c4["4번"] c5["5번"] c6["6번"] c7["7번"]
  fa["a · 1바이트"]:1 fp["빈 바이트 3"]:3 fn["n · 4바이트"]:4
  fs["구조체 크기 8바이트"]:8

필드 크기를 더하면 5바이트입니다. 그런데 구조체는 8바이트가 됩니다. 그래서 큰 필드부터 놓으면 끼워 넣는 빈 바이트가 줄어듭니다. 같은 구조체를 수백만 개 들고 있는 프로그램에서는 이 차이가 메모리 사용량에 그대로 드러납니다.

같은 규칙이 걸리는 다른 계층

주소를 배수에 맞추는 규칙은 값 하나에만 걸리지 않습니다. 운영체제는 메모리를 페이지라는 같은 크기의 조각으로 잘라 다룹니다. 그래서 메모리를 크게 얻어 쓸 때는 페이지 크기의 배수 주소에서 시작합니다. 이것을 페이지 정렬이라고 부릅니다.

CPU 캐시 역시 캐시 라인이라는 덩이 단위로 움직입니다. 값 하나를 가져올 때도 그 값이 든 캐시 라인을 통째로 들고 옵니다.

서로 다른 스레드가 고치는 값 둘이 한 캐시 라인에 같이 들어가 있으면 한쪽이 값을 고칠 때마다 다른 쪽이 들고 있던 캐시 라인이 버려집니다. 두 스레드가 남의 값 때문에 메모리를 자꾸 다시 다녀오게 됩니다. 이것이 거짓 공유입니다.

디스크도 일정한 크기의 블록 단위로 읽고 씁니다. 파일 안의 덩이가 블록 경계에 맞아떨어지면 한 블록만 읽습니다. 걸치면 두 블록을 읽습니다.

메모리 쪽 단위들은 크기만 다를 뿐 서로를 담고 있습니다. 바깥 단위 하나 안에 안쪽 단위가 여럿 들어갑니다.

flowchart TD
    subgraph 페이지["페이지 · 운영체제가 메모리를 자르는 크기"]
        subgraph 캐시라인["캐시 라인 · CPU 캐시가 한 번에 옮기는 크기"]
            워드["워드 · CPU 가 한 번에 읽는 크기"]
        end
    end

어느 단위에서든 규칙은 같습니다. 경계 안에 담기면 한 번에 끝납니다. 걸치면 두 번 읽습니다.

화면에서 쓰는 정렬

화면과 문서에서 쓰는 정렬은 글과 요소를 한쪽 끝에 맞추는 일입니다. 왼쪽 맞춤, 가운데 맞춤, 양쪽 맞춤이 그것입니다. CSS(Cascading Style Sheets, 계단식 스타일 시트)의 text-align 이 이 뜻입니다.

앞의 두 뜻과는 이어지지 않습니다. 값의 순서도 아니고 주소의 배수도 아닙니다. 눈에 보이는 가장자리를 맞추는 것입니다.

어느 뜻인지 가르는 단서

문서나 대화에서 「정렬」이 나오면 함께 붙은 낱말을 봅니다. 대개 그것만으로 어느 뜻인지 갈립니다.

함께 나오는 말	뜻
오름차순 · 내림차순 · 정렬 키 · 인덱스 · 상위 몇 건	값의 순서
바이트 · 주소 · 배수 · 경계 · 구조체 · 패딩 · 페이지 · 캐시 라인	주소의 배수
왼쪽 · 가운데 · 여백 · 글상자	화면의 가장자리

「정렬」 뒤에 「~해서 보여 줘」가 붙으면 값의 순서입니다. 「~이 안 맞아서 느려진다」가 붙으면 주소의 배수입니다.

정렬

상세

정렬이 가리키는 작업들

값을 크기 순서로 늘어놓는 정렬

정렬을 먼저 해 두는 까닭

무엇이 앞인지 정하는 규칙

정렬이 치르는 비용

메모리에 다 안 들어갈 때

주소를 배수에 맞추는 정렬

컴파일러가 끼워 넣는 빈 바이트

같은 규칙이 걸리는 다른 계층

화면에서 쓰는 정렬

어느 뜻인지 가르는 단서

관련 항목

값을 순서대로 늘어놓는 정렬 알고리즘

정렬 결과를 좌우하는 기준과 성질

정렬된 순서를 밑천으로 삼는 연산

질의를 처리할 때 정렬이 일어나는 단계

주소를 배수에 맞추는 정렬이 재는 단위

정렬 경계를 맞추다 생기는 빈칸과 오류

메모리 정렬을 전제로 도는 명령과 기능

글과 요소를 한쪽 끝에 맞추는 정렬