퀵소트 분석 - 스텝카운트, 빅오, 시간측정

소개글

퀵소트 분석 - 스텝카운트, 빅오, 시간측정에 대한 보고서 자료입니다.

목차

** Quick Sort의 코드
** Worst Case (최악의 경우)
** Worst Case 입력 배열 코드

1. Step Count
1.1 Code
1.2 Step Count Table (Worst Case)
* How-To
1.3 Result
1.4 Graph
1.5 Comment

2. Big O
2.1 Analysis on Worst Cases
2.2 Graph
2.3 Comment

3. Time Measurement
3.1 Code
3.2 Result
3.3 Graph
3.4 Comment

4. Summary

본문내용

** Quick Sort의 코드
inline void SWAP(int &a, int &b) { int tmp; tmp=a; a=b; b=tmp; }
void QuickSort(int *ar, int num) {
int left, right, key;
if (num <= 1) return; // 구간이 1이면 정렬 끝
key=ar[num-1]; // 피봇 결정 : 맨 끝 요소
for (left=0,right=num-2;;left++,right--) {
while (ar[left] < key) { left++; }
while (ar[right] > key) { right--; }
if (left >= right) break; // 좌우가 만나면 끝
SWAP(ar[left],ar[right]);
}
SWAP(ar[left],ar[num-1]); // 기준값과 i위치의 값 교환
QuickSort(ar,left); // 왼쪽 구간 정렬
QuickSort(ar+left+1,num-left-1); // 오른쪽 구간 정렬
}
** Worst Case (최악의 경우)
퀵 정렬의 최악의 경우는 입력배열 a의 원소들이 이미 오름차순(또는 내림차순)으로 정렬이 되어있는 경우이다. 만약 a가 이미 오름차순으로 정렬이 되어 있다면, 피봇 원소를 제외한 a의 모든 원소들이 피봇(배열 a의 끝 원소)보다 크지 않다. 따라서 가장 상위 단계에서의 분할(partition)이 이루어지고 나면, 피봇보다 오른쪽에 있게 되는 a의 원소는 하나도 없다. 마찬가지로 각 단계에서의 분할은 실제로 이루어지지 않는다.
** Worst Case 입력 배열 코드
int* dataArray(const int size){
int *a; int i; a=new int[size]; //공간 할당
for (i=0;i a[i]=i; //오름차순 소트된 상태
return a; //종료
}
1. Step Count
텍스트 23쪽에서 29쪽에 걸친 코드 예제들에 보면 비교, 할당, 실행문을 모두 고려하였다.

키워드

퀵소트,   스텝카운트,   빅오,   시간측정,   Quick Sort,   Step Count,   Big O,   Time Measurement