반응형 전체 글110 정렬 알고리즘 - 퀵 정렬(Quick Sort) 퀵 정렬(Quick Sort) 퀵 정렬 이란? - 분할 정복(divide and conquer) 알고리즘 디지인 기법에 근거하여 만들어진 정렬 방법. - 정렬 대상을 반씩 줄여가며 정렬한다. - 피벗을 기준으로 정렬한다. - 피벗을 어떤 값으로 설정하냐에 따라 속도가 달라진다. (피벗이 중간에 해당하는 값일 경우 정렬 대상을 균등하게 나눈다) - 정렬대상에서 세 개의 데이터를 추출하고, 그 중 중간 값에 해당하는 것을 피벗으로 삼는다. - 퀵 정렬은 O(nlogn)의 시작복잡도를 가진다.(최선의 경우) // 최악의 경우 O($n^2$) 퀵 정렬 예시(오름차순) - left와 right가 교차되는 상황 발생하면 더 이상 정렬할 대상이 없다는 것이다. 퀵 정렬 코드(C++) #include #include .. 2020. 6. 16. 정렬 알고리즘 - 병합 정렬(Merge Sort) 병합 정렬(Merge Sort) 병합 정렬이란? - 분할 정복(divide and conquer) 알고리즘 디지인 기법에 근거하여 만들어진 정렬 방법. - 데이터가 1개 남을 때까지 분할하고, 분할된 데이터를 정렬한 후 다시 결합한다. - 실제 정렬은 분할하는 과정이 아니라, 병합하는 과정에서 이루어진다. - 병합 정렬은 O(nlogn)의 시간복잡도를 가진다. - 병합 정렬은 임시 메모리가 필요하다는 단점이 존재한다. 병합 정렬 예시(오름차순) 병합 정렬의 정렬&결합 과정 - 결합하는 두 데이터는 모두 정렬되어 있다. - 처음부터 하나씩 비교하여 임의의 데이터 공간에 저장한다. 병합 정렬 코드(C++) #include #include using namespace std; void MergeData(vec.. 2020. 6. 16. 정렬 알고리즘 - 삽입 정렬(Insertion Sort) 삽입 정렬(Insertion Sort) 삽입 정렬 이란? - 이미 정렬되어 있는 것에 하나씩 추가해 정렬하는 방법 - 대상이 이미 정렬되어 있다면 매우 빠른 속도로 동작한다. - N개의 데이터가 주어졌을 때 O($N^2$)의 시간복잡도를 가진다. 삽입 정렬 예시 삽입 정렬 코드(C++) #include #include using namespace std; void insertionSort(vector &vec) { int i, j, data; for (i = 1; i = 0; j--) { if (vec[j] > data) { vec[j + 1] = vec[j]; } else break; } vec[j + 1.. 2020. 6. 14. [C++/STL] Algorithm 0. C++ STL - Algorithm - 헤더 선언 필요( #include ) 1. 정렬 정렬 함수 - 일반적인 정렬 함수 - O(nlogn) 보장 - sort(원소 시작 위치 반복자 ,원소 마지막 다음 위치 반복자 , 비교함수) - 예시(오름차순) #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); vector vec{ 5,6,8,12,3,9,1,30 }; cout 2020. 6. 14. 이전 1 ··· 22 23 24 25 26 27 28 다음 반응형
