힙정렬(heap sort) 이진 트리 : 모든 노드의 자식 노드가 2개 이하인 트리구조 완전 이진트리 힙정렬 #include void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } void heapify(int arr[], int here, int size) { int left = here * 2 + 1; int right = here * 2 + 2; int max=here; if (left arr[max]) max = left; if (right arr[max]) max = right; if (max != here) { swap(&arr[here], &arr[max]); heapify(arr, max, .. 2021. 1. 13. 병합정렬(Merge Sort) 존 폰 노이만(John von Neumann) 이 만든 분할 정복 알고리즘 Devide, Conquer, Combine 1. 분할(홀수일경우) 2. 병합 (Merge) 분할(짝수일경우) #include #define SIZE 8 int tmp[SIZE]; void merge(int arr[], int left, int right) { int L, R, k, a; int mid = (left + right) / 2; L = left; R = mid + 1; k = left; while (L 2021. 1. 13. 쉘 정렬(Shell sort) # include # define MAX_SIZE 10 void inc_insertion_sort(int list[], int first, int last, int gap){ int i, j, key; for(i=first+gap; i=first && list[j]>key; j=j-gap){ list[j+gap] = list[j]; } list[j+gap] = key; } } void shell_sort(int list[], int n){ int i, gap; for(gap=n/2; gap>0; gap=gap/2){ if((gap%2) == 0)( gap++; ) for(i=0; i 2020. 11. 10. 퀵정렬(Quick Sort) Name Best Avg Worst Run-time (int 60,000) sec 버블정렬 n^2 n^2 n^2 22.89 선택정렬 n^2 n^2 n^2 10.84 삽입정렬 n n^2 n^2 7.43 셀정렬 n n^1.5 n^2 0.05 퀵정렬 nlog₂n nlog₂n n^2 0.01 힙정렬 nlog₂n nlog₂n nlog₂n 0.03 병합정렬 nlog₂n nlog₂n nlog₂n 0.02 #include #define MAX_SIZE 9 #define SWAP(x,y, temp)((temp)=(x),(x)=(y),(y)=(temp)) int partition(int list[], int left, int right) { int pivot, temp; int low, high; low = left; h.. 2020. 11. 5. 삽입정렬(insertion sort) Name Best Avg Worst Run-time (int 60,000) sec 버블정렬 n^2 n^2 n^2 22.89 선택정렬 n^2 n^2 n^2 10.84 삽입정렬 n n^2 n^2 7.43 셀정렬 n n^1.5 n^2 0.05 퀵정렬 nlog₂n nlog₂n n^2 0.01 힙정렬 nlog₂n nlog₂n nlog₂n 0.03 병합정렬 nlog₂n nlog₂n nlog₂n 0.02 #include #define MAX_SIZE 5 void insertion_sort(int list[], int n) { int i, j, key; for (i = 1; i = 0 && list[j] > key; j--) { list.. 2020. 10. 21. 선택정렬(selection sort) 오름차순을 기준으로 정렬한다 선택정렬(selection sort)의 시간 복잡도 T(n)=(n-1)+(n-2)+...2+1=n(n-1/2=O(n^2) Name Best Avg Worst Run-time (int 60,000) sec 버블정렬 n^2 n^2 n^2 22.89 선택정렬 n^2 n^2 n^2 10.84 삽입정렬 n n^2 n^2 7.43 셀정렬 n n^1.5 n^2 0.05 퀵정렬 nlog₂n nlog₂n n^2 0.01 힙정렬 nlog₂n nlog₂n nlog₂n 0.03 병합정렬 nlog₂n nlog₂n nlog₂n 0.02 #include #define SWAP(x,y,temp)((temp=(x),(x)=(y),(y)=(temp))) #define MAX_SIZE 5 void select.. 2020. 9. 18. 버블정렬 (Bubble Sort) 옆에 있는 값과 비교해서 더 작은 값을 앞으로 보내자 버블정렬 또한 선택정렬과 같이 비효율적인 정렬 방법중 하나다. 버블정렬이 선택정렬보다 연산량이 많다 버블정렬(Bubble sort)시간복잡도 n-1, n-2, ..... , 2, 1 = n(n-1)/2 T(n)=O(n^2) 정렬 알고리즘 시간 복잡도 Name Best Avg Worst Run-time (int 60,000) sec 버블정렬 n^2 n^2 n^2 22.89 선택정렬 n^2 n^2 n^2 10.84 삽입정렬 n n^2 n^2 7.43 셀정렬 n n^1.5 n^2 0.05 퀵정렬 nlog₂n nlog₂n n^2 0.01 힙정렬 nlog₂n nlog₂n nlog₂n 0.03 병합정렬 nlog₂n nlog₂n nlog₂n 0.02 #includ.. 2020. 9. 17. 알고리즘 algorithm 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것, 계산을 실행하기 위한 단계적 절차 수학과 컴퓨터과학, 언어학 또는 엮인 분야에서 어떠한 문제를 풀어내기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것, 계산을 실행하기 위한 단계적 절차를 의미한다. 즉, 문제풀이에 필요한 계산절차 또는 처리과정의 순서를 뜻한다. 프로그램명령어의 집합을 의미 2020. 9. 17. 이전 1 다음
