본문 바로가기
728x90

분류 전체보기247

힙 정렬(Heap Sort) 힙(Heap) 부모의 값이 자식의 값보다 항상 크다(또는 작다)는 조건을 만족하는 완전이진트리 트리의 레벨 순서대로 배열에 저장하면 a[i] 노드에 대하여 다음과 같은 관계가 성립: 1. 부모는 a[(i-1) / 2] 2. 왼쪽 자식은 a[i*2 +1] 3. 오른쪽 자식은 a[i*2 +2] 힙 정렬(Heap sort) 가장 큰 값이 루트에 위치하는 특징을 이용하는 정렬 알고리즘 -> 힙에서 루트를 없앤 다음 다시 힙을 만들어야 함 1. 마지막 요소를 루트와 바꿈 2. 큰 값을 가지는 자식과 위치를 바꾸며 내려가는 작업을 정렬되지 않은 부분에서 반복. 자식이 더 작거나 leaf에 도달하면 종료. static void downheap(int a[], int left, int right) { //힙을 만드는 .. 2023. 9. 22.
병합 정렬(Merge Sort) 병합 정렬(Merge sort) 배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 후 둘을 병합하여 정렬하는 알고리즘 배열의 요소 개수가 2개 이상인 경우: 1. 앞부분을 병합 정렬로 정렬 2. 뒷부분을 병합 정렬로 정렬 3. 배열의 앞부분과 뒷부분을 병합 (두 배열의 요소를 하나씩 선택하여 비교한 후 작은 값을 대입) #include #include static int* buff; //작업용 배열 static void __mergesort(int a[], int left, int right) { if (left < right) { int center = (left + right) / 2; int p = 0; int i; int j = 0; int k = left; __mergesort(a, left, ce.. 2023. 9. 22.
퀵 정렬(Quick Sort) 퀵 정렬(Quick Sort) 기준이 되는 피벗(pivot)을 기준으로 배열을 두 그룹으로 나눈 후 피벗을 기준으로 더 작은 값은 왼쪽으로, 큰 값은 오른쪽을 옮김. 1. 한 배열의 왼쪽 끝 요소의 인덱스를 pl, 오른쪽 끝 요소의 인덱스를 pr이라고 할 때 2. a[pl] >= x인 pl과 a[pr] x) pr--; if (pl name, y->name); } 2023. 9. 22.
삽입 정렬(Insertion Sort) 삽입 정렬(Insertion Sort) i (0 tmp; j--) { a[j] = a[j - 1]; // tmp가 더 작으므로 정렬된 부분을 한 칸씩 뒤로 미룸 } a[j] = tmp; // 찾은 자리 j에 tmp를 넣음 } } 시간 복잡도: O(n^2) - avg, worst (best는 O(n)) 2023. 9. 22.
선택 정렬(Selection Sort) 선택 정렬(Selection sort) 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘 1. 정렬되지 않은 부분에서 가장 작은 키의 값을 선택 2. 아직 정렬하지 않은 부분의 첫 번째 요소와 교환 이 과정을 n-1회 반복 void selection(int a[], int n) { int i, j; for (i = 0; i < n - 1; i++) { int min = i; for (j = i + 1; j < n; j++) if (a[j] < a[min]) min = j; swap(a[i], a[min]); } } 시간복잡도: O(n^2) - best, avg, worst 모두 동일 2023. 9. 22.
버블 정렬(Bubble Sort) 버블 정렬(Bubble sort) 서로 인접한 두 원소를 비교하여 정렬되어 있지 않은 경우에 교환하는 정렬 알고리즘 *일련의 비교 과정을 패스(pass)라고 함 비교 횟수: (n-1) + (n-2) + ... + 1 = n(n-1)/2 이므로 시간복잡도 O(n^2) (best, avg, worst 모두) #include #include #define swap(x, y) do {int t = x; x = y; y = t;} while(0) void bubble(int a[], int n) { int i, j; for (i = n-1; i > 0; i--) { for (j = 0; j a[j + 1]) swap(a[j], a[j + 1]); } } } int main.. 2023. 9. 22.

티스토리툴바