<ALGORITHM>/SUMMARIZE7 6. STD::SORT STD::SORT ▼ 관련 개념 Loop & Template & STD ▼ 구현 코드 #include template bool Compare(T lhs, T rhs) { return (lhs < rhs); } int main() { std::array iArr = { 5, 4, 3, 2, 1 }; std::sort(iArr.begin(), iArr.end(), Compare); return (0); } CPP A.11에서 사용할 수 있는 std::sort를 사용한 방법이다. A.11를 지원하는 CPP 컴파일러라면 대부분의 경우 프로그래머가 직접 구현한 정렬 함수에 비해서 높은 성능을 낸다. (한가지 정렬법으로 구현된게 아니라 경우에 따라 최적의 방법으로 바꾸는 방식으로 되어있다.) 다른 알고리즘 문제를 .. 2021. 1. 27. 5. 삽입 정렬(Insertion Sort) 삽입 정렬의 개념 차례로 하나씩 꺼내서 앞에 있는 값들과 크기를 비교한 뒤 바꿔서 삽입한다고 해서 삽입 정렬이라 부른다. ▼ 삽입 정렬 알고리즘 도식화 그림을 보면 교환이라기 보다는 옆으로 꺼내두는 모습을 볼 수 있는데 삽입 정렬의 구현 방법은 이동(Shift) 방식과 교환(Swap) 방식 둘 다 가능하다. 삽입 정렬의 성능[O(n²)] 정렬할 자료의 수의 제곱에 비례하여 늘어난다. 삽입 정렬은 범위를 늘려가면서 비교하는 방식 때문에 배열이 길어지면 길어질 수록 효율이 떨어진다. 반대로 말하면 배열이 짧으면 짧을수록 속도가 빠르다. 고성능 정렬 라이브러리에서는 데이터의 양이 적을 때엔 삽입 정렬로 전환하여 속도를 올리기도 한다. C99 ▼ 관련 개념 Condition & Loop & Pointer & C.. 2021. 1. 18. 4. 선택 정렬(Selection Sort) 선택 정렬의 개념 한 위치씩 선택해서 순차적으로 작은 값들을 찾아서 선택 정렬이라고 한다. ▼ 선택 정렬 알고리즘 도식화 선택 정렬은 최소값을 찾은 다음 교환하기 때문에 교환 함수 호출을 최소화할 수 있다. 선택 정렬의 성능[O(n²)] 정렬할 자료의 수의 제곱에 비례하여 늘어난다. C99 ▼ 관련 개념 Loop & Pointer & Call By Address ▼ 구현 코드 int Compare(int lhs, int rhs) { return (lhs - rhs); } void Swap(int* lhs, int* rhs) { int _temp = *lhs; *lhs = *rhs; *rhs = _temp; } void SelectionSort(int arr[], int length) { int min; .. 2021. 1. 18. 3. 거품 정렬(Bubble Sort) 거품 정렬의 개념 거품 정렬은 단순히 처음부터 끝까지 두 개의 값을 서로 비교해가면서 정렬한다. ▼ 비교하는 모습이 거품과 같다. 두 값을 비교해서 교환하는 것이 마치 거품이 일어나는 모습과 비슷하다고 해서 거품 정렬이라 부른다. ▼ 거품 정렬 알고리즘 도식화 거품 정렬은 한번 외부 순환문을 돌 때마다 목표 방향 끝자리는 최댓값 혹은 최솟값이 정렬된다. 그렇기 때문에 내부 순환 문의 목푯값이 하나씩 줄어드는 것이 알고리즘의 핵심이다. 거품 정렬의 성능[O(n²)] 정렬할 자료의 수의 제곱에 비례하여 늘어난다. 순차 정렬과 마찬가지로 단순 무식한 방법인 만큼 거품 정렬은 거의 모든 경우에서 최악의 성능을 보여준다. 그리고 정렬이 이미 완료된 경우엔 최선의 성능을 보이는 것도 순차 정렬과 같다. 순차 정렬과.. 2021. 1. 18. 이전 1 2 다음
