[알고리즘] 자주 사용하는 정렬

버블 정렬(Bubble Sort)

 

• 특징
  • 인접한 두 요소를 비교해 자리를 바꾸며 정렬하는 방식
  • Loop가 끝날 때마다 가장 마지막에는 가장 큰 값 또는 가장 작은 값이 위치
• 복잡도
  • 시간 복잡도 : O(n^2)
  • 공간 복잡도 : O(1)
• 장점
  • 구현이 간단
  • 자료의 이동이 적음
• 단점
  • 정렬 속도가 느리기 때문에 실무에서는 사용되지 않고 대부분 교육 목적이나 간단한 작업에만 사용
  • 삽입 정렬이나 선택 정렬과 같은 시간 복잡도를 갖지만, 평균적으로 버블 정렬의 교환 횟수가 더 많기 때문에 더 많은 시간 소비

---

선택 정렬(Selection Sort)

 

 

• 특징
  • 전체 리스트에서 가장 작은(혹은 큰) 요소를 선택해 정렬하는 방식
    • 1번째부터 n번째까지 가장 작은 값을 찾아 1번째 데이터와 swap
    • 2번째부터 n번째까지 가장 작은 값을 찾아 2번째 데이터와 swap
    • ...
• 복잡도
  • 시간 복잡도 : O(n^2)
  • 공간 복잡도 : O(1)
• 장점
  • 자료 이동 횟수가 버블 정렬보다 적어, 자료의 이동이 중요한 경우 적합
• 단점
  • 느린 속도 때문에 큰 데이터셋에는 적합하지 않음

---

삽입 정렬(Insertion Sort)

 

• 특징
  • 리스트의 앞에서부터 이미 정렬된 부분과 비교해 자신의 자리를 찾아 삽입
• 복잡도
  • 시간 복잡도 : O(n^2)
  • 공간 복잡도 : O(1)
• 장점
  • 거의 정렬된 데이터에서는 매우 효율적 → O(n)에 가까운 성능
• 단점
  • 데이터가 많을수록 성능이 떨어짐

---

합병 정렬(Merge Sort)

 

• 특징
  • 리스트를 절반씩 나누어 정렬 후 합치는 방식
  • 분할 정복 알고리즘을 기반으로 정렬
• 복잡도
  • 시간 복잡도 : O(n log ⁡n)
  • 공간 복잡도 : O(n)
• 장점
  • 안정적인 정렬
  • 데이터의 크기에 상관없이 일정한 성능
• 단점
  • 추가적인 메모리 공간 필요

---

퀵 정렬(Quick Sort)

 

• 특징
  • 피벗을 기준으로 피벗보다 작은 값과 큰 값으로 나누며 정렬
  • 피벗의 기준을 어느 위치에 두냐에 따라 왼쪽 피벗 선택 방식, 중간 피벗 선택 방식 , 오른쪽 피벗 선택 방식으로 나뉨
    (이미지는 오른쪽 피벗 선택 방식)
• 복잡도
  • 평균 시간 복잡도 : O(n log ⁡n)
  • 최악의 경우 시간 복잡도 : O(n^2)
    
  • 공간 복잡도 : O(log n)
• 장점
  • 시간 복잡도가 O(n log n)인 다른 알고리즘에 비해 대체적으로 속도가 매우 빠름
  • 추가 메모리가 거의 필요 없음
• 단점
  • 특정 조건 하에 성능이 급격히 떨어짐
    → 이미 정렬이 된 경우 (퀵 정렬의 최대 단점)
  • 재귀를 사용하기 때문에 재귀를 사용할 수 없는 환경의 경우 구현이 매우 복잡

---

힙 정렬(Heap Sort)

 

• 특징
  • 힙 자료구조를 사용해 정렬하는 방식
    → 힙 자료구조는 우선 순위 큐(Priority Queue) 자료 구조의 기반
• 복잡도
  • 시간 복잡도 : O(n log⁡ n)
  • 공간 복잡도 : O(1)
• 장점
  • 추가 메모리 공간이 필요 없음
  • 최악의 경우에도 O(n log ⁡n) 성능 보장
• 단점
  • 일반적인 O(n log n) 정렬 알고리즘에 비해 성능이 조금 떨어짐
  • 코드가 상대적으로 복잡해 구현이 어려움

---

계수 정렬(Counting Sort)

 

• 특징
  • 특정 범위 내의 정수 데이터에 대해 개수를 세는 방식으로 정렬
• 복잡도
  • 시간 복잡도 : O(n + k) (k는 데이터의 범위 크기)
  • 공간 복잡도는 O(k)
• 장점
  • 데이터의 범위가 좁을 때 매우 빠른 성능
• 단점
  • 메모리를 많이 차지
  • 범위가 큰 경우 비효율적
    • 범위 : 주어진 숫자의 범위가 1 ~ 1,000,000,000
    • 개수 : 3개 (1, 100, 5000만)
    • 위의 조건일 때 고작 3개를 정렬하기 위해 10억 1개의 메모리를 확보해야 함