Sort algorithm

Comb Sort란? Bubble Sort에서 거북이(turtle) 데이터를 줄이고자 고안해낸 알고리즘입니다. 토끼(rabbit) 데이터는 bubble sort에서 문제가 되지 않습니다. Not stable하면서 In-place한 Algorithm입니다. Bubble Sort에서는 인접한 두 데이터의 크기를 비교합니다. 비교하는 두 데이터의 거리를 gap이라 합니다. Bubble sort에서는 바로 인접한 데이터를 비교하기때문에 gap이 1입니다. Comb sort gap의 크기를 1보다 크게합니다. bubble sort의 각 pass가 진행됨에 따라 gap의 크기를 줄여갑니다. "shrink factor"를 k 만큼 줄여갑니다 gap의 크기 : $$ [\frac{n}{k},\frac{n}{k^2}, \..

Selection Sort란? 기본 아이디어 정렬 중간 과정에서 데이터가 두 부분으로 나누어집니다. 왼쪽 데이터는 정렬이 된 데이터 오른쪽 데이터는 정렬이 되지 않은 데이터 Not stable한 알고리즘이면서 In place 알고리즘입니다. 오른쪽 데이터에서 제일 작은 데이터를 검색하여 선택하고 오른쪽 데이터의 제일 앞 숫자를 그 숫자랑 교환합니다. 정렬 과정 Selection Sort 코드 #include #include #define MAX_SIZE 1000 using namespace std; void selectionSort(int a[], int n); int main() { int numTestCases; scanf("%d", &numTestCases); for (int i = 0; i < n..

Bubble Sort Algorithm 정렬 알고리즘 중 기본적인 알고리즘 중 하나로 인접한 두 숫자를 비교하여 두 수의 정렬 순서가 맞지 않은 경우에 swap을 하는 알고리즘입니다. 마치 깊은 물속의 큰 물방울이 표면으로 떠 오르는 것과 같이 큰 데이터들이 배열의 왼쪽에서 오른쪽으로 이동하기 대문에 bubble sort라고 부른다고 합니다. 해당 알고리즘은 stable한 Algorithm이면서, In-Place한 Algorithm입니다. Stable: 정렬 이후 입력된 순서 그래도 유지가 되는가? In-place: 데이터를 저장하는 메모리 이외는 상수 크기의 메모리만 필요하는가? 평균적인 시간 복잡도는 O(n^2)입니다. Pass 맨 왼쪽 인접한 두 숫자를 비교하기 시작합니다 맨 끝 인접한 두 숫자를 ..