[Algorithm] 정렬

정렬 알고리즘의 종류에 따라 개념 및 특징 정리를 하기 위해 글을 포스팅 한다.

1. 버블 정렬

- 인접한 두 개의 요소를 비교해 가면서 정렬을 진행하는 방식

- 장점) 구현이 매우 간단함

- 단점) 순서에 맞지 않는 요소들의 교환이 자주 일어남

- 시간 복잡도

  - 최악의 경우, O(n^2)

  - 평균, O(n^2)
  - 최선의 경우, O(n)

 

2. 선택 정렬

- 전체 범위에서 차례대로 가장 작은 숫자를 탐색하고, 가장 왼쪽부터 차례대로 교환하는 방식

- 장점) 자료 이동 횟수가 미리 결정

- 단점) 값이 같은 요소가 있다면 상대적인 위치가 변경될 수 있음

- 시간 복잡도

  - 최악의 경우, 평균, 최선의 경우 모두 O(n^2)

 

3. 삽입 정렬

- 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입하는 방식

- 단점) 요소가 너무 많으면 비교적 많은 이동을 해야 하므로 성능이 좋지 않음

- 시간 복잡도

  - 최악의 경우, O(n^2)

  - 평균, O(n^2)

  - 최선의 경우, O(n)

 

4. 병합 정렬

- '분할 정복’ 이라는 알고리즘 디자인 기법에 근거하여 복잡한 문제를 복잡하지 않은 문제로 분할 하여 정복 하는 방식

- 병합 과정에서 정렬 발생

- 장점) 데이터 분포의 영향을 덜 받음

- 단점) 요소를 배열로 구성하면, 임시 배열이 필요함

- 시간 복잡도

  - 최악의 경우, 평균, 최선의 경우 모두 O(nlogn)

 

5. 퀵 정렬

- 특정 요소를 기준점 (pivot) 으로 잡고 기준점보다 작은 요소는 왼쪽, 큰 요소는 오른쪽으로 두고 왼쪽과 오른쪽을 각각 정복 하는 방식

- 장점) 평균 실행시간이 다른 알고리즘보다 빠른 편

- 단점) pivot 에 따라 성능 차이가 심함

- 시간 복잡도

  - 최악의 경우, O(n^2)

  - 평균, O(nlogn)

  - 최선의 경우, O(nlogn)

 

6. 힙 정렬

- '완전 이진 트리’인 최대 힙 트리 또는 최소 힙 트리를 구성해 정렬 하는 방식

- 전체 자료가 아닌 가장 큰 값 몇 개만 필요한 경우를 정렬할 때 유용

- 장점) 시간 복잡도가 좋은 편

- 시간 복잡도 

  - 최악의 경우, 평균, 최선의 경우 모두 O(nlogn)

 

7. 출처

https://www.youtube.com/watch?v=ww6URL1l1ho&list=WL&index=13 

[ 우아한 테크 - 10분 테크톡, 마크의 정렬 알고리즘 ]