본문 바로가기
알고리즘, 자료구조/알고리즘 개념

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

by Wordbe 2019. 8. 31.
728x90

정렬(Sort)

비교정렬(Comparision Sort)

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

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

O(N2) 정렬

1. 버블 정렬(Bubble sort)

장점 :

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

단점 :

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

2. 선택 정렬(Selection sort)

장점 :

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

단점 :

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

3. 삽입 정렬(Insertion sort)

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

장점 :

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

단점 :

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

4. 쉘 정렬(Shell sort): O(N(logN)2) or O(N1.25)

장점:

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

단점:

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

O(NlogN) 정렬

1. 퀵 정렬(Quick sort)

장점:

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

단점:

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

  • 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/

728x90

댓글