[알고리즘] 정렬

June 12, 2025

버블 정렬

리스트의 데이터를 처음부터 끝까지 하나씩 선택하여(N번), 인접한 데이터와 크기를 비교하여 정렬 순서에 맞게 서로 위치를 바꾸는 작업을 더 이상 비교할 데이터가 없을 때까지 최대 N번 수행한다.
정렬 알고리즘 중 구현이 가장 간단하지만 가장 비효율적인 알고리즘이다.
버블 정렬은 안정 정렬이다.
시간 복잡도
- 최선의 경우: O(N) (이미 정렬된 경우)
- 일반적인 경우: O(N²)
- 최악의 경우: O(N²)

리스트를 부분적으로 정렬해 나가는 리스트와 부분적으로 정렬되지 않은 리스트로 나눈 후 정렬되지 않은 리스트의 데이터를 처음부터 끝까지 하나씩 선택하여(N번), 정렬된 리스트의 적절한 위치에 삽입하는 작업을 수행한다.
정렬된 리스트의 적절한 위치에 삽입하여 새로운 정렬된 리스트를 만드는 과정에서 정렬된 데이터와 크기를 비교하는 작업을 더 이상 비교할 데이터가 없을 때까지 최대 N번 수행한다. 정렬되지 않은 리스트의 데이터가 존재하지 않을 때까지 반복한다.
정렬 시작 시 부분적으로 정렬된 리스트는 첫 데이터이며, 두 번째 데이터를 첫 데이터와 비교하여 정렬한다.
삽입 정렬은 데이터의 수가 작은 경우 매우 빠르지만 데이터의 수가 많아질수록 느려진다.
시간 복잡도
- 최선의 경우: O(N) (이미 정렬된 경우)
- 일반적인 경우: O(N²)
- 최악의 경우: O(N²)

리스트에서 기준 데이터(피벗(pivot))를 하나 선택한 후 리스트를 기준 데이터 보다 작은 데이터로 이루어진 하위 리스트, 큰 데이터로 이루어진 하위 리스트로 분할한다. 리스트를 분할할 때 데이터를 정렬한다.
리스트를 재귀적으로 분할할 때 데이터를 이동하여 정렬하는 방법을 사용하며 분할된 하위 리스트들을 결합할 때 정렬을 하지는 않는다.
퀵 정렬은 분할 정복 알고리즘을 사용한 정렬 알고리즘이다.
퀵 정렬은 제자리 정렬이지만 불안정 정렬이다.
퀵 정렬은 기준 데이터를 어떻게 선택하는가에 따라 실행 속도 차이가 크다.
시간 복잡도
- 최선의 경우: O(n log n)
- 일반적인 경우: O(n log n)
- 최악의 경우: O(n²) (이미 정렬된 경우)

리스트를 더 이상 분할할 수 없을 때까지(리스트의 길이가 1개일 때까지) 계속 반으로 분할한 후 분할이 끝나면 분할된 하위 리스트들 중 인접한 두 하위 리스트들의 데이터를 정렬하면서 병합한다. 이 과정을 모든 하위 리스트에 대해 수행한다. 병합된 하위 리스트들 중 인접한 두 하위 리스트들의 데이터를 정렬하면서 병합한다. 이 과정을 모든 데이터가 정렬될 때까지 반복한다.
N개의 리스트를 크기 1인 리스트가 N개로 분할될 때까지 반으로 분할한 후, 크기 1인 두 인접한 하위 리스트를 정렬하고 병합한다. 그 다음 크기 2인 두 인접한 하위 리스트를 정렬하고 병합한다. 이 과정을 크기 N인 리스트가 정렬될 때까지 반복한다.
리스트를 재귀적으로 분할할 때 원소를 이동하여 정렬하지는 않으며 분할된 하위 리스트들을 결합할 때 정렬을 하는 방법을 사용한다.
병합 정렬은 퀵 정렬과 마찬가지로 분할 정복 알고리즘을 사용한 정렬 알고리즘이다.
병합 정렬은 데이터에 관계 없이 실행 속도가 일정하지만 대부분의 경우 퀵 정렬보다는 느리다.
병합 정렬은 안정 정렬이지만 제자리 정렬이 아니다.
시간 복잡도
- 최선의 경우: O(n log n)
- 일반적인 경우: O(n log n)
- 최악의 경우: O(n log n)