[알고리즘] 정렬 알고리즘(2)

선택 정렬

 제일 큰 값을 찾아 맨 뒤의 요소와 교체하는 방법을 반복하여 전체를 정렬하는 알고리즘이다. 

 시간 복잡도는 최선/최악 모두 O(n^2)이다.

 

삽입 정렬

 점진적으로 정렬 범위를 넓혀 나가는 방식으로 정렬하는 알고리즘이다. 새로운 범위에 포함되는 마지막 원소보다 앞을 탐색하며 자신보다 작은 요소를 찾을 때까지 이동하면서 자리를 교환한다.

시간복잡도는 최선으로는 O(n) , 최악으로는 O(n^2)이다.

 

쉘 정렬

 삽입 정렬 알고리즘을 이용하는 정렬 방식으로, 같은 간격에 있는 원소들을 삽입 정렬 원리로 정렬하는 것을 반복한다. 간격의 초기 값을 1/2 씩 줄이며 반복한다.

 

퀵 정렬 

  재귀적인 방법으로 문제를 해결하는 알고리즘으로, 피벗 값을 선택하여 피벗 값보다 작은 값들은 왼쪽으로 보내고 큰 값들은 오른쪽으로 보낸 후에 다시 이들 사이에 피벗을 설정하는 원리를 이용한다. 피벗 값이 어떠냐에 따라 성능이 달라진다(반->좋은 성능, 최대/최소 -> 최악의 성능) 

 평균적으로 가장 빠른 정렬이고, 분할 정복법을 사용한다. 

 시간복잡도는 최선 O(nlog n ) / 최악 O(n^2)이다.

 

병합정렬

  배열을 작은 단위의 배열로 분할한 후에 분할한 배열을 정렬하고 이들을 다시 정렬하면서 전체 배열을 정렬하는 알고리즘이다. 

 무조건 배열을 절반으로 분할하기 때문에 항상 O(NlongN)이라는 시간복잡도를 갖게된다. 단, 추가적인 메모리가 요구되기에 메모리 공간이 부족하는 경우가 생길 수 있다.

 

힙 정렬

 힙 트리를 이용하는 알고리즘으로, 최대 힙을 사용하면 크기순으로 정렬하고 최소 힙을 사용하면 크기 역순으로 정렬한다.

 루트의 값과 맨 마지막 값을 교환한 후에 정렬 범위를 1 줄인다. 이와 같은 작업을 반복하여 정렬 범위가 1일 때까지 반복한다.

 

 

기수 정렬 

  O(N)이라는 시간 복잡도를 갖는 정렬법으로 엄청나게 빠르다. 

  버킷이라는 추가적인 메모리가 할당되어야 한다는 단점이 있다. 특정한 데이터 타입에 한해서만 적용 가능하며, 제약조건이 굉장이 많이 붙는다.

 

카운팅 정렬

  정렬을 통해 O(N)이라는 시간 복잡도를 가지며, 추가적인 메모리가 필요하다는 단점이 있다. 이상값 때문에 과도한 메모리의 낭비가 발생할 수 있다.