정렬 알고리즘
데이터를 순서대로 — 비교·교환의 미학. 아래 8개 항목을 인터랙티브 시각화로 단계별로 학습해 보세요.
인접한 두 원소를 비교하여 정렬하는 방식입니다. 큰 값이 거품처럼 배열의 끝으로 떠오르는 모습에서 이름이 유래되었습니다. 구현이 단순하지만 큰 데이터에는 부적합합니다.
O(n²)각 요소를 이미 정렬된 부분과 비교하여 적절한 위치에 삽입하는 알고리즘입니다. 데이터가 거의 정렬되어 있을 때 매우 빠른 속도를 자랑합니다.
O(n²)배열에서 가장 작은(혹은 가장 큰) 요소를 반복적으로 찾아 맨 앞의 요소와 교체하는 방식으로 정렬을 수행하는 직관적인 제자리 정렬 알고리즘입니다.
O(n²)삽입 정렬을 일반화한 알고리즘으로, 간격(gap)을 점진적으로 줄이며 gapped insertion을 반복해 먼 거리의 원소를 효율적으로 이동시킵니다. 간격 수열에 따라 성능이 좌우됩니다.
O(n log² n)피벗(Pivot)을 기준으로 배열을 분할해가며 정렬하는 빠르고 효율적인 분할 정복 알고리즘입니다. 대부분의 언어에서 내장 정렬 함수의 기반이 되는 매우 중요한 알고리즘입니다.
O(n log n)배열을 더 이상 나눌 수 없을 때까지 나눈 후, 정렬하면서 다시 병합하는 안정적이고 일관된 성능을 가진 분할 정복 알고리즘입니다.
O(n log n)배열을 Max Heap 구조로 재구성한 뒤 루트(최댓값)를 반복적으로 추출하여 정렬하는 제자리(in-place) 알고리즘입니다. 최악의 경우에도 O(n log n)이 보장됩니다.
O(n log n)비교 없이 값의 빈도를 세어 정렬하는 non-comparison 알고리즘입니다. 값의 범위 k가 제한적일 때 O(n+k)의 선형 시간에 안정적(stable)으로 정렬할 수 있습니다.
O(n + k)