[Algorithm] Heap Sort(힙 정렬)
Code def create_heap(a): hsize=len(a)-1 for i in reversed(range(1, hsize)): downheap(i, hsize) def downheap(i, size): while(2*i=a[k]): break a[i], a[k] = a[k], a[i] i=k def heapsort(a): N=len(a)-1 for i in range(N): a[1], a[N] = a[N], a[1] downheap(1,N-1) N-=1 a = [-1, 10, 4, 5, 1, 8, 6, 2, 7, 9, 3] create_heap(a) print(a) heapsort(a) print(a) 정리 이진 트리 사용 1. max heap 만들기 2. 첫번째 노드와 마지막 노드의 위치를 바..
[Algorithm] Shell Sort(쉘 정렬)
Code def shell_sort(a): n=len(a) gap=n//2 while(gap>=1): if(gap%2==0): gap+=1 for i in range(gap,n): j=i while(j>=gap and a[j-gap]>a[j]): a[j-gap], a[j] = a[j], a[j-gap] j-=gap print(' Gap=', gap, a) gap=gap//2 a = [10, 4, 5, 1, 8, 6, 2, 7, 9, 3] print(a) shell_sort(a) print(a) 정리 삽입정렬에 전처리 과정을 추가한 알고리즘 gap을 사용해 정렬된 간격을 줄인다. 시간복잡도 최악의 경우 O(n^2) 평균의 경우 O(n^1.5) - Hibbard의 간격 특징 간격을 어떻게 설정하냐에 따라 수..
[Algorithm] Bubble Sort(버블 정렬)
Code Python def bubble_sort(a): for i in range(len(a)-1,0,-1): flag = False for j in range(i): if(a[j]>a[j+1]): a[j], a[j+1] = a[j+1], a[j] flag = True if not flag: break a = [10, 4, 5, 1, 8, 6, 2, 7, 9, 3] print(a) bubble_sort(a) print(a) C++ #include using namespace std; const int ARRAY_SIZE = 10; void bubble_sort(int a[]){ for(int i=ARRAY_SIZE-1; i>0; i--){ bool flag=false; for(int j=0; ja[j+..
[Algorithm] Insertion Sort(삽입 정렬)
Code Python def insertion_sort(a): for i in range(1, len(a)): for j in range(i, 0, -1): if a[j-1] > a[j]: a[j], a[j-1] = a[j-1], a[j] a = [10, 4, 5, 1, 8, 6, 2, 7, 9, 3] print(a) insertion_sort(a) print(a) def insertion_sort2(a): for i in range(1, len(a)): j=i while(a[j-1]>a[j] and j!=0): a[j], a[j-1] = a[j-1], a[j] j-=1 a = [10, 4, 5, 1, 8, 6, 2, 7, 9, 3] print(a) insertion_sort(a) print(a) C++..
[Algorithm] Selection Sort(선택 정렬)
Code python def selection_sort(a): for i in range(0, len(a)-1): minimum=i; for j in range(i, len(a)): if(a[minimum] > a[j]): minimum=j; a[i], a[minimum] = a[minimum], a[i] a = [10, 4, 5, 1, 8, 6, 2, 7, 9, 3] print(a) selection_sort(a) print(a) c++ #include using namespace std; const int ARRAY_SIZE = 10; void selection_sort(int a[]){ for(int i=0; i
