반응형 정렬 썸네일형 리스트형 [C++] STL - sort STL에서 제공하는 sort 함수를 알아보자. 우선 sort 함수를 이용하기 위해서는 헤더 파일을 include 해주어야 한다. sort함수는 퀵정렬을 기반으로 하므로 O(nlogn)의 평균 시간 복잡도를 가진다. sort 함수의 형태는 아래와 같다. 1 2 3 4 5 template void sort(T start, T end); //default 오름차순 template void sort(T start, T end, Compare comp); //compare 함수 정의 가능 위처럼 정렬 기준이 되는 함수 (comp) 를 추가하지 않는다면 기본적으로 '오름차순'으로 정렬해준다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include using namespace std; .. 퀵 정렬 (Quick Sort) 퀵 정렬 (Quick Sort) 퀵 정렬 (Quick Sort)은 '찰스 앤터니 리차드 호어 (Charles Antony Richard Hoare)가 개발한 정렬 알고리즘이다. 다른 원소와의 비교만으로 정렬하는 "비교 정렬"에 속하며, 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 갖는다. 비교 정렬의 시간복잡도 하한선 : O(nlogn) / 퀵 정렬의 평균 시간복잡도 O(nlogn) (이름 자체에서도 빠르다는 것을 알려주고 있다...) 퀵 정렬 (Quick Sort) 알고리즘의 동작 원리 기준점(pivot)을 설정해 해당 기준으로 분할 i) 리스트 중에서 한 원소를 선택한다. 이렇게 고른 원소를 피벗(Pivot)이라고 한다. (일반적으로는 pivot을 리스트의 가장 앞의 원소 혹은 가.. 셸 정렬 (Shell Sort) 셸 정렬 (Shell Sort) 셸 정렬 (Shell Sort)에 대해서는 학교 수업시간에 학습한 개념이지만, 겉핥기 식으로만 학습하였고, 또 백준 알고리즘 문제를 해결하다보니 기존에 학습한 기본적인 정렬 (삽입, 선택, 버블)로는 대부분 시간초과로 통과하지 못하였기에 더 빠른 정렬을 이용하고자 다시 제대로 학습하게 되었다. 우선 셸 정렬 (Shell Sort)는 1959년, 이 방법을 고안한 "도널드 셸"의 이름을 따서 붙여졌고, 기존의 삽입 정렬(Insertion Sort)의 단점을 보완하고자 개발되었다. 1. 정렬이 하나도 되어 있지 않은 경우 매우 비효율적 2. 삽입되어야 할 위치가 멀리 있다면 원소들의 많은 이동을 해야만 삽입 가능 (삽입 정렬 Review) 주어진 배열에서 모든 요소를 앞에서부.. 이전 1 다음
