sort

1. Quick sort 분할 정복 테크닉을 사용한 매우 빠른 시간 복잡도를 가진 정렬 알고리즘이다. 정렬 로직 수행 간 초기 정렬 상태를 보장하지 않는 불안정 정렬이다. 추가 메모리 공간을 필요로 하지 않는다. 시간 복잡도 : O(NlogN) Quick sort의 로직 동작 과정 주어진 배열의 범위 내에서 하나의 값(Pivot)을 기준으로 정하고, pivot 왼쪽에는 pivot보다 작은 값들이 오른쪽에는 pivot보다 큰 값들이 오도록 정렬한다. pivot을 기준으로 나뉜 배열은 정렬된 순서는 보장하지 않기 때문에 각각 배열에서 새로운 pivot을 설정하여 다시 분할해서 재귀 호출 한다. 1,2번의 과정을 배열을 분할할 수 없을 때 까지 반복한다. Quick sort 장/단점 장점 - pivot과 거리..

1. Merge sort 분할 정복기법을 활용하여 정렬시키는 정렬 알고리즘이다. 재귀를 활용하여 큰 문제를 작은 문제로 쪼개서 풀이한 다음 return하면서 값을 합쳐서 도출해낸다. 정렬 로직 수행 간 초기 정렬상태를 보장하는 안정 정렬 방식이다 시간복잡도 : O(NlogN) // 공간복잡도 : O(N) Merge sort의 로직 동작 과정 1. 정렬할 배열의 처음과 끝 인덱스를 함수의 인자로 넘겨준다. 2. 처음과 끝 인덱스를 2로 나눈, 즉 mid = (left + right)/2. mid를 기준으로 재귀함수를 호출하여 범위가 1이 될 때 까지 나눠준다. 3. 정렬한 후 값을 복사해서 return 한다. mid를 기준으로 나눴을 때 왼쪽 부분의 범위 : left~mid mid를 기준으로 나눴을 때 오..

1-1. Bubble sort / 버블 정렬 인접한 두 원소를 비교해서 정렬이 잘못되어 있으면 서로 바꾸는 방식으로 정렬한다. 한번 큰 for문을 돌 때마다 탐색 범위 중에서 가장 큰 값을 가지는 원소가 뒤로 이동한다(오름차순 정렬일 경우) 돌 때마다 큰 숫자 하나는 무조건 정렬되기 때문에 (전체 원소의 갯수 - 큰 for문을 돈 횟수)만큼 돌아주면 된다. 시간복잡도 : O(N^2) 1-2. Code #include using namespace std; int n; vector arr; void Print() { for (int a : arr) { cout

오늘 백준에서 문제를 풀다가 vector정렬 시 내가 원하는 순서대로 커스텀해서 정렬하는 compare함수를 만들어서 사용하다가 Runtime Error를 만나서 구글링으로 알아낸 결과를 정리하려고 한다. 결론은 벡터를 정렬하기 위해 sort로 넘겨준 cmp 함수가 잘못돼서 발생한 문제였다. 1. C++ 공식 문서에서 알아보는 Sort C++ STL의 sort함수는 수학적으로 strict weak ordering 조건을 만족해야 한다. 1. cmp(a, a) == false 2. cmp(a, b) == true이면 cmp(b, a) == false. 두 비교체를 바꾸면 참/거짓 값도 변경되어야한다. 3. cmp(a, b) == true이고 cmp(b, c) == true이면 cmp(a, c) == tru..