Algorithm:[정렬 : 정렬별 장단점 및 시간복잡도]

정렬

데이터의 집합을 어떠한 기준(핵심항목, key)의 대소관계를 따져 일정한 순서로 줄지어 세우는 것

 

JavaScript에서는 그저 제공하는 sort()를 통해서 정렬을 하고있지만

그안에 숨어져있는 알고리즘들과 그 종류들 그리고 그것의 장단점을 알고자 합니다.

(보통 상황에 맞는 정렬방식으로 자동 사용된다고 합니다)

 

정렬별 장단점 및 시간복잡도를 비교

사실 이 정렬법이 무조건 제일 좋다는 정렬법은 없다고 합니다.

그이유는  정렬법들 모두 각각의 장단점이 있기 때문입니다.

---

# 버블정렬(Bubble Sort)

## O(N^2)  

장점

• 일단 구현이 쉬움  
• 코드 자체가 직관적

  단점

• 굉장히 비효율적
• 최악이든 최선이든 O(N^2)

---

# 선택정렬(Selection Sort)

## O(N^2) 

장점

• 선택정렬 또한 버블정렬과 마찬가지로 구현이 쉬운편
• 정렬을 위한 비교 횟수는 많지만 실제로 교환하는 횟수는 적기 때문에
  많은 교환이 일어나야 하는 자료상태에서 효율적으로사용될 수 있음
• 버블정렬보다는 좀더 빠름

  단점

• 비효율적
• 선택정렬도 버블정렬처럼 항상  O(N^2)
  (그러나 실제로 해보면 버블정렬보다 좀더 빠름)

---

# 퀵 정렬(Quick Sort)

## O(NlogN) ~ O(N^2)

장점

• 기준값에 의한 분할을 통해서 구현하는 정렬법
• 분할 과정에서 O(logN), 전체적으로 보게 되면 O(NlogN)
• 실행시간이 준수한 편

  단점

• 기준값(Pivot)에 따라서 시간복잡도가 크게 달라진다.
• 인자들이 적당히 이상적 O(NlogN), 최악 O(N^2)

---

# 힙 정렬(Heap Sort)

## O(NlogN)

  장점

• 추가적인 메모리를 필요로 하지 않으면서 항상 O(NlogN)

  단점

• 데이터의 상태에 따라서 다른 정렬법들에 비해서 조금 느린 편이다.
• 안정성(Stable)을 보장받지 못함

---

# 삽입정렬(Insertion Sort)

## O(N) ~ O(N^2)

  장점

   - 최선의 경우 O(N)

   - 성능이 좋다

  단점

• 최악의 경우 O(N^2)
• 데이터의 상태 및 데이터의 크기에 따라서성능의 편차가 굉장히 심함

---

# 병합정렬(Merge Sort)

## O(NlogN)

  장점

• 퀵정렬과 비슷하게 원본 배열을 반씩 분할해가면서 정렬하는 정렬법
  (퀵정렬과 달리 무조건 절반으로 분할)
  (분할 하는 과정에서 logN 만큼의 시간 걸림)
• 최종적으로 보게되면 항상 O(NlogN)

  단점

• 추가적인 메모리 필요

---

# 쉘 정렬(Shell Sort)

## O(N) ~ O(N^2)

  장점

• 삽입정렬의 단점을 보완해서 만든 정렬법 

  단점

• 일정한 간격에 따라서 배열을 바라봄
• 이 '간격'을 잘못 설정한다면 성능이 굉장히 안 좋아질수 있음 

---

# 기수정렬(Radix Sort)

##  O(N) 

  장점

   - 정렬법들 중에서 가장빠름 O(N) 

  단점

• '버킷' 이라는 추가적인 메모리 필요
• 데이터 타입이 일정한 경우에만 가능하다.
  (기수정렬의 경우 양의 정수는 양의 정수끼리만, 음의 정수는 음의 정수끼리만 정렬이 가능)
• 조건이 굉장히 많이 붙음 

---

# 카운팅정렬(Counting Sort)

##  O(N) 

  장점

• 가장 빠름 O(N)

  단점

• 많은 메모리 필요
• 숫자 갯수를 저장해야 될 별도의 공간, 또 결과를 저장할 별도의 공간 등 추가적인 메모리가 필요
• 숫자의 편차가 쿠면 메모리의 낭비
  (ex)[ 1, 2, 3, 4, 5, 99999999999 ] 99999999999 때문에 필요한 배열의 크기가 최소 [ 99999999999 ] 보다는 커야함

# 정리 

# 시간복잡도 순위

참고  

  O(1)이 가장빠르고, O(N!)이 가장 느립니다

 

 

++2022.06.30

TimSort도 있음

최근? 비교적 최근에 사용하는(2018년인듯) 안정적인 정렬

https://en.wikipedia.org/wiki/Timsort 

https://twitter.com/mathias/status/1036626116654637057?lang=en