(코딩 인터뷰) 정렬 알고리즘 장단점 및 특징

< 선택 정렬 >

시간복잡도: O(N^2)
->선택 정렬은 비교는 많지만, 교환은 적은 알고리즘이다.
 장점: 정렬된 상태를 역순으로 정렬시 효율적이다.
 단점: 정렬된 데이터에 소수의 데이터 추가시 이를 다시 정렬하기 위해서는 최악이다.


 < 버블 정렬>

시간복잡도: O(N^2)

->데이터를 하나씩 비교할 수 있어서 정밀하게 비교 가능하나 비교횟수가 많아지므로
성능면에서 좋은 방법이 아니다. 첫번째 원소부터 마지막 원소까지 비교가 끝나면 가장 큰 원소를 마지막 자리로 정렬한다.


< 퀵정렬 >

시간복잡도
최악- O(N^2)
평균- O(NlogN)

->캐시라는 지역적 특성에 의해 실제적으로 NlogN보다 좋은 성능을 보여 가장 많이 사용하는 정렬이다. 단점으로는 안정성이없다. 안정성이 없다는 것은 정렬되기 이전의 데이터 동일한 데이터끼리의 순서를 정렬 후에도 유지하고 있는가이다.



< 삽입정렬 >

시간복잡도 : O(N^2)

버블정렬이 조금 비효율적인 면이 있기에 비교횟수를 효율적으로 줄이기 위해 고안된 삽입정렬이다. 버블정렬은 비교대상의 메모리 값이 정렬되어 있음에도 불구하고 비교연산을 하는 부분이 있는데 삽입정렬은 비교적 비교횟수를 줄이고 , 정렬된 값은 한번도 교환이 일어나지 않고 N-1의 비교만 일어난다.


< 쉘 정렬 >

시간복잡도: O(N^1.25)

삽입정렬의 개념을 확대하여 일반화한 정렬방법이다. 알고리즘이 간단하여 간단히 구현할 수 있다. 수행능력도 삽입정렬보다 우수하다. 멀리있는 레코드들 끼리 비교 및 교환 될 수 있으므로, 어떤 데이터가 제 위치에서 멀리 떨어져 있다면 여러 번의 교환이 발생하는 버블정렬의 단점을 해결 할 수 있다.


<병합 정렬>

시간복잡도: O(NlogN)

작은 단위부터 정렬해서 정렬된 단위들을  계속 병합해가면서 정렬하는 방식이다. 알고리즘 중에 가장 간단하고 쉽게 떠올릴 수 있는 방법이다. 안정성이 있으며 상당히 좋은 성능을 나타낸다. 큰 결점은 데이터 크기만한 메모리가 더 필요하다는 것이다.

<버킷정렬>

버킷정렬은 정렬대상의 키들을 일정한 범위로 구분해 버킷(통)에 넣고 그 버킷을 각각 정렬하는 방법이다.

특징: 키가 어떤 범위내에서 키값이 확률적으로 균등하게 분포되어 있을 때 적용하면 효과가 좋다.
  실행시간: 버켓에 넣는 시간 O(n)+정렬시간

사용하기 좋은 예: "Person 객체를 담은 아주 큰 배열이 있다고 하자. 이 배열에 담긴 객체들을 나이순으로 정렬하라"
  여기서 두 힌트를 얻을 수 있다.
1. 큰 배열이므로 효율성이 중요하다.
2. 나이에 따라 정렬하는 것이므로, 그 값의 범위가 좁게 제한되어 있음을 이용할 수 있다.

정렬 알고리즘들을 살펴보면, 아마 버킷정렬 또는 기수 정렬이 가장 적합하리라는 것을 눈치 챌 수 있을 것이다. 버킷을 작게 만들 수 있고(각 버킷에 1년)O(n)으 실행시간을 달성할 수 있다. 그렇다면 값의 범위가 작을 때 사용하기 좋은 정렬인것인가???