정렬 알고리즘
정렬 알고리즘(sorting algorithm)이란 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다. 효율적인 정렬은 탐색이나 병합 알고리즘처럼 (정렬된 리스트에서 바르게 동작하는) 다른 알고리즘을 최적화하는 데 중요하다. 또 정렬 알고리즘은 데이터의 정규화나 의미있는 결과물을 생성하는 데 유용히 쓰인다.
sort(vector.begin(), vector.end(), operator)
sort(array, array + int, operator)
[출처] 위키백과 - 정렬 알고리즘
* 연관 문제:
- [백준] 11651번: 좌표 정렬하기 2
- [백준] 10817번: 세 수 (배열 정렬)
안정 정렬 (Stable Sort)
동등한 요소의 순서는 보존하면서 정렬하는 방식이다.
반복되는 요소를 입력 때와 동일한 순서로 정렬시킨다. 특정한 유형의 데이터를 정렬할 때 정렬 순서 결정 시 데이터의 일부분만 검사한다.
안정성은 몇 가지 이유로 중요하다. 예를 들어, 데이터가 학생 이름으로 우선 정렬되면(일부의 경우 웹 페이지에 동적으로) 데이터는 이제 어느 학급에 위치하는지에 따라 다시 정렬된다. 학생들이 같은 학급에 있다고 가정한다면 이들의 이름 순서는 특정한 순서가 아니게 뒤섞이며 이는 성가신 문제일 수 있다. 정렬 알고리즘이 안정적이면 학생 이름은 정상적인 순서에 위치할 수 있다.
template <class RandomIt, class Compare>
void stable_sort(RandomIt first, RandomIt last, Compare compare);
- #include <algorithm>
- first, last: 정렬 범위
- compare: 비교 함수
int compare(const void* a, const void* b);
[출처] cppreference.com - std::stable_sort
[출처] 위키백과 - 정렬 알고리즘
* 연관 문제:
- [백준] 10814번: 나이순 정렬
퀵 정렬 (Quick Sort)
다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n²)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다.
퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고(그 이유는 메모리 참조가 지역화되어 있기 때문에 CPU 캐시의 히트율이 높아지기 때문이다.), 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다. 또한 매 단계에서 적어도 1개의 원소가 자기 자리를 찾게 되므로 이후 정렬할 개수가 줄어든다. 때문에 일반적인 경우 퀵 정렬은 다른 O(n log n) 알고리즘에 비해 훨씬 빠르게 동작한다. 이러한 이유로 퀵소트(빠른정렬)라는 이름의 기원이 되었다. 그리고 퀵 정렬은 정렬을 위해 평균적으로 O(log n)만큼의 memory를 필요로한다. 이는 재귀적 호출로 발생하는 것이며, 최악의 경우 O(n)의 공간복잡도를 보인다.
void qsort (void* base, size_t num, size_t size, int (*compare)(const void*,const void*));
- #include <cstdlib>
- base: 배열 첫번재 원소의 주소값
- num: 배열의 사이즈
- size: 배열 원소 타입의 사이즈
- compare: 함수 포인터의 값을 비교하는 함수
int compare(const void* a, const void* b);
- a negative integer if the first argument is less than the second
- a positive integer if the first argument is greater than the second
- zero if both arguments are equal
[출처] 위키백과 - 퀵 정렬
[출처] C++ qsort()
* 관련 문제
- [백준] 25305번: 커트라인
카운팅 정렬 (Counting Sort)
계수 정렬 또는 카운팅 소트(counting sort)는 컴퓨터 과학에서 정렬 알고리즘의 하나로서, 작은 양의 정수들인 키에 따라 객체를 수집하는 것, 즉 정수 정렬 알고리즘의 하나이다. 구별되는 키 값들을 소유하는 객체의 수를 계수하고 출력 시퀀스에 각 키 값의 위치를 결정하기 위한 해당 계수에 전위합을 적용함으로써 동작한다. 실행 시간은 항목의 수, 그리고 최대 키 값과 최소 키 값의 차이에 선형적이므로 키의 다양성이 항목의 수보다 상당히 크지 않은 상황에서 직접 사용하는 데에만 적절하다. 더 큰 키들을 더 효율적으로 처리할 수 있는 다른 정렬 알고리즘인 기수 정렬의 서브루틴에 종종 사용된다.
계수 정렬은 비교 정렬이 아니다.
[출처] 위키백과 - 계수 정렬
* 관련 문제
- [백준] 10989번: 수 정렬하기 3
댓글