[알고리즘] 정렬 알고리즘 개요

정렬이란?

- 이름, 학번, 학점 등의 특정 키를 기준으로 대소 관계에 따라 데이터의 집합을 일정한 순서로 바꾸어서 늘어놓는 작업이다.

- 값이 작은 데이터부터 앞쪽에 늘어놓는 것: 오름차순(ascending order) 예) a = [1, 2, 3, 4, 5]

- 값이 큰 데이터부터 앞쪽에 늘어놓는 것: 내림차순(descending order) 예) a = [5, 4, 3, 2, 1]

- 정렬 알고리즘은 시간 복잡도에 따라 성능이 좌우되고, 성능이 좋은 알고리즘일수록 구현 방법이 어려워진다.

 

정렬 알고리즘의 시간복잡도

- O(n²): 버블 정렬, 선택 정렬, 삽입 정렬, 셸 정렬(최악 O(n²), 최선O(n log n))

- O(n log n): 병합 정렬, 퀵 정렬, 힙 정렬

- O(n): 도수 정렬

 

정렬 알고리즘의 핵심: 교환, 선택, 삽입

 

내부 정렬 알고리즘과 외부 정렬 알고리즘

- 내부 정렬(internal sorting): 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용(대부분의 알고리즘)

- 외부 정렬(external sorting): 정렬할 데이터의 양이 많아 하나의 배열에 저장할 수 없는 경우에 사용

 

안정적인 정렬 알고리즘과 불안정적인 정렬 알고리즘

- 안정적인 정렬 알고리즘: 값이 같은 원소의 순서가 정렬한 후에도 유지되는 것.

- 불안정적인 정렬 알고리즘: 정렬한 후에도 원래의 순서가 유지된다는 보장이 없음.

 

정렬 알고리즘을 사용했을 때의 결과