정렬 알고리즘 비교
언제나 가장 빠른 정렬 알고리즘은 없습니다. 어떤 것은 단순하지만 느리고, 어떤 것은 무작위 데이터에서는 빠르지만 정렬된 데이터에서 헤매며, 어떤 것은 아예 비교 정렬이 아닙니다. 여덟 가지를 같은 목록으로 경주시키면 차이가 한눈에 보입니다.
세 가지 계열
버블 정렬, 선택 정렬, 삽입 정렬은 단순한 정렬입니다. 가까이 있는 값을 비교하고 교환하며, 무작위 목록에서는 n²에 비례하는 시간이 걸립니다. 병합 정렬, 퀵 정렬, 힙 정렬은 작업을 영리하게 나누어 n log n에 비례하는 시간이 걸리는데, 두 값 중 어느 쪽이 큰지만 물을 수 있는 정렬로서는 이것이 최선입니다. 기수 정렬과 계수 정렬은 그 질문을 아예 건너뜁니다. 자릿수나 값 자체를 쓰므로, 작은 정수 같은 키에만 쓸 수 있습니다.
작업량 재기
정렬 대결은 비교, 자릿수나 값 읽기, 교환이나 이동마다 연산 한 번을 셉니다. 무작위 값 40개에서는 계수 정렬이 약 120번, 기수 정렬 240번, 퀵 정렬 260번, 병합 정렬 380번, 힙 정렬 490번, 선택 정렬과 삽입 정렬이 각각 약 820번, 버블 정렬이 1,100번 넘게 걸립니다. 실제 컴퓨터에서는 메모리도 중요합니다. 목록을 훑는 방식 때문에 퀵 정렬은 실제로 횟수보다 대개 더 빠르고, 힙 정렬은 더 느립니다.
입력이 중요하다
거의 정렬된 목록에서는 값 40개에 삽입 정렬이 약 50번, 버블 정렬이 약 90번의 연산만 필요합니다. 각 값이 제자리 가까이에 있기 때문입니다. 역순 목록에서는 같은 두 정렬이 최악의 경우인 1,560번이 필요합니다. 선택 정렬, 힙 정렬, 병합 정렬, 기수 정렬, 계수 정렬은 순서에 거의 영향을 받지 않습니다. 세 값의 중앙값을 쓰는 퀵 정렬은 정렬된 목록과 역순 목록도 잘 처리하지만, 단순한 피벗을 쓰면 정렬된 목록이 최악의 경우가 됩니다. 값 종류가 적으면 퀵 정렬이 느려지는데, 같은 값이 모두 한쪽으로 몰리기 때문입니다.
메모리와 안정성
버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 힙 정렬은 제자리에서 동작하며 추가 메모리가 거의 필요 없습니다. 병합 정렬, 기수 정렬, 계수 정렬은 목록 길이만 한 버퍼가 필요합니다. 안정 정렬은 같은 값들의 원래 순서를 유지합니다. 버블 정렬, 삽입 정렬, 병합 정렬, 기수 정렬, 계수 정렬은 안정적이고, 선택 정렬, 퀵 정렬, 힙 정렬은 그렇지 않습니다. 레코드를 한 필드씩 차례로 정렬할 때 안정성이 중요합니다.
무엇을 써야 할까
실제로는 프로그래밍 언어에 내장된 정렬을 씁니다. 대개 짧은 조각에는 삽입 정렬을 쓰고 부분적으로 정렬된 데이터에서 빠른 병합 정렬인 Timsort이거나, 힙 정렬로 전환할 수 있고 작은 부분에는 삽입 정렬을 쓰는 퀵 정렬인 introsort입니다. 작은 정수 키가 많다면 계수 정렬이나 기수 정렬이 둘 다 이길 수 있습니다. 버블 정렬과 선택 정렬은 주로 교육용입니다.
직접 해 보기
정렬 대결을 열고 ‘재생’을 누르세요. 각 레인은 같은 목록에 대한 정렬 하나이며, 오른쪽 숫자가 연산 횟수를 세고, 끝나면 레인이 초록색으로 바뀝니다. 거의 정렬된 목록, 역순 목록, 값 종류가 적은 목록을 시도하고 끝나는 순서가 어떻게 바뀌는지 보세요. 각 정렬에는 단계별로 자세히 살펴볼 수 있는 전용 앱도 있습니다.
자주 묻는 질문
가장 빠른 정렬 알고리즘은 무엇인가요?
일반 데이터에서는 퀵 정렬과 병합 정렬(그리고 introsort나 Timsort처럼 이를 바탕으로 한 하이브리드)이 평균적으로 가장 빠르며, n log n입니다. 작은 정수 키라면 계수 정렬과 기수 정렬이 더 빠릅니다. 짧거나 거의 정렬된 목록에서는 삽입 정렬이 이깁니다.
비교 정렬은 왜 n log n보다 빠를 수 없나요?
값 n개의 목록은 n!가지 순서가 될 수 있고, 비교 한 번의 결과는 두 가지이므로, 최악의 경우 모든 순서를 구별하려면 적어도 log₂(n!)번의 비교가 필요합니다. 이는 약 n log₂ n입니다. 기수 정렬과 계수 정렬은 비교하지 않으므로 이 한계를 피합니다.
안정적인 정렬 알고리즘은 무엇인가요?
버블 정렬, 삽입 정렬, 병합 정렬, 기수 정렬, 계수 정렬은 일반적인 형태에서 안정적입니다. 선택 정렬, 퀵 정렬, 힙 정렬은 값을 멀리 옮기기 때문에 안정적이지 않습니다.
추가 메모리가 필요한 정렬은 무엇인가요?
병합 정렬, 기수 정렬, 계수 정렬은 목록 길이 정도의 버퍼가 필요합니다. 버블 정렬, 선택 정렬, 삽입 정렬, 힙 정렬은 거의 필요 없고, 퀵 정렬은 재귀를 위해 조금만 씁니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
정렬 대결 시작하기