기록장

Merge Sort 여러 부분 집합으로 분할하고, 정렬한 후, 병합하는 방식 종류 2-way: 2개의 정렬된 자료 집합을 하나의 집합으로 병합 n-way: n개의 정렬된 자료 집합을 하나의 집합으로 병합 void merge(int arr[], int begin, int middle, int end) { int *sorted = new int[end - begin + 1]; int i = 0; int left = begin; int right = middle + 1; while(left

Quick Sort 배열을 부분 집합을 나눈 후, 특정 키 값 (pivot)을 정해서 피봇보다 작은 값은 피봇의 왼쪽 집합으로, 큰 값은 오른쪽 집합으로 교환하며 정렬해가는 방식 void QuickSort(int arr[], int begin, int end) { if(begin >= end) return; int pivot = (begin + end) / 2; int left = begin, right = end; while(left arr[pivot]) right--; if(left 0 && arr[pos/2] > value; pos /= 2) arr[pos] = arr[pos/2]; arr[pos] = value; } void print() { while(count > 0) cout

Bubble sort 인접한 두 개의 원소를 비교하며 자리를 바꾸는 방식 void bubbleSort(int arr[], int length) { for(int i = 0; i arr[j+1]) swap(&arr[j], &arr[j+1]); } } Selection Sort 가장 작은 원소를 찾아서 맨 앞부터 자리를 바꾸는 방식 void selectionSort(int arr[], int length) { for(int i = 0; i ..

실행 방법에 따른 분류 비교식 정렬: 두 값을 비교하여 정렬하는 방식 분산식 정렬: 하나의 키 값을 잡아서 부분집합으로 나누어서 정렬함으로써 전체를 정렬하는 방식 정렬 장소에 따른 분류 내부 정렬 정렬할 자료를 메인 메모리에 올려서 정렬하는 방식. 용량이 제한적이다 교환 방식 (Selection, Bubble, Quick), 삽입 방식 (Insertion, Shell), 병합 방식 (2-way, n-way), 분배 방식 (radix), 선택 방식 (heap, tree) 등이 있다 외부 정렬 정렬할 자료를 보조 기억장치에서 정렬하는 방식. 속도가 떨어지지만 대용량이 가능하다 병합 방식 (2-way, n-way) 이 있다 Big O O(n²): Bubble, Selection, Insertion, Shell..