🎹 정렬 알고리즘 🎹

2026.02.05 (목)
정렬 알고리즘

---

정렬 알고리즘에 대해 자세하게 공부해보자!
어제 공부한 내용 다시 한번 공부하면서 더 잘 이해할 수 있도록 그래프를 그려보며 공부해봤다

---

🚥 정렬 알고리즘

정렬 알고리즘 무작위로 나열된 데이터 집합을 특정 기준(오른차순 또는 내림차순)에 따라 일정한 순서로 재배열하는 일련의 과정을 의미한다.

데이터의 형태에 따라 숫자 크기순, 문자 사전순 등으로 정렬할 수 있으며, 효율적인 정렬은 이후의 데이터 처리 속도를 결정짓는 핵심적인 선행 단계이다.

---

📄 정렬 알고리즘을 사용하는 핵심 이유

단순히 보기 좋게 나열하는 것을 넘어, 정렬은 시스템의 전반적인 성능 최적화를 위해 필수적이다.

📕 탐색 성능의 극대화

데이터가 정렬되어 있지 않으면 특정 값을 찾기 위해 처음부터 끝까지 확인하는 선형 탐색을 해야한다. 하지만 정렬된 데이터에서는 이진탐색을 사용할 수 있어 탐색 속도가 빨라진다.

• 미정렬 상태 : $O(n)$
• 정렬 상태 : $O(\log n)$

📗 데이터 처리 효율성 향상

• 중복 제거 : 정렬된 데이터에서는 인접한 요소끼리 비교하여 중복된 항목을 쉽게 찾아낼 수 있다.
• 그룹화: 특정 기준에 따라 데이터를 모아서 분석하거나 통계를 낼 때 정렬이 되어 있으면 처리가 간결해진다.

📘 다른 알고리즘의 기반 기술

많은 효율적인 알고리즘들이 데이터가 정렬되어 있음을 전제로 작동한다. 예를 들어, 두 데이터 집합의 교집합을 구한거나 최솟값/최댓값을 빠르게 추출해야 하는 로직에서 정렬은 필수적인 전처리 과정이다.

정렬 알고리즘을 선택할 때는 단순히 속도뿐만 아니라, 시간 복잡도($O(n \log n)$ vs $O(n^2)$)와 공간 복잡도, 그리고 동일한 값의 상대적 순서가 유지되는지 여부인 안정성(Stability)을 종합적으로 고려해야 한다!

---

📚 정렬의 기준에 따라 정리해보자

📕 안정성 기준

값이 같은 데이터가 있을 때, 정렬 전의 순서가 유지되는가?

• 안정 정렬: 병합 정렬, 삽입 정렬
  • 안정 정렬을 쓴다면 가격이 같은 상품들끼리 여전히 주문 일자순을 유지할 수 있다.
• 불안정 정렬 : 퀵정렬, 힙 정렬
  • 불안정 정렬을 쓴다면 가격이 같은 상품들의 주문 일자 순서가 뒤죽박죽 섞일 수 있다.

📗 제자리 정렬

데이터 정렬을 위해 추가적인 메모리 공간이 얼마나 필요한가?

• 제자리 정렬 : 퀵정렬, 힙 정렬, 선택 정렬
• 제자리 정렬이 아닌 것 : 병합 정렬

아주 작은 센서 장치에서는 추가적인 메모리를 사용하는 병합 정렬보다는 기존 배열 내에서 위치만 바꾸는 제자리 정렬 방식이 훨씬 유리하다.

📘시간 복잡도 기준

데이터 양이 많아질 때 얼마나 정체되는가?

• 단순한 정렬 $O(n^2)$ : 거품 정렬, 선택 정렬
• 효율적인 정렬 $O(n \log n)$ : 퀵 정렬, 병합 정렬

데이터가 적을 때 : 알고리즘이 복잡한 퀵 정렬보다 오히려 단순한 삽입 정렬이 더 빠를 수 있다. 실제로 많은 표준 라이브러리들이 데이터가 적을 땐 삽입 정렬을 섞어서 사용한다고 한다..!

데이터가 많다면? 반드시 $O(n \log n)$의 효율을 가진 정렬을 써야 시스템이 멈추지 않느다!

📙데이터의 성격 기준

데이터를 서로 비교하는가? 아니면 값의 특성을 이용하는가?

• 비교 정렬: 우리가 흔히 아는 대부분의 정렬 (퀵, 병합 등)
• 비비교 정렬 : 계수 정렬, 기수 정렬

수능 성적표를 처리할 때, 점수는 0점에서 100점 사이로 범위가 정해져 있다. 이럴 때는 숫자를 하나하나 비교하는 것보다 0점부터 100점까지의 칸을 미리 만들어두고 점수별로 개수를 세는 계수 정렬을 쓰면 $O(n)$이라는 압도적인 속도로 정렬이 끝난다.

---

$O(n)$ 상향 그래프

$O(n \log n)$ 상향 그래프

다음에는 시간 복잡도와 공간 복잡도에 따른 그래프를 그려봐야겠다..!