정렬

정렬은 흩어진 것을 기준에 맞춰 가지런히 놓는 일입니다. 그런데 무엇을 무엇에 맞추는지가 분야마다 다릅니다. 데이터를 다루는 쪽의 정렬은 값을 순서대로 줄 세우는 sort 입니다. 메모리 쪽의 정렬은 주소를 배수에 맞추는 alignment, 화면 쪽의 정렬은 글을 가장자리에 맞추는 align 입니다.

상세

「정렬」이 세 맥락에서 각각 무엇을 무엇에 맞추는지를 여기서 가릅니다. 대상은 셋입니다. 데이터베이스에서 행을 꺼내는 질의 하나, 메모리에 놓이는 4바이트 정수 하나, 웹 페이지의 글 한 줄입니다. 맥락마다 맞추는 대상과 기준, 그리고 그렇게 맞추는 까닭을 짚습니다.

값을 순서대로 줄 세우는 정렬

데이터 쪽 정렬은 값 여럿을 기준 하나로 다시 늘어놓는 일입니다. 기준이 되는 값을 정렬 키라고 부릅니다. 주문 목록을 주문 시각 순서로 줄 세운다면 주문 시각이 정렬 키입니다.

데이터베이스에 이 정렬을 시키는 말이 SQL(Structured Query Language, 구조적 질의 언어)의 ORDER BY 입니다.

SELECT id, ordered_at FROM orders ORDER BY ordered_at DESC;

ASC 를 붙이면 작은 값이 앞에 오는 오름차순입니다. DESC 를 붙이면 큰 값이 앞에 오는 내림차순입니다. 아무것도 안 붙이면 오름차순입니다. 키를 둘 이상 적으면 앞 키가 같은 행끼리 뒤 키로 다시 가릅니다.

PostgreSQL 에서 ORDER BY 를 빼면 행은 약속되지 않은 차례로 나옵니다. 그 차례는 테이블을 읽고 잇는 방식과 디스크에 놓인 차례에 따라 달라집니다. 그러니 그 차례에 기대면 안 됩니다. 원하는 차례를 보장받으려면 정렬 단계를 명시해야 합니다.

줄 세운 결과는 뒤따르는 일도 싸게 만듭니다. 줄 서 있는 목록에서는 찾는 값을 가운데 값과 견줍니다. 그 결과로 찾을 범위를 절반씩 줄여 갑니다. 이 방법이 이진 탐색입니다.

정렬할 행이 많으면 메모리 안에서 다 못 끝낼 수 있습니다. PostgreSQL 의 실행 계획에서 정렬 단계는 Sort 노드로 나옵니다. 이 노드는 정렬이 메모리 안에서 끝났는지 디스크로 넘어갔는지와 쓴 양을 보여 줍니다.

Sort  (cost=713.05..713.30 rows=100 width=488) (actual time=2.995..3.002 rows=100.00 loops=1)
  Sort Key: t1.fivethous
  Sort Method: quicksort  Memory: 74kB

이 출력에서는 정렬이 메모리 74kB 안에서 퀵 정렬로 끝났습니다. 디스크를 빌려 쓰는 정렬은 외부 정렬이라고 부릅니다.

차례를 정하는 규칙

값이 수라면 크고 작음만 견주면 됩니다. 글자나 값이 없는 칸은 무엇이 앞인지를 따로 정해 두어야 합니다. 그 규칙이 달라지면 같은 데이터도 다른 차례로 나옵니다.

글자의 차례를 정하는 규칙을 콜레이션(collation)이라고 부릅니다. PostgreSQL 은 콜레이션을 열마다, 또는 연산마다 따로 정할 수 있게 합니다. ORDER BY 는 정렬 키에 붙은 콜레이션을 따릅니다.

값이 없는 행의 위치도 규칙이 정합니다. 값이 없음을 나타내는 표시는 NULL 입니다. PostgreSQL 은 NULL 을 어떤 값보다도 큰 것처럼 다룹니다. 오름차순에서는 맨 뒤, 내림차순에서는 맨 앞입니다. NULLS FIRST 나 NULLS LAST 를 붙이면 이 기본을 바꿉니다.

