[알고리즘] 정렬 알고리즘 정리

정렬 알고리즘은 데이터를 특정 기준에 따라 오름차순 또는 내림차순으로 나열하는 알고리즘이다. 데이터 탐색 속도를 높이고, 중복 제거나 비교 연산을 쉽게 하기 위해 필수적으로 사용된다. 이번 글에서는 기본적인 정렬 알고리즘 7가지를 소개한다.

 

1. 삽입 정렬

삽입 정렬은 정렬되지 않은 데이터를 하나씩 꺼내어, 정렬된 영역에 적절한 위치에 삽입하는 방식이다. 

두 번째와 첫 번째를 비교 후 회전

세 번째와 첫 번째를 비교 후 회전, 세 번째와 두 번째를 비교 후 회전

네 번째와 첫 번째를 비교 후 회전, 네 번째와 두 번째를 비교 후 회전, 네 번째와 세 번째를 비교 후 회전 ...

평균과 최악 모두 수행 복잡도가 O(n²) 이지만 데이터가 거의 정렬되어 있을 땐 빠른 성능을 보인다. (최선 O(n))

 

2. 쉘 정렬

삽입 정렬을 보완한 알고리즘으로, 일정 간격으로 떨어진 데이터를 비교하며 정렬하고, 점점 간격을 줄여가며 삽입 정렬을 여러 번 수행하는 방식이다.

이 덕분에 삽입 정렬의 단점인 많은 이동 횟수를 줄일 수 있다.

 

3. 선택 정렬

전체 중에서 최솟값을 찾아 첫 번째 요소와 교환하고, 나머지 중에서 최솟값을 찾아 두 번째 요소와 위치를 교환한다. 계속 최솟값을 골라낸다. 모든 경우에 상관없이 비교 횟수가 일정하다. 평균과 최악 모두 수행 복잡도가 O(n²) 이다. 

 

4. 버블 정렬

인접한 두 요소를 비교해가며 자리를 바꾸는 방식으로, 가장 큰 값이 거품처럼 맨 끝으로 밀려나게 된다.

- 첫 번째와 두 번째를 비교, 두 번째와 세 번째를 비교, 세 번째와 네 번째를 비교 => 네 번째 요소 완성

- 첫 번째와 두 번째를 비교, 두 번째와 세 번째를 비교 => 세 번째 요소 완성 ...

단순하지만 비효율적이다.평균과 최악 모두 수행 복잡도가O(n²)이다. 

 

5. 퀵 정렬 Quick Sort

분할 정복(Divide and Conquer) 기법을 이용한 정렬 알고리즘이다. 전체 데이터 중 하나를 피벗(Pivot)으로 정하고, 이를 기준으로 작은 값과 큰 값으로 나눈다. 그 후 분할된 그룹을 다시 퀵 정렬로 정렬한다. 임의의 키를 분할 원소로 사용한다. 

- 분할(Divide): 분할 원소 즉 피봇을 중심으로 두 집합으로 나눈다. 

- 정복(Conquer): 왼쪽엔 작은 원소들의 부분 집합을, 오른쪽엔 큰 원소들의 부분 집합을 둔다.

- 부분 집합의 크기가 더 이상 나누어질 수 없을 때까지 반복수행한다.

- 평균 시간 복잡도는 O(nlogn), 최악 시간 복잡도는 O(n²)이다.

• n번: 피벗 기준으로 전체 배열을 한 바퀴 돌면서 분할함 (이게 O(n))
• log n번: 계속 절반씩 나누는 깊이 (이게 O(log n))

그래서 n * log n → O(n log n) 됨.

 

6. 힙 정렬

- 전 이진 트리(완전 이진 트리)인 힙 트리로 변환하여 정렬한다.

- 완전 이진 트리이되, 부모가 항상 자식보다 큰 값이거나 (최대힙) 자식이 항상 부모보다 큰 값이다. (최소 힙)

- 평균과 최악 모두 시간 복잡도는 O(nlogn)

- 배열을 완전 이진 트리로 구성 후, 노드의 역순으로 부모와 자식의 값을 비교하며 큰 값을 위로 올린다. (최대 힙)

 

7. 합병 정렬

- 이미 정렬된 두 개의 파일을 한 개의 파일로 합병한다.

- 2 way merge sort는 두 개씩 묶어서 비교하는 방법이다.

- 평균과 최악 모두 시간 복잡도는 O(nlogn)

 

 

정렬 알고리즘은 상황에 따라 성능이 크게 달라진다. 예를 들어, 데이터가 거의 정렬되어 있다면 삽입 정렬이 유리하고, 빠른 속도가 중요하다면 퀵 정렬이나 힙 정렬이 주로 사용된다. 반면, 안정성과 정렬 품질이 중요하다면 합병 정렬을 사용한다. 정렬 알고리즘을 제대로 이해하는 것은 효율적인 프로그래밍의 시작점이다.