[알고리즘] 정렬 알고리즘 알아보기

소리·2025년 6월 11일

알고리즘 정렬

안녕하세요! 소리입니다 👋

정렬 알고리즘은 문제 해결의 기초가 되는 중요한 개념이에요.
정렬 알고리즘의 개념과 다양한 종류, 그리고 각 알고리즘의 특징까지 함께 알아볼게요.

🚀 정렬 알고리즘이란?

정렬 알고리즘이란 데이터를 특정 기준에 따라 나열하는 방법을 말해요.
많은 알고리즘에서 선행 작업으로 사용될 만큼 매우 중요하고 자주 쓰여요.

정렬 알고리즘에는 여러 구현 방법이 있습니다.
각 방법별 시간 복잡도나 공간 복잡도, 안정성 등의 특징이 다르기 때문에 이를 확인하고 적절한 방법을 선택해야 해요.

🤔 안정성이란?

정렬 과정에서 같은 값을 가지는 데이터의 순서가 유지되는 것을 안정(stable) 정렬이라고 해요.
요소가 여러 값을 가지고 있는 경우 정렬의 안정성이 중요할 수 있어요.

정렬 알고리즘 비교

종류	시간 복잡도	공간 복잡도	안정성	난이도
버블 정렬	$O(N^2)$	$O(1)$	안정	⭐
선택 정렬	$O(N^2)$	$O(1)$	불안정	⭐
삽입 정렬	$O(N^2)$	$O(1)$	안정	⭐
퀵 정렬	평균: $O(NlogN)$ 최악: $O(N^2)$	평균: $O(logN)$ 최악: $O(N)$	불안정	⭐⭐
합병 정렬	$O(NlogN)$	$O(N)$	안정	⭐⭐
힙 정렬	$O(NlogN)$	$O(1)$	불안정	⭐⭐⭐

📚 다양한 정렬 방법

버블 정렬 (Bubble Sort)

인접한 두 요소를 비교해 작은 수를 앞으로 보내는 작업을 반복하며 정렬하는 방법이에요.

시간 복잡도	공간 복잡도	안정성
$O(N^2)$	$O(1)$	안정

과정

배열의 맨 앞부터 교환 작업을 진행합니다.
1. 현재 요소가 다음 요소보다 크다면 교환합니다.
2. 다음 칸으로 이동해 똑같이 반복합니다.
마지막 요소를 제외한 후 남은 요소에 대해 똑같이 반복합니다.

장점

구현이 매우 간단하고 직관적입니다.
안정적인 정렬 방법입니다.
추가적인 메모리를 사용하지 않습니다.

단점

데이터가 많아질수록 성능이 급격히 저하됩니다.
교환 횟수가 많아 비효율적입니다.

선택 정렬 (Selection Sort)

정렬되지 않은 요소 중 가장 작은 것을 찾아 차례대로 붙이며 정렬하는 방법이에요.

시간 복잡도	공간 복잡도	안정성
$O(N^2)$	$O(1)$	불안정

과정

정렬되지 않은 요소 중 가장 작은 요소를 찾습니다.
찾은 요소를 정렬되지 않은 부분의 맨 앞과 교환합니다.
맨 앞을 제외한 나머지에 대해 이를 반복합니다.

장점

구현이 매우 간단하고 직관적입니다.
추가적인 메모리를 사용하지 않습니다.

단점

데이터가 많아질수록 성능이 급격히 저하됩니다.
불안정한 정렬 방법입니다.

삽입 정렬 (Insertion Sort)

정렬되지 않은 요소를 정렬된 배열 부분의 적합한 위치에 삽입하여 정렬하는 방법이에요.
거의 정렬된 데이터라면 $O(N)$ 에 가까운 시간 복잡도를 보여요.

시간 복잡도(최적)	시간 복잡도(평균·최악)	공간 복잡도	안정성
$O(N)$	$O(N^2)$	$O(1)$	안정

과정

정렬되지 않은 부분의 맨 앞 요소를 선택합니다.
정렬된 배열에 선택한 요소를 삽입합니다.
1. 정렬된 배열의 뒤부터 선택한 요소와 비교합니다.
2. 선택한 요소보다 더 크다면 뒤로 밉니다.
3. 이 과정이 완료되면 빈 자리에 선택한 요소를 넣습니다.
정렬이 완료될 때까지 계속 반복합니다.

장점

구현이 매우 간단하고 직관적입니다.
추가적인 메모리를 사용하지 않습니다.
작은 크기의 배열에서 효과적입니다.

단점

데이터가 많아질수록 성능이 급격히 저하됩니다.

퀵 정렬 (Quick Sort)

데이터에서 피벗을 고른 후 피벗보다 작은 배열과 큰 배열로 나눠 각각을 재귀적으로 정렬하고 합하는 정렬 방법이에요.
이름대로, 빠른 정렬 방법입니다. 다만 최악의 경우 $O(N^2)$ 의 시간 복잡도를 가질 수 있어요.

시간 복잡도(최적·평균)	시간 복잡도(최악)	공간 복잡도(최적·평균)	공간 복잡도(최악)	안정성
$O(NlogN)$	$O(N^2)$	$O(logN)$	$O(N)$	불안정

과정

