Programming/Algorithm15 c언어 퀵정렬 함수 퀵정렬(quick sort)의 시간복잡도는 nlogn으로 동작 원리는 기준키를 기준으로 작거나 같은 값을 지닌 데이터는 앞으로, 큰 값을 지닌 데이터는 뒤로 가도록 하여 작은 값을 갖는 데이터와 큰 값을 갖는 데이터로 분리해가며 정렬하는 방법이다. c언어로 구현하면 다음과 같다. void Swap(int arr[], int idx1, int idx2){int temp=arr[idx1];arr[idx1]=arr[idx2];arr[idx2]=temp;} int Partition(int arr[], int left, int right){int pivot = arr[left];int low = left+1;int high = right; while(low = arr[low] && low 2018. 4. 19. c언어 병합정렬 함수 병합정렬의 시간복잡도는 O(nlogn)이고 말 그대로 병합(합병)하면서 정렬이 된다. 합병 정렬은 다음과 같이 작동한다.리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. c언어로 구현하면 다음과 같다. void MergeTwoArea(int arr[], int left, int mid, int right){int fIdx = left;int rIdx = mid+1; int * sortArr = (int *)malloc(sizeof(int)*(right+1));int sIdx = left;.. 2018. 4. 19. c언어 삽입정렬 함수 삽입정렬(Insert Sort)이란 아직 정렬되지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입해 가며 정렬하는 방식이다삽입정렬의 시간복잡도는 O(n^2)이다. c언어로 구현하면 다음과 같다. void InsertSort(int arr[], int n){int insData;for(int i=1;i=0;j--){if(arr[j]>insData)arr[j+1]=arr[j];elsebreak;}arr[j+1]=insData;}} 2018. 4. 19. c언어 선택정렬 함수 선택정렬(selection sort)이란 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식이다.선택정렬의 시간복잡도는 O(n)이다. c언어로 구현하면 다음과 같다. void selsort(int arr[], int n){ int max, temp;for(int i=0;i 2018. 4. 19. 이전 1 2 3 4 다음