Category: Algorithm

0

BinarySearch

이진탐색데이터의 정렬이 선행되어야 한다. 시간복잡도는 O(log2n) 이다. BinarySearch.c 재귀적인 방법12345678910111213141516int ISearch(int ar[], int first, int last, int target){ int mid; if(first > last) return -1; // -1의

0

기수정렬 (RadixSort)

기수정렬버켓에 데이터를 작은 수 부터 넣고 빼내어 정렬하는 방식이다.기수정렬의 시간복잡도는 O(ln)이며 l은 버켓의 크기를 의미한다. red, why, few 정렬가능 - 버킷 3개 필요10,161,18,1 가능 - 버킷 3개 필요proffesor , red , why 불가능125 , -101, 167, -505 불가능 ##참고사항 1의자리 수 구하

0

퀵정렬 (QuickSort)

퀵정렬퀵 정렬 O(nlog2n)- 피벗을 정하여 분할하여 정복.. 피벗을 선택 할때 3개를 선택하여 평균치를 구하여 구하면 더 효율적으로 피벗을 정할 수 있다.피벗이 잘 선택될 경우 시간복잡도가 줄어든다. 최악의 경우 O(n^2)이 될 수 있다 (피벗값이 많이 안좋을 경우) O(nlog2n)의 시간복잡도를 갖는 다른 정렬 알고리즘 보다 평균적으로 빠르다.

0

병합정렬 (MergeSort)

병합정렬재귀적으로 분할하여 병합하는 방식으로 재귀적으로 모든 요소들을 쪼갠 후 합쳐나간다. 시간복잡도는 O(nlog2n))이다. MergeSort.c1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253void MergeTwoArea(in

0

힙정렬 (HeapSort)

힙 정렬힙을 만들어서 힙에 넣고 빼는것으로서 시간복잡도는 O(nlog2n) 이다. BubbleSort.c12345for(i=0;i<n;i++) HInsert(&heap,arr[i]);for(i=0;i<n;i++) arr[i]=HDelete(&heap); 참고 : 윤성우의 열혈 자료구조

0

삽입정렬 (InsertionSort)

삽입정렬1n까지 정렬해 나감 12 정렬 12묶음 3정렬 13묶음 4정렬첫 번째 데이터는 정렬이 되어있다고 봄. 그래서 i=0이아닌 1부터 시작.시간복잡도는 O(n^2) 이다. InsertionSort.c123456789101112for(i=1;i<n;i++){ insData=arr[i]; //정렬대상을 insData에 저장 for(j

0

선택정렬 (SelectionSort)

선택정렬오름차순일 경우 작은걸 맨앞에 넣고 그 다음 작은걸 두 번째 넣고 ..이 과정을 계속 반복한다. 시간복잡도는 O(n^2) 이다. SelectionSort.c12345678910for(i=0;i<n-1;i++){ maxIdx=i; for(j=i+1;j<n;j++) //최소값 탐색 { if(arr[i]<arr[maxI

0

거품정렬 (BubbleSort)

거품정렬거품정렬의 코드는 다음과 같다.시간복잡도는 O(n^2) 이다. BubbleSort.c12345678910for(i=0;i<n-1;i++){ for(j=0;j<(n-i)-1;j++) { if(arr[j]>arr[j+1]) { swap; } }} 참고 : 윤성우의 열혈 자료