[알고리즘] 정렬 알고리즘(Sort Algorithm)

정렬 알고리즘

정렬 알고리즘이란? : 배열과 같은 리스트에 저장된 요소들을 특정한 순서대로 재배치하는 알고리즘

 

정렬 알고리즘 선택 시 고려 사항

- 시간 복잡도

- 메모리 사용량

- 안정성(stability)

- 직렬 vs 병렬

위와 같은 것들을 고려해야 하기 때문에 정렬 알고리즘 선택 이전에 정렬할 데이터의 양, 이미 정렬된 정도, 필요한 추가 메모리의 양 등을 고려해서 적절한 알고리즘을 선택하는 과정이 필요하다.

 

정렬 알고리즘 7가지

1. 선택 정렬 (Selection Sort) : 선택된 값과 나머지 데이터를 비교하여 알맞은 자리를 찾는 알고리즘. (안정성 보장 X)

ㅡ> 시간복잡도 worst, average, best : O(n^2) 

 

2. 삽입 정렬 (Insertion Sort) : 데이터를 순회하면서 정렬이 필요한 요소를 뽑아 이를 다시 적당한 곳에 삽입하는 알고리즘.

*성능이 버블 정렬보다는 좋음

ㅡ> 시간복잡도 worst, average : O(n^2), 이미 정렬되어 있는 best : O(n)

 

3. 버블 정렬 (Bubble Sort) : 거품이 수면으로 올라오듯 인접한 두 수를 비교하여 오름차순 or 내림차순으로 정렬하는 알고리즘. (안정성 보장)

ㅡ> 시간복잡도 worst, average, best : O(n^2) 

 

4. 병합 정렬 (Merge Sort) : 두 개의 부분집합으로 데이터를 나누고 각 부분집합을 정렬한 다음 부분집합들을 다시 정렬된 형태로 합치는 방식의 알고리즘. (안정성 보장)

*분할 정복법(Divide and Conquer) 사용

1. 분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할
2. 정복 : 각각의 작은 문제를 순환적으로 해결
3. 합병 : 작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함.

*병합 정렬은 데이터 집합이 메모리에 한번에 올리기에 너무 클때 쓰기에 적합한 알고리즘.

*다른 알고리즘과 비교했을 때, O(n) 수준의 메모리가 추가적으로 필요함.

ㅡ> 시간복잡도 worst, average, best : O(n log n) 

 

5. 힙 정렬 (Heap Sort) : 트리 기반으로 최대 힙 트리 or 최소 힙 트리를 구성하여 정렬하는 알고리즘. (안정성 보장 X)

내림차순 정렬 ㅡ> 최대 힙, 오름차순 정렬 ㅡ> 최소 힙

*완전 이진트리여야 함.

ㅡ> 시간복잡도 worst, average, best : O(n log n)

 

6. 퀵 정렬 (Quick Sort) : 데이터 집합 내에 임의의 기준(pivot) 값을 정하고 해당 피봇을 기준으로 두개의 부분 집합으로 나눈다. 한쪽 부분에는 피봇보다 작은값, 나머지 한쪽은 피봇보다 큰 값을 넣어 정렬하는 알고리즘. (안정성 보장 X)

*더 이상 쪼갤 부분 집합이 없을 때까지 각각의 부분 집합에 대해 피봇/쪼개기 재귀적으로 적용.

*병합 정렬과 마찬가지로 분할 정복법 사용. 범위, 기준, 비교, 스왑 순서

ㅡ> 시간복잡도 best, average : O(n log n), worst : O(n^2)

 

7. 기수 정렬 (Radix Sort) : 낮은 자리수부터 비교해가며 정렬. 비교연산을 하지 않아 빠르지만, 기수 테이블의 크기만한 또 다른 메모리 공간을 필요로 하는 것이 단점.

ㅡ> 시간복잡도 O(dn) 

*d는 자리수

 

참고자료

https://hyo-ue4study.tistory.com/68

[알고리즘]정렬 알고리즘의 선택과 종류 7가지