[Do it!] 자료구조와 함께 배우는 알고리즘 입문(C언어 편)

에라토스테네스의 체 --> memoizationsquare root 까지만 점검.

결과

출력

정렬 되었는지 확인기본 Bubble정렬중간에 정렬이 끝났으면 종료정렬된 부분은 다음에 생략(왼쪽 끝)정렬된 부분은 다음에 생략(왼쪽 끝, 오른쪽 끝)1, 2, 3은 오차범위내에서 순서가 순위가 변하지만 4는 항상 더 빠르다.

보초법추가로 확실한 성능향상이 있다.

기본 쉘 정렬 (Group끼리 섞일 수 있게 gap을 홀수로 고정)코드 가독성 (for문 한개 줄임)gap = 3n+1 꼴일때 최대 효율(Group끼리 섞임)

Recursion

using namespace std;bool is_sorted(int arr\[], const int N) { for (int i = 1; i < N; i++) if (arri - 1 > arri) return false;