[알고리즘] 정렬, Sorting

정의

정렬이란, 리스트에 포함된 원소들을 일정한 기준에 따라 정렬하는 문제이다.

특성

정렬은 스프레드시트, 데이터베이스 등 다양한 응용에서 매우 흔하게 사용되는 연산이다.

대표적인 정렬 알고리즘

분류	알고리즘	설명
기초 정렬	버블 정렬 (Bubble Sort)	인접한 요소를 비교하여 큰 값을 오른쪽으로 밀어내며 정렬
	선택 정렬 (Selection Sort)	가장 작은 값을 선택해 앞쪽에 배치
	삽입 정렬 (Insertion Sort)	정렬된 구간에 현재 값을 알맞은 위치에 삽입하여 정렬
고급 정렬	병합 정렬 (Merge Sort)	분할 → 정복 → 병합, 안정적이고 재귀적으로 동작
	퀵 정렬 (Quick Sort)	피벗을 기준으로 분할, 평균적으로 매우 빠름
	힙 정렬 (Heap Sort)	최대/최소 힙 자료구조를 활용하여 정렬
비교 기반 아님	계수 정렬 (Counting Sort)	정수 데이터의 개수를 세어 정렬 (범위가 한정된 경우)
	기수 정렬 (Radix Sort)	자릿수를 기준으로 여러 번 정렬 (정수형에 적합)
	버킷 정렬 (Bucket Sort)	값을 일정 범위(버킷)로 나눈 뒤 각 버킷을 정렬하여 합침

---

Definition

The problem of ordering the elements of a list.

Property

Sorting is a common operation in many applications (e.g., spreadsheets and databases).

Representative Sorting Algorithms

Category	Algorithm	Description
Basic Sorting	Bubble Sort	Compares adjacent elements and pushes larger ones to the right
	Selection Sort	Selects the smallest element and places it at the front
	Insertion Sort	Expands the sorted section by inserting the current element into the correct position
Advanced Sorting	Merge Sort	Divide → Conquer → Merge; stable and recursive
	Quick Sort	Uses pivot to partition; very fast on average
	Heap Sort	Uses max/min heap structure for sorting
Non-comparison Based	Counting Sort	Counts occurrences of integers (limited range)
	Radix Sort	Sorts by digit places (suitable for integers)
	Bucket Sort	Divides values into ranges (buckets) and sorts within them