[Sort] 대표적인 정렬의 모든 것

정렬(Sort)

비교정렬(Comparision Sort)

비교하여 정렬하는 방법은, 아무리 알고리즘을 잘 짜도 O(NlogN)보다 크다.

그렇지만, O(NlogN)도 충분히 빠른 정렬이고, 일반적인 경우에 대해 정렬할 수 있는 방법이기 때문에 이를 공부하는 것은 중요하다.

O(N²) 정렬

1. 버블 정렬(Bubble sort)

장점 :

• "순서대로 대소 비교 후 큰 것을 뒤로 보낸다."를 그대로 구현하면 되기 때문에,
• 코드가 보기에 직관적이므로 구현이 쉽다.
• stable 정렬이다.

단점 :

• 최악이든 최선이든 O(N²)이기 때문에 굉장히 비효율적이다.

2. 선택 정렬(Selection sort)

장점 :

• "최댓값을 찾고, 맨 뒤의 원소와 바꾸어준다"를 그대로 구현하면 된다. 구현이 쉽다.
• 원소 교환 횟수가 적어서(N번), 교환이 많이 일어나야 하는 배열에서 유리하다.
• stable 정렬이다.

단점 :

• O(N²), 시간이 오래걸린다. 100,000개 이상 인풋에서는 대략 10초가 넘어간다.

3. 삽입 정렬(Insertion sort)

​ "순서대로 하나씩 뽑으면서, 적당한 위치에 삽입한다."

장점 :

• 최선의 경우 (배열이 이미 거의 정렬되어 있을 때) O(N) 이다.
• 성능이 좋아 다른 정렬 알고리즘의 일부로 사용되기도 한다.
• stable 정렬이다.

단점 :

• 최악의 경우 O(N²) 이다. 데이터 상태, 크기에 따라 성능의 편차가 심하다.

4. 쉘 정렬(Shell sort): O(N(logN)²) or O(N^1.25)

장점:

• 삽입 정렬을 개선한 정렬이다.
• 삽입 정렬을 이용한 코드이기 때문에, 이해하기 쉽고, 간결하다.
• 멀리 떨어져 있는 자료를 교환함으로써, 입력자료에 민감하지 않다.

단점:

• '간격'을 잘못 설정하면, 성능이 O(N²) 까지 악화될 수 있다.

O(NlogN) 정렬

1. 퀵 정렬(Quick sort)

장점:

• 분할과정에서 logN, partition에서 N시간이 걸려 평균적으로 O(NlogN) 으로 빠르게 정렬된다.
• 최선의 성능을 낼 때는 병합정렬, 힙정렬보다 빠르다.

단점:

• 신뢰성이 낮다. 기준값(pivot)에 따라 시간복잡도가 크게 달라지고, 최악의 경우 O(N²)이 나온다. 고로, 안정적인 시간복잡도를 요구하는 곳(사용자에게 데이터베이스 쿼리 결과생성 등)에서 사용할 수 없다.

• unstable 정렬이다. 중복되는 key값에 대해 순서대로 정렬되지 않는다.

2. 병합 정렬

장점:

• 안정적으로 준수한 시간 내에 정렬한다. O(NlogN) 시간 복잡도이다. 이는 매우 큰 장점이다.
• stable 정렬이다.

단점:

• 추가적인 메모리가 필요하다. 임시배열 temp[]에 원본 배열의 복사가 필요하다. 배열의 크기가 상당히 큰 경우 부담이 될 수도 있다.

3. 힙 정렬

장점:

• 추가적인 메모리를 필요로 하지 않으면서, 최악의 경우에도 O(NlogN)을 보장한다.

단점:

• 데이터에 분포에 따라 결과가 다르게 나오는, 불안정성이 있다.
• unstable 정렬이다.

(비비교 정렬)Non-Comparision Sort

O(N) 정렬 - 특수한 상황에서만 동작

1. 계수 정렬

장점:

• 매우 빠른시간에 정렬할 수 있다.
• stable 정렬이다.

단점:

• 배열의 인덱스를 이용하기 때문에 정해진 범위에 한정하여 정렬할 수 있다.

2. 기수 정렬

장점:

• 매우 빠른시간에 정렬할 수 있다.
• stable 정렬이다.

단점:

• O(d(N + k))의 시간복잡도를 가진다. d는 자릿 수, n은 배열 안 원소 수, k는 요소 값 중 최댓값.

정렬 알고리즘의 효율성 비교

성능비교

코드 정리

https://github.com/Wordbe/Algorithms/blob/master/sort/