왜 정렬을 배워야 할까
정렬은 데이터를 일정한 기준에 따라 순서대로 배치하는 일입니다. 숫자를 작은 값부터 큰 값으로 놓으면 오름차순 정렬이고, 큰 값부터 작은 값으로 놓으면 내림차순 정렬입니다. 이름을 가나다순으로 놓거나, 학생 점수를 높은 순서로 놓는 것도 정렬입니다.
처음에는 정렬이 단순히 보기 좋게 줄 세우는 작업처럼 느껴질 수 있습니다. 하지만 알고리즘에서 정렬은 훨씬 중요한 역할을 합니다. 정렬된 데이터에는 규칙이 생깁니다. 규칙이 생기면 찾기, 비교하기, 중복 제거하기, 가까운 값 찾기 같은 작업이 쉬워집니다.
예를 들어 다음 숫자들이 있다고 해 봅시다.
[7, 2, 5, 2, 9, 5]이 상태에서 중복된 값을 찾으려면 여러 값을 서로 비교해야 합니다. 하지만 정렬하면 다음과 같습니다.
[2, 2, 5, 5, 7, 9]이제 같은 값은 옆에 붙어 있습니다. 중복 여부를 확인하려면 바로 앞의 값과만 비교해도 됩니다. 정렬은 문제를 직접 해결하는 답이 아닐 때도 많지만, 문제를 쉽게 풀 수 있는 상태로 만드는 강력한 준비 작업입니다.
AI 생성 이미지
정렬을 이해하는 기본 생각
정렬 알고리즘은 대부분 두 가지 행동으로 설명할 수 있습니다.
비교: 두 값 중 어떤 값이 앞에 와야 하는지 판단한다.
교환 또는 이동: 값의 위치를 바꾼다.
예를 들어 [4, 1, 3]을 오름차순으로 정렬한다고 해 봅시다. 4와 1을 비교하면 1이 앞에 와야 합니다. 그래서 두 값을 바꿉니다.
[4, 1, 3]
[1, 4, 3]이제 4와 3을 비교하면 3이 앞에 와야 하므로 다시 바꿉니다.
[1, 4, 3]
[1, 3, 4]이처럼 정렬은 복잡한 마법이 아니라, 값을 비교하고 위치를 조정하는 과정을 반복하는 일입니다.
버블 정렬: 큰 값을 뒤로 밀어내기
버블 정렬은 이웃한 두 값을 계속 비교하면서 순서가 잘못되어 있으면 바꾸는 방법입니다. 물속의 거품이 위로 올라가듯, 오름차순에서는 큰 값이 한 단계씩 뒤로 밀려납니다.
예를 들어 [4, 2, 5, 1]을 오름차순으로 정렬해 봅시다.
첫 번째 반복에서는 앞에서부터 이웃한 값을 비교합니다.
[4, 2, 5, 1]
4와 2 비교 → 바꿈: [2, 4, 5, 1]
4와 5 비교 → 그대로: [2, 4, 5, 1]
5와 1 비교 → 바꿈: [2, 4, 1, 5]가장 큰 값 5가 맨 뒤로 갔습니다. 이제 마지막 값은 정렬이 끝났다고 볼 수 있습니다. 같은 과정을 남은 구간에 반복합니다.
의사코드는 다음과 같습니다.
bubble_sort(arr):
n = length(arr)
for end from n - 1 down to 1:
for i from 0 to end - 1:
if arr[i] > arr[i + 1]:
swap arr[i], arr[i + 1]버블 정렬은 이해하기 쉽지만 효율은 좋지 않습니다. 이웃한 값만 바꾸기 때문에 많은 비교와 교환이 필요합니다. 시간 복잡도는 보통 O(n²)입니다.
선택 정렬: 가장 작은 값을 골라 앞에 두기
선택 정렬은 이름 그대로, 아직 정렬되지 않은 값들 중 가장 작은 값을 선택해서 앞쪽에 놓는 방법입니다.
[4, 2, 5, 1]을 정렬해 보겠습니다.
전체에서 가장 작은 값 1 선택 → 첫 번째 위치와 교환
[1, 2, 5, 4]
남은 [2, 5, 4]에서 가장 작은 값 2 선택 → 이미 제자리
[1, 2, 5, 4]
남은 [5, 4]에서 가장 작은 값 4 선택 → 5와 교환
[1, 2, 4, 5]선택 정렬은 매번 "이번 위치에 들어갈 값을 찾는다"라고 생각하면 쉽습니다.
selection_sort(arr):
n = length(arr)
for pos from 0 to n - 1:
min_index = pos
for i from pos + 1 to n - 1:
if arr[i] < arr[min_index]:
min_index = i
swap arr[pos], arr[min_index]선택 정렬도 시간 복잡도는 O(n²)입니다. 다만 버블 정렬과 달리 교환 횟수는 비교적 적습니다. 각 위치마다 많아야 한 번 정도만 교환하기 때문입니다.
삽입 정렬: 알맞은 위치에 끼워 넣기
삽입 정렬은 카드를 손에 들고 정리하는 모습과 비슷합니다. 왼쪽에는 이미 정렬된 카드들이 있고, 새 카드를 하나 뽑아 알맞은 위치에 끼워 넣습니다.
[4, 2, 5, 1]에서 시작해 봅시다.
처음에는 4 하나만 정렬되어 있다고 생각합니다.
[4 | 2, 5, 1]이제 2를 왼쪽의 정렬된 구간에 넣습니다. 4보다 작으므로 앞으로 이동합니다.
[2, 4 | 5, 1]다음 값 5는 4보다 크므로 그대로 둡니다.
[2, 4, 5 | 1]마지막 값 1은 5, 4, 2보다 작으므로 맨 앞으로 들어갑니다.
[1, 2, 4, 5]의사코드는 다음과 같습니다.
insertion_sort(arr):
n = length(arr)
for i from 1 to n - 1:
value = arr[i]
j = i - 1
while j >= 0 and arr[j] > value:
arr[j + 1] = arr[j]
j = j - 1
arr[j + 1] = value삽입 정렬도 최악의 경우 O(n²)입니다. 하지만 거의 정렬된 데이터에서는 매우 빠르게 동작할 수 있습니다. 이미 앞뒤 순서가 대부분 맞으면 이동해야 할 값이 적기 때문입니다.
병합 정렬: 나누고, 정렬하고, 합치기
지금까지 본 세 정렬은 작은 입력을 손으로 이해하기 좋습니다. 하지만 입력이 커지면 O(n²)은 부담이 됩니다. 더 빠른 정렬을 이해하려면 분할 정복을 알아야 합니다.
분할 정복은 큰 문제를 작은 문제로 나누고, 작은 문제의 답을 합쳐 전체 문제를 해결하는 방식입니다. 병합 정렬은 이 아이디어를 정렬에 적용합니다.
핵심 흐름은 세 단계입니다.
배열을 반으로 나눈다.
나뉜 배열을 각각 정렬한다.
정렬된 두 배열을 하나로 합친다.
예를 들어 [4, 2, 5, 1]은 다음처럼 나눌 수 있습니다.
[4, 2, 5, 1]
→ [4, 2]와 [5, 1]
→ [4], [2], [5], [1]원소가 하나인 배열은 이미 정렬된 상태입니다. 이제 다시 합칩니다.
[4]와 [2]를 합침 → [2, 4]
[5]와 [1]을 합침 → [1, 5]
[2, 4]와 [1, 5]를 합침 → [1, 2, 4, 5]두 정렬된 배열을 합칠 때는 맨 앞 값끼리 비교합니다. 더 작은 값을 결과 배열에 넣고, 해당 배열의 다음 값으로 이동합니다.
merge_sort(arr):
if length(arr) <= 1:
return arr
mid = length(arr) / 2
left = merge_sort(arr[0:mid])
right = merge_sort(arr[mid:end])
return merge(left, right)
merge(left, right):
result = empty list
i = 0
j = 0
while i < length(left) and j < length(right):
if left[i] <= right[j]:
append left[i] to result
i = i + 1
else:
append right[j] to result
j = j + 1
append remaining values of left to result
append remaining values of right to result
return result병합 정렬의 시간 복잡도는 O(n log n)입니다. 배열을 계속 반으로 나누기 때문에 단계 수는 log n에 가깝고, 각 단계에서 전체 원소를 한 번씩 합치기 때문입니다. 대신 합치는 과정에서 추가 배열이 필요하므로 공간을 더 사용합니다.
퀵 정렬: 기준값을 중심으로 나누기
퀵 정렬도 분할 정복을 사용합니다. 다만 병합 정렬처럼 무조건 반으로 나누지는 않습니다. 기준값을 하나 정하고, 그보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 나눕니다. 이 기준값을 피벗이라고 부릅니다.
예를 들어 [4, 2, 5, 1, 3]에서 피벗을 3으로 정해 봅시다.
피벗: 3
작은 값: [2, 1]
큰 값: [4, 5]작은 값과 큰 값도 같은 방식으로 정렬한 뒤 합치면 됩니다.
[1, 2] + [3] + [4, 5]
→ [1, 2, 3, 4, 5]의사코드는 간단히 표현하면 다음과 같습니다.
quick_sort(arr):
if length(arr) <= 1:
return arr
pivot = choose one value from arr
less = values smaller than pivot
equal = values equal to pivot
greater = values greater than pivot
return quick_sort(less) + equal + quick_sort(greater)퀵 정렬은 평균적으로 O(n log n)입니다. 하지만 피벗이 계속 한쪽으로 치우치면 최악의 경우 O(n²)이 될 수 있습니다. 그래서 실제 정렬 함수들은 피벗 선택, 작은 구간 처리, 메모리 사용 등을 잘 조정해 안정적으로 동작하도록 만들어져 있습니다.
정렬 후 쉬워지는 문제들
정렬을 배우는 진짜 이유는 정렬 자체보다 정렬 후 문제 해결이 쉬워지는 경험에 있습니다.
중복 제거
정렬 전에는 같은 값이 떨어져 있을 수 있습니다.
[5, 1, 3, 5, 2, 3]정렬하면 같은 값이 붙습니다.
[1, 2, 3, 3, 5, 5]이제 앞의 값과 다를 때만 결과에 넣으면 중복을 제거할 수 있습니다.
unique_values(sorted_arr):
result = empty list
for value in sorted_arr:
if result is empty or last value of result != value:
append value to result
return result순위 계산
점수를 높은 순서로 정렬하면 순위를 매기기 쉬워집니다.
점수: [80, 100, 90]
내림차순 정렬: [100, 90, 80]이제 앞에 있는 값일수록 높은 순위입니다. 만약 같은 점수는 같은 순위로 처리해야 한다면, 이전 점수와 같은지 확인하면 됩니다.
rank_scores(scores):
sort scores in descending order
rank = 0
previous = none
for i from 0 to length(scores) - 1:
if scores[i] != previous:
rank = i + 1
previous = scores[i]
print scores[i], rank가까운 값 찾기
정렬 전에는 어떤 두 값이 가장 가까운지 찾기 어렵습니다. 모든 쌍을 비교하면 O(n²)이 걸립니다. 하지만 숫자를 오름차순으로 정렬하면 가장 가까운 두 값은 반드시 서로 이웃한 위치에 있습니다.
[10, 2, 14, 4]
정렬 후: [2, 4, 10, 14]이제 이웃한 값의 차이만 보면 됩니다.
minimum_difference(arr):
sort arr in ascending order
answer = infinity
for i from 0 to length(arr) - 2:
diff = arr[i + 1] - arr[i]
answer = min(answer, diff)
return answer정렬에 O(n log n)이 걸리고, 이후 이웃 비교는 O(n)입니다. 전체는 O(n log n)입니다. 모든 쌍을 비교하는 O(n²)보다 훨씬 나아질 수 있습니다.
기본 정렬 함수 사용하기
실전에서는 정렬 알고리즘을 직접 구현하기보다 언어가 제공하는 기본 정렬 함수를 많이 사용합니다. 중요한 것은 "어떤 기준으로 정렬할 것인가"입니다.
숫자 배열을 오름차순으로 정렬하는 경우는 단순합니다.
sort(arr)내림차순이 필요하면 방향을 반대로 지정합니다.
sort(arr, reverse = true)문제에서는 숫자 하나가 아니라 여러 정보를 함께 정렬해야 할 때도 많습니다.
students = [
{name: "민수", score: 80},
{name: "지아", score: 95},
{name: "현우", score: 90}
]점수 기준 오름차순이면 기준값을 score로 잡습니다.
sort(students, key = student.score)점수 높은 순서가 필요하면 내림차순을 함께 지정합니다.
sort(students, key = student.score, reverse = true)기준이 두 개 이상일 수도 있습니다. 예를 들어 점수는 높은 순서, 점수가 같으면 이름은 가나다순으로 정렬해야 한다고 해 봅시다.
sort(students, key = (-student.score, student.name))여기서 -student.score는 점수를 큰 값부터 오게 만들기 위한 표현입니다. 이름은 그대로 두었으므로 작은 값, 즉 가나다순으로 정렬됩니다.
또 하나 확인할 점은 같은 기준값을 가진 원소들의 순서입니다. 예를 들어 점수가 같은 학생들이 있을 때, 정렬 후에도 입력된 순서가 그대로 유지되어야 하는 문제가 있습니다. 이렇게 같은 값끼리의 기존 순서를 유지하는 정렬을 안정 정렬이라고 합니다. 언어의 기본 정렬 함수가 안정 정렬인지 아닌지는 언어마다 다를 수 있으므로, 원본 순서가 의미 있는 문제에서는 문서나 문제 조건을 꼭 확인해야 합니다.
자주 틀리는 부분
정렬 문제에서 가장 흔한 실수는 오름차순과 내림차순을 반대로 적용하는 것입니다. 문제를 읽을 때 "작은 순서인지, 큰 순서인지"를 먼저 표시해 두는 습관이 좋습니다.
두 번째는 정렬 기준을 잘못 잡는 것입니다. 학생을 이름순으로 정렬해야 하는지, 점수순으로 정렬해야 하는지, 점수가 같을 때 어떤 기준을 적용해야 하는지 확인해야 합니다. 특히 "같으면"이라는 조건은 보조 정렬 기준을 뜻하는 경우가 많습니다.
세 번째는 원본 순서가 필요한데 정렬로 바꿔 버리는 실수입니다. 정렬은 배열의 순서를 바꿉니다. 이후에 원래 위치가 필요하다면 값과 함께 원래 인덱스를 저장해야 합니다.
with_index = empty list
for i from 0 to length(arr) - 1:
append (arr[i], i) to with_index이렇게 원래 인덱스를 함께 저장해 두면, 정렬한 뒤에도 "이 값이 처음에는 어디에 있었는가"를 다시 확인할 수 있습니다.
네 번째는 정렬 비용을 무시하는 것입니다. 정렬은 보통 O(n log n)입니다. 한 번 정렬한 뒤 많은 작업을 쉽게 만들 수 있다면 좋은 선택입니다. 하지만 아주 작은 조건만 확인하면 되는 문제에 무조건 정렬을 쓰면 불필요한 비용이 될 수 있습니다.
정리
정렬은 데이터를 기준에 맞게 순서대로 배치하는 작업입니다. 버블 정렬, 선택 정렬, 삽입 정렬은 비교와 교환의 기본 흐름을 이해하기 좋습니다. 병합 정렬과 퀵 정렬은 큰 문제를 작은 문제로 나누는 분할 정복 사고를 보여 줍니다.
정렬의 가치는 정렬 후에 더 분명해집니다. 같은 값은 붙고, 순위는 앞에서부터 정해지며, 가까운 값은 이웃한 위치에서 찾을 수 있습니다. 그래서 정렬은 단순한 줄 세우기가 아니라 탐색과 최적화를 쉽게 만드는 준비 작업입니다.
문제를 풀 때는 먼저 이렇게 질문해 보세요.
데이터를 순서대로 놓으면 규칙이 생기는가?
같은 값이나 가까운 값을 쉽게 찾을 수 있는가?
정렬 비용
O(n log n)을 감당할 수 있는가?정렬 후 원래 순서가 필요하지는 않은가?
이 질문에 답할 수 있다면, 정렬은 많은 문제에서 강력한 첫 번째 선택지가 됩니다.
이 노트는 보도·비평·교육·연구 목적으로 작성되었습니다. 저작권 문의가 있으시면 에서 알려주세요.