키가 같은 값들끼리의 차례도 결과를 가릅니다. 키가 같은 레코드의 원래 차례를 지키는 정렬을 안정 정렬이라고 합니다. Python 의 정렬은 언제나 안정 정렬입니다.

>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
>>> sorted(data, key=itemgetter(0))
[('blue', 1), ('blue', 2), ('red', 1), ('red', 2)]

색 이름만으로 줄 세웠습니다. 그래도 ('blue', 1) 은 ('blue', 2) 앞에 남습니다. 원래 목록에서 앞에 있었기 때문입니다.

이 성질 덕에 줄 세우기를 두 번에 나눠 할 수 있습니다. 둘째 키로 먼저 줄 세웁니다. 그다음 첫째 키로 다시 줄 세웁니다. 첫째 키가 같은 묶음 안에는 둘째 키 순서가 남습니다.

주소를 배수에 맞추는 정렬

메모리 쪽 정렬은 값을 놓는 시작 주소를 일정한 바이트 수의 배수로 맞추는 요구입니다. 그 바이트 수를 정렬 값이라고 부릅니다. 정렬 값이 4인 4바이트 정수는 0번·4번·8번처럼 4의 배수 주소에서 시작해야 합니다. 이렇게 놓인 값을 정렬돼 있다고 말합니다.

이 요구를 타입마다 두는 것은 C 언어 표준입니다. 어떤 타입의 정렬 값이 얼마인지는 컴파일러와 같은 구현이 정합니다. 다만 정렬 값은 1·2·4·8 처럼 언제나 2의 거듭제곱입니다. _Alignas 를 쓰면 더 엄격한 정렬을 따로 요구할 수 있습니다.

4의 배수인 주소를 4바이트 경계라고 부릅니다. 인텔의 x86 프로세서에서는 값이 꼭 정렬돼 있지 않아도 읽힙니다. 다만 4바이트 값이 4바이트 경계를 넘어 두 구간에 걸치면 메모리 접근이 두 번 듭니다. 정렬된 값은 한 번이면 됩니다.

그래서 성능을 위해 데이터 구조는 되도록 자연 경계에 맞춥니다. 자연 경계는 값 크기의 배수인 주소입니다. 2바이트 값은 짝수 주소, 4바이트 값은 4의 배수 주소, 8바이트 값은 8의 배수 주소입니다.

아래 그림은 같은 4바이트 값을 두 주소에 놓아 봅니다.

block-beta
columns 8
  h0["0번"] h1["1번"] h2["2번"] h3["3번"] h4["4번"] h5["5번"] h6["6번"] h7["7번"]
  g1["0~3번 · 첫 4바이트 구간"]:4 g2["4~7번 · 둘째 4바이트 구간"]:4
  ok["정렬된 값 · 0번에서 시작 · 한 번에 읽는다"]:4 space:4
  space:3 bad["어긋난 값 · 3번에서 시작 · 두 번 읽는다"]:4 space:1

0번에서 시작한 값은 첫 구간 안에 다 들어갑니다. 3번에서 시작한 값은 4번의 경계를 넘어 두 구간에 걸칩니다. 그래서 두 구간을 따로 읽어야 합니다.

어긋난 값을 아예 받지 않는 명령도 있습니다. 16바이트를 한 번에 다루는 명령 가운데 일부는 피연산자가 16의 배수 주소에 있어야 합니다. 어긋나 있으면 일반 보호 예외라는 오류를 냅니다.

구조체 안의 빈 바이트

값 여러 개를 한 묶음으로 만든 것을 구조체라고 합니다. 묶음 안의 값 하나하나는 필드라고 합니다. 필드는 선언한 차례대로 주소가 커지게 놓입니다. 각 필드는 자기 타입에 맞는 정렬을 지킵니다.

