본문 바로가기

Algorithm

 (5)
[알고리즘] 퀵 정렬 퀵 정렬 분할정복방법론 다른 완소와의 비교만으로 정렬을 수행하는 비교 정렬에 속함 최악 시간복잡도 - O(n^2), 평균 시간복잡도 - O(nlogn) 일반적으로 다른 O(nlogn)알고리즘에 비해 훨씬 빠르게 동작 피봇은 제일 오른쪽에 있는 값으로 설정 #include void quickSort(int *A, int p, int r) { int q; if (p < r) { q = partition(A, p, r);// 분할 quickSort(A, p, q - 1);// 왼쪽 부분 배열 정렬 quickSort(A, q + 1, r);// 오른쪽 부분 배열 정렬 } } int partition(int *A, int p, int r) { int i = p; int j = p; int tmp = 0; whil..
[알고리즘] 병합 정렬 https://www.youtube.com/watch?v=oHRChO--Hjs 이보다 친절한 수업은 없다 내가 짠 코드 #include #include void merge(int* a, int p, int q, int r); void mergeSort(int* a, int p, int r) { int q; if (p < r) { q = (p + r) / 2; mergeSort(a, p, q);// 전반부 mergeSort(a, q + 1, r);// 후반부 merge(a, p, q, r); } } void merge(int* a, int p, int q, int r) { int i; int p_idx = p; int q_idx = q + 1; int r_idx = r; int a_idx = p; int*..
[알고리즘] 삽입 정렬 삽입 정렬 : 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 C언어 구현 ver1. void insertionSort(int A[], int n) { int key, index; for (int i = 1; i = 0; j--) { if (A[j] > key) { A[j + 1] = A[j]; } else { index = j + 1; break; } } A[index] = key; } for (int i = 0; i < n; i++) { printf("%d ", A[i]); } } ver2. void insertionSort2(i..
[알고리즘] 선택 정렬 선택 정렬 : 각 루프마다 최대 원소를 찾고, 최대 원소와 맨 오른쪽 원소를 교환 -> 맨 오른쪽 원소를 제외한다. 하나의 원소만 남을 때까지 위의 루프를 반복. void selectionSort(int A[], int n) { int big;// 최댓값 인덱스 int temp; for (int i = n - 1; i > 0; i--) { big = i; for (int j = 1; j A[big]) { big = j; } } temp = A[i]; A[i] = A[big]; A[big] = temp; } for (int i = 0; i < n; i++) { printf("%d ", A[i]); } }
[알고리즘] 버블 정렬 버블 정렬 : 인접한 두 개의 원소를 비교하여 자리 교환하는 방식. 첫 번째 원소부터 마지막 원소까지 반복하면 가장 큰 원소가 마지막 자리에 온다. 시간복잡도 비교 횟수 최상, 평균, 최악 모두 일정. n-1, n-2, … , 2, 1 번 = n(n-1)/2 교환 횟수 입력 자료가 역순으로 정렬되어 있는 최악의 경우, 한 번 교환하기 위하여 3번의 이동(SWAP 함수의 작업)이 필요하므로 (비교 횟수 * 3) 번 = 3n(n-1)/2 입력 자료가 이미 정렬되어 있는 최상의 경우, 자료의 이동이 발생하지 않는다. O(n^2) C언어 구현 void bubbleSort(int A[], int n) { int temp; for (int i = n - 1; i >= 1; i--) { for (int j = 0; ..

티스토리툴바