[자료구조 복습 10] Quick Sort 퀵 정렬
일반 퀵소트 1. 파티션 함수를 통해 '피벗값'을 정한다. - 여기서 파티션 함수의 수행은 이러하다 1) 피벗값을 중심으로 왼쪽에는 피벗보다 작은 값을, 오른쪽에는 피벗보다 큰 값을 정렬한다. 2) 이를위해 left와 right이 배열을 따라 내려오면서, arr[left] > pivot 인경우와 arr[right] right 이 되는 경우, 즉 right과 left가 서로 교차하는 경우 루프를 멈추어준다. 4) 멈춘 곳에서 right과 우리가 정한 pivot의 자리를 바꾸어준다. 왜냐하면, pivot을 맨 첫번째 요소로 선택한다 했을때, pivot은 자신보다 작은 값과 바꾸어 져야하는데 pivot보다 작은 값을 마지막으로 가리키고 있는 것은 right이기 때문이다. 즉,pivot값 이렇게 위치해있으므로 ..
[자료구조 복습 9] Merge sort 합병정렬
머지소트 머지소트의 원리는 '분할정복'이다. 1) 배열을 더이상 쪼갤 수 없을 때까지 쪼갠다 2) 쪼개진 배열을 병합, 정렬한다. 가장처음엔 1개로 이루어진 배열 두개를 정렬하여 길이가 2인 배열을만들고, 이를 또 길이가 2인 배열 두개를 병합/정렬하여 길이가 4인 배열을 만든다..-> 배열이 모두 병합/정렬될 때까지 한다. 머지소트는 재귀의 깊이가 O(log2N)이고, 각 재귀 당 비교 및 스왑연산이 평균적으로 n번수행된다고 보면, 시간복잡도는 O(Nlog2N) 이 되겠다. 머지소트의 최대 단점이라하면, in place 알고리즘이 아니라는 것이다. 즉, 머지소트는 외부의 다른 배열을 만들고, 그 배열에서 정렬한 후, 정렬된 값을 다시 원래의 배열로 옮겨줘야한다. public class Sort { st..
#include using namespace std; int solve(int n) { int sum = 0; int min = 0; if (n == 4 || n == 7) return -1; while (1) { while (sum n) { sum -= 5; min--;} //만약 넘었다면 5kg을 빼준다. while (sum > N; cout 자루의 무게가 N과 같다면 ->종료 2)자루의 무게가 N보다 크다면 -> 자루의 무게가 N보다 작거나 같아질 때 까지 자루에서 5kg를 뺀다. 3)자루의 무게가 N보다 작거나 같을 때 까지 3kg를 추가한다. -> 자루의 뭬가 N과 같다면 -> 종료 -> 자루의 무게가 N보다 커지게 되었다면 앞에서부터 다시시작
1. 선택 소트 void selection_sort(int list[], int n) { int least=0, i=0, j=0; for (i = 0; i < n-1; i++) { least = i; for (j = i + 1; j < n; j++) { if (list[j] < list[least]) least = j; //가장 작은 값 찾기 } swap(list, i, least); } } 1) 인덱스 0 부터 n-1까지 차례대로 해당 인덱스에 올 i번째로 작은 값을 찾는다. 2) 이를 위해 내부 루프는 i보다 1큰 인덱스부터 시작하여 맨 끝 인덱스까지 본다. 선택 소트는 , 인접요소들 끼리 차례대로 정렬하는 것이 아니라, 앞의 인덱스에 있는 요소와 뒤의 랜덤의 요소 (가장 작은 값)을 정렬하는 것으로..