정렬 알고리즘의 장단점과 시간 복잡도 및 공간 복잡도

정렬 알고리즘 복잡도

---

Sorting Algorithm	공간 복잡도		시간 복잡도
	최선	최악	최선	평균	최악
Bubble Sort	$O(1)$	$O(n)$	$O(n^2)$	$O(n^2)$	$O(n^2)$
Heap Sort	$O(1)$	$O(n\times log\ n)$	$O(N\times log\ n)$	$O(n\times log\ n)$	$O(n\times log\ n)$
Insertion Sort	$O(1)$	$O(n)$	$O(n)$	$O(n^2)$	$O(n^2)$
Merge Sort	$O(1)$	$O(n\times log\ n)$	$O(n\times log\ n)$	$O(n\times log\ n)$	$O(n\times log\ n)$
Quick Sort	$O(log \ n)$	$O(n\times log\ n)$	$O(n\times log\ n)$	$O(n\times log\ n)$	$O(n^2)$
Selection Sort	$O(1)$	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(n^2)$
Shell Sort	$O(1)$	$O(n)$

 

정렬 알고리즘 특징 및 장단점

---

• 버블 정렬
  • 장점 : 인접한 값만 계속해서 비교하는 방식으로 구현이 쉬우며, 코드가 직관적이다. n개 원소에 대해 n개의 메모리를 사용하기에 데이터를 하나씩 정밀 비교가 가능하다.
  • 단점 : 최선이든 최악이든 $O(N^2)$이라는 시간복잡도를 가진다. n개 원소에 대해 n개의 메모리를 사용하기에 원소의 개수가 많아지면 비교 횟수가 많아져 성능이 저하된다.

 

• 힙 정렬 
  • 장점 : 추가적인 메모리를 필요로하지 않으면서 항상 $O(N\times logN)$의 시간 복잡도를 가진다. $O(N\times logN)$인 정렬 방법 중 가장 효율적인 정렬방법이라 할 수 있다. 퀵 정렬의 경우 효율적이나 최악의 경우 시간이 오래걸린다는 단점이 있으나 힙 정렬의 경우 항상 $O(N\times logN)$이 보장된다.
  • 단점 : 이상적인 경우에 퀵정렬과 비교했을 때 똑같이 $O(N\times logN)$이 나오긴 하나 실제 시간을 측정하면 퀵정렬보다 느리다고 한다. 즉, 데이터의 상태에 따라서 다른 정렬들에 비해서 조금 느린편이다. 또한, 안정성을 보장받지 못한다.

 

• 선택 정렬
  • 장점 : 정렬을 위한 비교 횟수는 많으나 교환 횟수가 적기에, 교환이 많이 이루어져야 하는 상태에서 효율적으로 사용될 수 있으며, 이에 가장 적합한 자료상태는 역순 정렬이다. 즉, 내림차순이 정렬되어 있는 자료를 오름차순으로 재졍렬할 때 적합하다. 
  • 단점 : 정렬을 위한 비교 횟수가 많으며, 이미 정렬된 상태에서 소수의 자료가 추가되면 재정렬할 때 최악의 처리 속도를 보인다.

 

• 빠른 정렬
  • 장점 : 기준값(Pivot)에 의한 분할을 통해 구현하는 정렬 방법으로, 분할 과정에서 $logN$이라는 시간이 소요되며, 전체적으로 $N\times logN$으로 준수한 편이다.
  • 단점 : 기존값에 따라 시간복잡도가 크게 달라진다(안정성이 없다). 기준값을 이상적인 값으로 선택했다면 $N\times logN$의 시간복잡도를 가지지만, 최악의 기준값을 선택할 경우 $O(N^2)$라는 시간복잡도를 갖게 된다.

 

• 삽입 정렬
  • 장점 : 최선의 경우 $O(N)$이라는 빠른 효율성을 가지고 있다. 버블정렬의 비교횟수를 줄이기 위해 고안된 정렬이다. 버블정렬의 경우 비교대상의 메모리 값이 정렬되어 있더라도 비교연산을 진행하나, 삽입정렬은 버블정렬의 비교횟수를 줄이고 크기가 적은 데이터 집합을 정렬하는 알고리즘을 작성할 때 효율이 좋다.
  • 단점 : 최악의 경우 $O(N^2)$이라는 시간복잡도를 가지게 된다. 즉, 데이터의 상태와 크기에 따라 성능의 편차가 큰 정렬 방법이다.

 

