[정렬] 꼭 알아야 할 8가지 정렬 알고리즘 비교 정리

728x90

정렬(Sorting) 

정렬(Sorting)은 데이터를 일정한 순서(오름차순, 내림차순 등)로 재배치하는 알고리즘입니다. 정렬은 탐색, 최적화, 통계 처리 등 거의 모든 컴퓨터 과학 문제의 전처리 단계로 중요하게 사용됩니다. 정렬 알고리즘은 수행 방식, 안정성, 시간/공간 복잡도에 따라 다양하게 나뉘며, 내부 정렬(internal sorting)과 외부 정렬(external sorting)로도 분류할 수 있습니다. 대표적인 정렬 방식에는 버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬, 힙 정렬 등이 있으며, 각 언어는 기본 라이브러리 또는 메서드를 통해 내부적으로 고도화된 정렬 알고리즘을 제공합니다.

 

---

1.  정렬 알고리즘이란?

정렬의 목적

• 데이터를 빠르게 검색하거나 탐색을 쉽게 하기 위해
• 이진 탐색과 같은 알고리즘의 전처리
• 인간이 읽기 좋은 형식 제공
• 데이터 중복 또는 이상값 확인

정렬 알고리즘 분류

분류 기준	설명
비교 정렬	원소 간 비교를 통해 순서를 결정 (예: 버블, 퀵, 병합)
비비교 정렬	키 값을 이용하여 정렬 (예: 계수 정렬, 기수 정렬 등)
안정 정렬	같은 값일 경우 원래 순서를 유지
불안정 정렬	같은 값일 경우 원래 순서를 보장하지 않음
내부 정렬	모든 데이터를 메모리 내에서 정렬
외부 정렬	메모리에 다 못 올라가는 대용량 데이터를 외부 저장장치와 함께 처리

 

---

2.  각 언어별 기본 정렬 예시

a.  Python

arr = [5, 3, 8, 1, 2]
sorted_arr = sorted(arr)  # 새로운 리스트 반환
arr.sort()  # 제자리 정렬 (in-place)

• 내부적으로 Timsort 알고리즘 사용 (병합 + 삽입 정렬 기반)
• 안정 정렬

b.  C++

#include <algorithm>
#include <vector>

std::vector<int> arr = {5, 3, 8, 1, 2};
std::sort(arr.begin(), arr.end());

• std::sort() 는 IntroSort 사용 (퀵 + 힙 + 삽입 정렬 혼합)
• 불안정 정렬
• 안정 정렬이 필요한 경우 std::stable_sort() 사용

c.  Java

import java.util.Arrays;

int[] arr = {5, 3, 8, 1, 2};
Arrays.sort(arr);

• 기본 Arrays.sort() 는
  • 기본형(int 등): Dual Pivot QuickSort
  • 객체형: Timsort
• 객체형 정렬은 안정 정렬, 기본형은 불안정

d.  JavaScript

const arr = [5, 3, 8, 1, 2];
arr.sort((a, b) => a - b);

• sort() 는 기본적으로 문자열 정렬
• 숫자 정렬 시 비교 함수 필수
• 대부분의 엔진은 Timsort 또는 MergeSort 변형 사용

 

---

3.  추가적으로 고려할 요소

시간 복잡도 정리 (대표 알고리즘 기준)

알고리즘	평균 시간 복잡도	최악의 시간 복잡도	안정성	특징
버블 정렬	O(n²)	O(n²)	O	단순하지만 비효율적
선택 정렬	O(n²)	O(n²)	X	데이터 이동 횟수 적음
삽입 정렬	O(n²)	O(n²)	O	거의 정렬된 경우 빠름
계수 정렬	O(n + k)	O(n + k)	O	값의 범위가 작을 때 매우 빠름, 비교 안 함
기수 정렬	O(nk)	O(nk)	O	k = 자릿수, 비교 기반 아님
병합 정렬	O(n log n)	O(n log n)	O	안정적, 공간 복잡도 높음
퀵 정렬	O(n log n)	O(n²)	X	평균적으로 가장 빠름
힙 정렬	O(n log n)	O(n log n)	X	공간 효율 좋음

 

---

4.  마무리

• 정렬은 거의 모든 프로그래밍 문제에서 중요한 기본 도구입니다.
• 다양한 알고리즘이 있으며, 각각의 시간/공간 복잡도 및 안정성에 따라 선택해야 합니다.
• Python, C++, Java, JavaScript 등 주요 언어들은 각각 최적화된 내부 정렬 알고리즘을 제공합니다.
• 정렬은 단순한 기능 같지만 성능, 리소스, 목적에 따라 적절한 선택이 중요합니다.

함께 보면 좋은 자료

블로그 글 :

• [버블 정렬] 하나씩 비교하며 정렬하는 알고리즘
• [선택 정렬] 가장 작은 값을 골라 정렬하는 알고리즘
• [삽입 정렬] 카드를 정렬하듯, 데이터를 끼워 넣는 알고리즘
• [계수 정렬] 숫자를 세는 방식의 정렬 알고리즘
• [기수 정렬] 숫자의 자릿수를 활용한 빠른 비비교 정렬 알고리즘
• [병합 정렬] 나누고 정렬하고 다시 합치는 정렬 알고리즘
• [퀵 정렬] 피벗으로 나누고 빠르게 정복하는 정렬 알고리즘
• [힙 정렬] 힙 자료구조를 활용한 제자리 정렬 알고리즘

 

---