정렬 알고리즘이란?
목록안에 저장된 요소들을 특정한 순서대로 재배치하는 알고리즘이다.
입력데이터는 보통 배열과 같은 데이터 구조(연결리스트를 사용하면 시작점부터 차례대로 훑어야해서 정렬시 사용이 복잡해진다)
사용하는 이유
- 데이터 검색 효율을 향상시킬 수 있다.
정렬된 데이터는 이진 검색 등의 고속 검색 알고리즘을 사용할 수 있어 데이터 검색 속도가 빨라진다. - 데이터 처리 및 분석 편의성 향상
시각화, 통계 분석 등 다양한 데이터 처리 작업에 유용하다. - 데이터 관리 및 저장 효율성 향상
중복 제거, 압축 등의 작업에 효과적이다. - 알고리즘 설계 및 구현 편의성 향상
정렬된 데이터를 바탕으로 다양한 알고리즘을 보다 쉽게 설계하고 구현할 수 있다. 또한 다른 알고리즘(병합 정렬, 힙 정렬 등)과 조합하여 활용할 수 있다.
사용시 고려사항
- 시간 복잡도
O(n^2)
a. 버블 정렬
b. 선택 정렬
c. 삽입 정렬
O(n log n)
d. 퀵 정렬
e. 병합 정렬
f. 힙 정렬
등등....
- 메모리 사용량
- 정렬 알고리즘에 따라 추가적인 메모리 공간이 필요할 수 있다.
ex) 제자리 정렬 알고리즘은 추가 메모리 공간을 필요로 하지 않지만, 병합 정렬과 같은 알고리즘은 추가 메모리 공간이 필요하다. - 따라서 메모리 사용량이 중요한 경우 제자리 정렬 알고리즘을 사용하여야 한다.
- 안정성(stable)
- 안정 정렬 알고리즘은 입력 데이터에서 순서가 같은 요소의 상대적인 순서를 유지한다.
- 안정성을 고려해야 하는 경우 삽입 정렬, 병합 정렬, 버블 정렬 등의 안정 정렬 알고리즘을 사용해야 한다.
- 직렬 vs 병렬
- 직렬
- 순차적으로 데이터를 처리한다
- 병렬
- 여러 프로세서를 활용하여 병렬로 데이터를 처리한다.
- 대량의 데이터를 빠르게 정렬할 수 있지만, 이에 대한 추가 리소스가 발생한다.
따라서 데이터의 크기, 자원, 문제의 특성 등을 고려하여 직렬 또는 병렬을 선택하여야 한다.
종류
선택 정렬(Selection Sort)
선택된 값과 나머지 데이터 중 비교하여 알맞은 자리를 찾는 알고리즘이다.
삽입 정렬(Insertion Sort)
데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 이를 다시 적당한 곳으로 삽입하는 알고리즘 이다.
버블 정렬(Bubble Sort)
인접한 두 수를 비교하여 오름차순or내림차순으로 정렬한다.
병합 정렬(Merge Sort)
둘 이상의 부분집합으로 가르고, 각 부분집합을 정렬한 다음 부분집합들을 다시 정렬된 형태로 합치는 방식이다.
이 정렬은 데이터의 집합이 메모리에 한번에 올리기에 너크 클때 사용하기 좋은 방법이다.
ex) 큰 파일의 내용을 여러개의 작은 파일로 나누어 적당한 알고리즘으로 정렬하고 다시 저장하는 식으로 합치기
- 분할 정복법 사용(Divide-And_Conquer)
- 분할: 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할한다.
- 정복: 각각의 작은 문제를 순환적으로 해결한다.
힙 정렬(Heap Sort)
트리 기반으로 최대 힙 트리 혹은 최소 힙 트리를 구성해 정렬을 하는 방법이다.
- 완전 이진트리여야한다.
퀵 정렬(Quick Sort)(분할 정복)
데이터 집합 내에 임의의 기준(pivot) 값을 정하고 해딩 피벗으로 집합을 기준으로 두개의 부분 집합으로 나눈다.
더 이상 쪼갤 부분 집합이 없을 때까지 각각의 부분 집합에 대해 피벗/쪼개기를 재귀적으로 적용한다.
기수 정렬(Radix Sort)
낮은 자리수부터비교해가며 정렬한다. 비교 연산을 하지 않아 빠르지만, 데이터 전체 크기에 기수 테이블의 크기만한 또 다른 메모리 공간이 필요하다는게 단점이다.