그 탓에 필드 사이에 이름 없는 빈 바이트가 들어갈 수 있습니다. 이 빈 바이트를 패딩이라고 부릅니다. 패딩은 구조체 맨 앞에는 없습니다. 맨 끝에는 있을 수 있습니다.

struct A {
    char a;   // 1바이트
    int  n;   // 4바이트
};

int 가 4바이트이고 정렬 값도 4인 환경이라면 여덟 바이트가 이렇게 나뉩니다. 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바이트가 됩니다. 패딩 3바이트만큼 메모리를 더 쓰는 셈입니다.

글을 가장자리에 맞추는 정렬

화면 쪽 정렬은 한 줄 안의 글을 줄의 한쪽 끝이나 가운데에 맞추는 일입니다. 가로쓰기 웹 페이지에서는 글 한 줄을 줄 상자라는 상자에 담습니다. 문단 하나는 줄 상자를 위아래로 쌓은 것입니다.

이 정렬을 맡는 것은 CSS(Cascading Style Sheets, 계단식 스타일 시트)의 text-align 속성입니다. CSS 의 표준은 W3C(World Wide Web Consortium, 월드 와이드 웹 컨소시엄)가 정합니다. 이 속성은 글이 줄 상자를 다 채우지 못했을 때 남은 폭에서 글을 어디에 둘지 정합니다.

아래 그림은 줄 상자 셋을 쌓아 남은 폭이 어느 쪽으로 가는지 보입니다.

block-beta
columns 4
  w["줄 상자 하나의 폭"]:4
  s1["start · 글"]:2 s2["남은 폭"]:2
  m1["남은 폭"]:1 m2["center · 글"]:2 m3["남은 폭"]:1
  e1["남은 폭"]:2 e2["end · 글"]:2

맞추는 기준은 줄 상자입니다. 화면 전체나 바깥 상자가 아닙니다.

이 뜻은 앞의 두 뜻과 겹치지 않습니다. 값의 차례를 바꾸지 않습니다. 주소를 건드리지도 않습니다. 눈에 보이는 가장자리를 맞춥니다.

맥락별 뜻

세 맥락의 뜻을 한 표에 모읍니다. 맥락마다 영어 낱말과 그 뜻을 정의한 문서를 붙였습니다.

세 뜻은 모두 맞는 뜻입니다. 어느 하나가 틀린 것이 아니라 맞추는 대상이 다릅니다. sort 는 값들 사이의 차례를 바꿉니다. alignment 는 값 하나가 놓이는 주소를 정합니다. text-align 은 글이 놓이는 가장자리를 정합니다.

영어 낱말은 셋이 아니라 둘입니다. 값을 줄 세우는 일만 sort 입니다. 뒤의 두 뜻은 모두 「맞추다」라는 뜻의 align 계열입니다. 그 요구를 가리키는 명사가 alignment, 웹에서 글을 맞추는 속성 이름이 text-align 입니다.

어느 맥락인지 가르는 단서

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

배경

한 낱말이 이 뜻들을 어떻게 다 받게 됐는지 짚습니다. 영어에서 sort 와 align 은 서로 다른 낱말입니다. 한국어 정보통신 용어 사전들이 그 둘을 모두 「정렬」로 옮겼습니다.

TTA(Telecommunications Technology Association, 한국정보통신기술협회) 정보통신용어사전에는 「정렬」 표제가 둘 있습니다. 하나는 sort 를, 다른 하나는 align 을 옮긴 것입니다. align 쪽 표제 안에는 뜻이 다시 둘입니다. 국립국어원 우리말샘의 정보·통신 뜻풀이도 여러 영어 낱말을 「정렬」 하나로 받습니다.

우리말샘에는 메모리 주소를 배수에 맞추는 뜻이 없습니다. 그 뜻은 TTA 사전의 align 표제에만 있습니다.

