정렬 알고리즘의 특징 정리

2021년 08월 31일 / 4 댓글

버블 정렬
- 인접한 원소끼리 자리 교환을 통해 첫 번째 원소부터 마지막 원소까지 정렬하는 방식
- 장점
  - 구현이 쉽다
- 단점
  - 다른 정렬 알고리즘에 비해 성능이 좋지않다

선택 정렬
- 첫 번째 원소부터 자신의 뒤에 속하는 원소들과 순차적인 비교를 통해 자리를 교환하여 정렬하는 방법
- 장점
  - 버블 정렬과 마찬가지로 구현이 쉽다
- 단점
  - 버블 정렬과 마찬가지로 성능이 좋지않다

삽입 정렬
- 두 번째 원소부터 자신의 앞에 먼저 정렬된 배열 안에서 자신의 위치를 찾아 삽입하는 방법
- 장점
  - 최적의 상태에서 빠른 성능을 가진 알고리즘
- 단점
  - 성능의 편차가 심하다 (입력 자료가 역순일 경우 O(N²)의 느린 성능을 갖게됨)

셸 정렬
- 삽입 정렬에서 고안된 방법
- 정렬할 리스트를 임의의 기준에 따라 분류한 후 분류한 리스트를 여러 개의 부분 리스트로 만들어 각 부분 리스트를 삽입 정렬한 후 다시 전체 리스트를 더 적은 수의 부분 리스트로 만드는 작업을 반복하여 정렬하는 방법
- 장점
  - 성능이 비교적 빠른 편이다
    삽입 정렬과 다르게 먼 거리의 대상으로 위치 이동이 효율적이다
- 단점
  - 성능의 편차가 심하며 최악의 경우 성능이 좋지않다

퀵 정렬
- 다른 원소와의 비교를 통한 정렬로 비교 정렬에 속한다.
- pivot 값을 정한 후 왼쪽부터 pivot 값보다 큰 값을 오른쪽부터 pivot 값보다 작은 값을 찾아 값을 교환하는 작업을 반복하여 정렬하는 방법
- 장점
  - O(NlogN)의 빠른 연산 속도를 가지고 있고 O(NlogN) 중에서 빠른 편에 속한다
- 단점
  - 최악의 경우 성능이 좋지않다

힙 정렬
- 이진트리 구조로 부모 노드와 자식 노드의 크기 비교를 통해 노드 간 데이터 교환으로 정렬하는 방법
- 장점
  - 우선순위 큐 구현에 효율적이다
- 단점
  - 완전 정렬이 아닌 반정렬이며 O(NlogN) 중 느린 편에 속한다

병합 정렬
- 작은 단위로 쪼개어 작은 단위부터 정렬해서 정렬된 단위들을 계속 병합해가면서 정렬하는 방식
- 장점
  - 안정적인 성능을 가지고 있는 편이다
- 단점
  - 데이터를 나누고 병합하는 과정에서 더 많은 메모리를 차지한다

정렬 알고리즘	최선 시간복잡도	평균 시간복잡도	최악 시간복잡도	공간복잡도
버블 정렬	N²	N²	N²	1
선택 정렬	N²	N²	N²	1
삽입 정렬	N	N²	N²	N
셸 정렬	N	N^1.5	N²	N
퀵 정렬	NlogN	NlogN	N²	logN
힙 정렬	NlogN	NlogN	NlogN	1
병합 정렬	NlogN	NlogN	NlogN	N

참고 – 위키백과

댓글 4개

답글 남기기 응답 취소

이 사이트는 스팸을 줄이는 아키스밋을 사용합니다. 댓글이 어떻게 처리되는지 알아보십시오.