배열 길이가 1 이하이면 중단합니다. (재귀의 탈출 조건)
피벗을 선정합니다.
피벗을 기준으로 작은 요소는 피벗의 왼쪽으로, 큰 요소는 오른쪽으로 분할합니다.
1. 배열의 왼쪽에서 피벗보다 큰 요소를 찾고, 오른쪽에서 작은 요소를 찾아 교환합니다.
2. (1)의 작업을 왼쪽 포인터와 오른쪽 포인터가 엇갈릴 때까지 반복합니다.
3. 엇갈린 위치에 피벗을 삽입합니다.
나뉜 배열을 재귀적으로 정렬합니다.

💡 자료 설명!

위 사진은 피벗을 배열의 맨 왼쪽 요소로 선정하는 예시예요.
맨 왼쪽을 선정하면, 포인터가 엇갈린 후 오른쪽에서 출발한 포인터가 찾은 작은 요소와 교환해서 배열을 분할할 수 있어요. 교환 후 피벗의 왼쪽에는 피벗보다 작은 값이, 오른쪽에는 큰 값이 있게 됩니다.

장점

배열을 매우 빠르게 정렬합니다. 다른 $O(NlogN)$ 시간의 방법보다 빠른 경우가 많습니다.
비교 과정에서 요소를 순차적으로 접근하는 경우가 많아, 캐시 메모리 활용률이 높습니다.

단점

지속적으로 편향된 값의 피벗이 선정된다면 $O(N^2)$ 의 시간이 걸립니다.
불안정한 정렬 방법입니다.

합병 정렬 (Merge Sort)

데이터를 반으로 나눠 각각을 정렬하고 합하는 방법이에요.
안정적인 정렬 방법 중 뛰어난 성능을 가져요.

시간 복잡도	공간 복잡도	안정성
$O(NlogN)$	$O(N)$	안정

과정

배열 길이가 1 이하이면 중단합니다. (재귀의 탈출 조건)
배열을 반으로 나누고 각각을 재귀적으로 정렬합니다.
나누었던 배열을 하나로 합칩니다.
1. 각 배열의 앞 부분 중 작은 값을 임시 배열로 옮깁니다.
2. 옮긴 요소를 제외한 후, (1)의 과정을 모든 요소를 옮길 때까지 반복합니다.
3. 임시 배열의 값을 다시 원래의 배열에 넣습니다.

장점

배열을 빠르고 효율적으로 정렬합니다.
안정적인 정렬 방법입니다.

단점

배열을 합치는 과정에서 추가적인 메모리가 필요합니다.

힙 정렬 (Heap Sort)

힙 구조를 이용한 정렬 방법이에요.
배열을 힙 구조로 바꾼 후 값을 추출하면서 정렬해요.

시간 복잡도	공간 복잡도	안정성
$O(NlogN)$	$O(1)$	불안정

과정

배열을 최대 힙 구조로 변경합니다.
1. 힙을 구성하지 않는 배열의 첫 번째 요소를 힙에 포함한 후 힙 구조에 맞게 정렬합니다.
2. 모든 요소가 힙에 포함될 때까지 반복합니다.
힙에서 데이터를 꺼내서 정렬합니다.
1. 힙의 루트를 힙의 마지막 요소와 바꾸고 힙에서 제외합니다.
2. 루트의 요소를 힙 구조에 맞게 재정렬합니다.

🤔 힙이란?

힙은 부모 노드가 자녀 노드보다 항상 우선순위가 높도록 하는 완전 이진 트리 구조예요.
요소의 값이 크면 우선 순위를 가지는 최대 힙의 경우, 트리의 루트는 트리 내에서 가장 큰 값을 가져요.

힙 구조는 배열의 메모리 공간을 그대로 활용해 만들 수 있으므로 힙 정렬은 추가적인 메모리 소모 없이 데이터를 정렬해요.

장점

배열을 빠르고 효율적으로 정렬합니다.
힙 구조를 데이터의 교환을 통해 만들어내므로 추가적인 메모리 소모가 없습니다.

단점

힙 구조의 생성과 관리로 인해 비효율적인 요소 접근이 많아 일반적으로 $O(NlogN)$ 속도의 방법 중 가장 느립니다.
불안정한 정렬 방법입니다.

🎯 상황별 유용한 정렬 방법

각 정렬 알고리즘은 장단점이 달라 상황에 따라 적절한 방법을 사용해야 합니다.
예를 들어 빠른 시간 내에 해결해야 한다면 $O(NlogN)$ 시간의 방법을 사용해야 해요.

위에서 설명한 방법들을 상황에 따라 표로 정리했어요.

상황	추천 정렬	이유
데이터가 거의 정렬되어 있음	삽입 정렬	$O(N)$ 에 가까운 빠른 속도
메모리 절약이 필요함	힙 정렬	정렬을 위해 추가적인 공간이 필요하지 않음
안정성이 중요함	합병 정렬	같은 값을 가진 요소의 순서가 보장됨
평균적으로 빠른 성능이 필요함	퀵 정렬	대부분의 경우 빠르게 정렬함

지금까지 다양한 정렬 알고리즘을 살펴봤습니다.
정렬은 방법이 다양해서 문제 해결에서 요구하는 상황에 따라 선택하는 것이 중요해요.
이 글이 앞으로 알고리즘을 배우는 여정에 도움이 되길 바랄게요! 😁

소리

소리의 우당탕탕 블로그

이전 포스트

블로그 시작!

다음 포스트