반대로 alignment 를 「맞춤」으로 옮긴 문서도 있습니다. Microsoft Learn 의 C++ 맞춤 문서 한국어판이 그렇습니다. 이 페이지는 기계 번역판입니다. alignment 는 「맞춤」으로, 같은 페이지의 aligned 는 「정렬된」으로 옮깁니다. 번역이 한 낱말로 다 굳은 것은 아닙니다.

왜 sort 와 align 을 둘 다 「정렬」로 옮겼는지는 확인하지 못했습니다(미확인).

「정렬」을 영어로 옮길 때는 맥락을 먼저 봐야 합니다. 한 낱말이 세 가지 일을 받고 있습니다. 낱말 하나로는 못 옮깁니다. 값을 줄 세우는 정렬은 sort 입니다.

나머지 두 뜻은 모두 align 계열의 낱말로 옮깁니다. 값을 놓는 주소를 배수에 맞추라는 요구는 명사 alignment 라고 부릅니다. 웹 페이지에서 글을 가장자리에 맞추는 속성 이름은 text-align 입니다.

경계

메모리 순서(memory ordering)도 정렬인가. 아닙니다.

이 말은 이름에 「메모리」와 「순서」가 다 들어 있습니다. 그래서 정렬의 두 뜻 어느 쪽으로도 읽힐 수 있습니다. 그러나 이 말이 가리키는 것은 프로세서가 메모리 읽기와 쓰기를 시스템 버스로 내보내는 차례입니다.

인텔 386 프로세서는 읽기와 쓰기를 명령에 적힌 차례대로 내보냈습니다. 이것을 강한 순서라고 부릅니다. 펜티엄 4 같은 뒤의 프로세서는 성능을 위해 이 차례에서 벗어나는 것을 허용합니다. 버퍼에 쌓인 쓰기보다 읽기가 먼저 나가는 식입니다.

메모리 순서는 값들을 키에 따라 다시 늘어놓지 않습니다. 값의 시작 주소를 배수에 맞추지도 않습니다. 메모리 연산이 시간 위에서 일어나는 차례를 다룹니다. 정렬의 어느 뜻에도 들지 않습니다.

관련 항목

sort 뜻의 정렬을 수행하는 알고리즘

정렬 알고리즘 · 퀵 정렬 · 병합 정렬 · 힙 정렬 · 삽입 정렬 · 선택 정렬 · 기수 정렬 · 팀 정렬 · 외부 정렬 · 제자리 정렬

sort 결과의 차례를 정하는 규칙과 성질

정렬 키 · 오름차순 · 내림차순 · 비교 함수 · 안정 정렬 · 콜레이션 · 로케일 · Unicode · 문자 인코딩

줄 세운 차례를 밑천으로 삼는 연산

이진 탐색 · 병합 조인 · 중앙값 · 분위수 · 중복 제거 · 상위 N 질의 · 선택 알고리즘

데이터베이스가 sort 를 수행하는 처리 단계

ORDER BY · SQL · 실행 계획 · EXPLAIN · 인덱스 · B-tree · 조인 · 질의 · SSTable · 컴팩션

alignment 가 배수를 재는 단위

바이트 · 옥텟 · 워드 · 자연 경계 · 캐시 라인 · 페이지 · 섹터 · 비트

alignment 를 맞추다 생기는 빈 바이트와 오류

패딩 · 구조체 · 정렬되지 않은 접근 · 일반 보호 예외 · 버스 오류 · 거짓 공유 · 세그멘테이션 폴트

alignment 를 전제로 도는 명령과 기능

C11 · 원자 연산 · SIMD · 메모리 매핑 · 다이렉트 IO · 포인터 · CPU 캐시

글을 가장자리에 맞추는 화면 배치 기술

텍스트 정렬 · CSS · 줄 상자 · 레이아웃 · 플렉스박스 · 그리드 레이아웃 · 타이포그래피

정렬과 이름이 헷갈리는 이웃 개념

메모리 순서 · 메모리 모델 · 메모리 배리어 · 엔디언