• 병합 정렬
  • 장점 : 퀵 정렬과 비슷하게 원본 배열을 절반씩 분할해가면서 정렬하는 정렬법으로써 분할하는 과정에서 $logN$ 만큼의 시간이 소요된다. 즉, 최종적으로 보게되면 $N\times logN$이 된다. 또한 퀵 정렬과 달리 기준값을 설정하는 과정없이 무조건 절반으로 분할하기에 기준값에 따라 성능이 달라지는 경우가 없다. 따라서 항상 $O(N\times logN)$이라는 시간복잡도를 가지게 된다.
  • 단점 : 병합정렬은 임시배열에 원본맵을 계속해서 옮겨주며 정렬을 하는 방식이기에 추가적인 메모리가 필요하다는 점이다. 데이터가 최악인 면을 고려하면 퀵 정렬보다는 병합정렬이 훨씬 빠르기 때문에 병합정렬을 사용하는 것이 많지만, 추가적인 메모리를 할당할 수 없다면 병합정렬을 사용할 수 없기 때문에 퀵을 사용해야 하는 것이다.

 

• 쉘 정렬
  • 장점 : 삽입정렬의 단점을 보완하고 개념을 확대해서 만든 정렬방법으로, 삽입 정렬에 비해 성능이 우수하며, 어떤 데이터가 제 위치에서 멀리 떨어져있을 경우 여러 번의 교환이 발생하는 버블정렬의 단점을 해결한다.
  • 단점 : 일정한 간격에 따라 배열을 보아야 하며, 간격을 잘못 설정할 경우 성능이 급격히 저하될 수 있다.

 

• 기수 정렬
  • 장점 : $O(N)$이라는 시간복잡도를 가지는 정렬방법으로 매우 빠른 속도를 가지고 있다.
  • 단점 : 버킷이라는 데이터 전체 크기와 기수 테이블의 크기만큼의 추가적인 메모리가 할당되어야 한다. 

 

• 카운팅 정렬
  • 장점 : 비교를 하지 않고 정렬하는 방법으로 $O(N)$이라는 시간복잡도를 가지게 된다.
  • 단점 : 숫자 갯수를 저장해야 될 별도의 공간, 또 결과를 저장할 별도의 공간 등 추가적인 메모리가 필요하다.

 

정렬 알고리즘 장단점 요약

---

Sorting	장점	단점
버블 정렬	인접한 두 개의 데이터를 비교하기에 구현이 쉬우며 정밀 비교 가능	원소의 갯수가 많아지면 비교 연산이 많아져서 성능이 저하
선택 정렬	정렬을 위한 교환 횟수가 적어 내림차순된 데이터를 오름차순할 때 효율이 좋음	정렬 비교 횟수가 많고, 정렬된 상태서 소수의 자료가 추가되면 재정렬 시 최악의 처리 속도를 보임
삽입 정렬	버블정렬의 비교횟수를 줄이기 위해 고안된 방법이며, 크기가 적은 데이터 집합을 정렬하는 알고리즘을 작성할 때 효율이 좋음	데이터의 상태와 크기에 따라 성능 편차가 큰 정렬 방법
힙 정렬	추가적인 메모리를 필요로하지 않으면서 항상 시간 복잡도 $O(N\times logN)$ 를 가짐	실제 시간을 측정 시 퀵정렬보다 느림. 즉, 데이터의 상태에 따라서 다른 정렬들에 비해 느린편. 안정성을 보장받지 못함
병합 정렬	퀵 정렬과 달리 기준값을 설정하는 과정없이 무조건 절반으로 분할하기에 기준값에 따라 성능이 달라지는 경우가 없음	병합정렬은 임시배열에 원본맵을 계속해서 옮겨주며 정렬을 하는 방식이기에 추가적인 메모리가 필요
퀵 정렬	기준값(Pivot)에 의한 분할을 통해 구현하는 정렬 방법으로, 분할 과정에서 $logN$이라는 시간이 소요되며, 전체적으로 $N\times logN$으로 준수	최악의 기준값을 선택할 경우 $O(N^2)$라는 시간복잡도를 가짐
기수 정렬	$O(N)$이라는 시간복잡도를 가지는 정렬방법으로 매우 빠른 속도를 가짐	버킷이라는 데이터 전체 크기와 기수 테이블의 크기만큼의 추가적인 메모리가 할당돼야 함

 

 

Reference

---

[1] https://tctt.tistory.com/47

[2] https://yabmoons.tistory.com/250

[3] https://hsp1116.tistory.com/33

[4] https://yaraba.tistory.com/79