소개글
과제할때 참고하시면 좋을것 같습니다
Quick sort에 대한 best case, worst case 시간 복잡도 분석 레포트입니다
각각 case에 대한 증명, 실제 코드 돌렸을때 측정된 시간그래프, 코드 증명 등 작성했습니다
과제 점수 모두 만점 받았습니다
코드(c++)와 레포트 모두 있습니다
(광운대 알고리즘 2차 과제)
목차
1. To show the results and graphs in Problems 2, 3, and 4, write your program with your comments. Explain your program at least four lines.
2. When you run your program for the following cases, show the step-by-step results. Explain the results at least four lines.
(a) For the worst-case time complexity of quicksort
(b) For the best-case time complexity of quicksort
(c) For the average-case time complexity of randomized quicksort
3 - (a) For the worst-case time complexity of quicksort
3 - (b) For the best-case time complexity of quicksort
3 - (c) For the average-case time complexity of randomized quicksort
4. When you run your program for the following cases, draw the graphs for the actual running time in your PC versus n. Write the basic information about the PC (e.g., CPU, RAM, OS). Explain the graphs at least four lines.
(a) For the worst-case time complexity of quicksort
(b) For the best-case time complexity of quicksort
(c) For the average-case time complexity of randomized quicksort
본문내용
1. To show the results and graphs in Problems 2, 3, and 4, write your program with your comments. Explain your program at least four lines.
void swap(int arr[ ], int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
int partition(int arr[ ], int p, int q) {
int pivot = arr[p]; //시작을 pivot으로
int i = p;
for (int j = p + 1; j <= q; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr, j, i);
}
}
swap(arr, p, i);
return i; // 중간위치 반환
void quick(int arr[ ], int p, int r) {
if (p < r) {
int q = partition(arr, p, r);
quick(arr, p, q - 1);
quick(arr, q + 1, r);
}
}
int main() {
int arr[ ] = { 3,2,4,5,2,1 };
int n = (sizeof(arr) / sizeof(int))-1;
quick(arr, 0, n);
for (int i = 0; i < n+1; i++) {
printf("%d", arr[i]);
}
printf("\n");
return 0;
}
Quick sort는 pivot값을 중심으로 subarray를 2개로 나눠서 진행하는 것이다. Pivot 값을 중심으로 왼쪽에 위치하는 값들은 pivot보다 작게, 오른쪽은 pivot보다 크게 정렬한다. 2개의 subarray를 재귀적으로 sort하는 것이다.
참고 자료
없음
압축파일 내 파일목록
알고리즘_2차_보고서.docx
코드/소스.cpp
압축파일 
