파티션: 1개의 글

알고리즘(Algorithm) 실습5

Posted by Patchman
2010.02.15 14:59 Univ Study/알고리즘과 실습


 

5-1. 다음에 주어진 프로그램을 참고해서 N(>1000) 개의 정수를 발생하여 heapsort()를 구현하여 실습하고, 키의 비교연산회수를 헤아려서 출력하고 비교하시오. 또한, 최악의 상태의 데이터로 실험할 때 키의 비교연산회수를 헤아려서 출력하고 비교하시오. 단, heapsort()를 구현하기 위해서 class PQ 에 정의된 연산 MakeHeap()은 별도로 구현하며, 필요한 사항은 임의로 정한다.

 

 

#include<stdio.h>

#include<stdlib.h>

 

#define MAX 1500

typedef int itemType;

 

int comparision = 0; // 비교연산회수카운터변수

 

// -- class 시작

class PQ

{

private:

 

itemType *a;

int N;

 

public:

 

PQ(int max)

{ a=new itemType[max]; N=max; }

 

~PQ()

{ delete a;}

 

void swap(int i, int j){

itemType t = a[i]; a[i] = a[j]; a[j] = t;

}

 

void worstcase(int j) // Worst Case 배열세팅

{

for(int i=N; i>=1; i--)

{

a[j] = i;

j++;

}

}

 

void randomcase() // Random Case 배열세팅

{

for(int i=0; i < N; i++)

a[i] = rand() % N+1;

}

 

void heapsort()

{

int i;

for(i=N/2; i>=1; i--) // 1차원 배열을 히프로 변환

makeHeap(a, i-1, N-1);

 

for(i=N-1; i>=1; i--)

{

swap(0, i); // 히프의 최대 값 제거

makeHeap(a, 0, i-1); // 남은 원소로 다시 히프변환

}

}

 

void makeHeap(itemType a[], int Root, int LastNode)

{

int Parent, LeftSon, RightSon, Son, RootValue;

Parent = Root;

RootValue = a[Root];

LeftSon = 2*Parent+1;

RightSon = LeftSon+1;

 

while(LeftSon <= LastNode){

 

// 조건문을 통하여 자식노드 중 더 큰 값을 Son에 저장한다

if(RightSon <= LastNode && a[LeftSon] < a[RightSon])

Son = RightSon;

else Son = LeftSon;

 

// 조건문을 통하여 노드가 자식을 뿌리로 하는 작은 히프에 // 아래로 내려가면서 제 자리를 찾게 한다.

if(RootValue < a[Son]){

/* Worstcase의 경우 히프정렬의 첫 번째 단계인 1차원 배열을 히프로 변환하는 과정에서 이미 뿌리노드가 자식노드보다 큰 값을 가지고 있기 때문에 위의 조건문이 실행되지 않는다.

WorstCase와 RandomCase의 비교연산회수 카운터에 차이가 나타나는 것은 바로 그 이유 때문이다.*/

comparision++;

 

 

a[Parent] = a[Son];

Parent = Son;

LeftSon = Parent*2+1;

RightSon = LeftSon+1;

}

else break

}

a[Parent] = RootValue;

}

}; // -- class 종료

 

void result() // 결과출력함수

{ printf("\n 비교연산 회수는 %d번 수행 되었습니다.\n\n", comparision);

comparision = 0; // 비교연산 카운터 변수 초기화

}

 

void main()

{

PQ pq(MAX); // PQ class 선언

 

printf("\n================= 5-1 HEAP SORT ==================\n");

 

pq.worstcase(0); // Worst Case 배열세팅

 

printf("\n------------------ Worst Case --------------------\n");

pq.heapsort(); // heapsort 호출

result(); // 비교연산회수출력

printf("--------------------------------------------------\n\n");

 

pq.randomcase(); // Random Case 배열세팅

 

printf("\n----------------- Random Case --------------------\n");

pq.heapsort(); // heapsort 호출

result(); // 비교연산회수출력

printf("--------------------------------------------------\n\n\n");

}

 

▣ 결과 출력

 







5-2. 다음에 주어진 프로그램을 참고해서 N(>1000) 개의 정수를 발생하여 mergesort()를 구현하고 실습하고, 키의 비교연산회수와 데이터 교환회수를 헤아려서 출력하고, 5-1의 결과요 비교하시오. 또한 최악의 상태의 데이터로 실험할 때 키의 비교연산회수를 헤아려서 출력하고 비교하시오. 단 merge()는 교과서를 참고해서 별도로 구현한다.

 

 

#include<stdio.h>

#include<stdlib.h>

 

#define MAX 1500

 

typedef int itemType;

 

itemType b[MAX];

int data_swap = 0;

int comparision = 0;

 

inline void swap(itemType a[], int i, int j){

itemType t = a[i]; a[i] = a[j]; a[j] = t;

};

 

void makeHeap(itemType a[], int Root, int LastNode)

{

int Parent, LeftSon, RightSon, Son, RootValue;

Parent = Root;

RootValue = a[Root];

LeftSon = 2*Parent+1;

RightSon = LeftSon+1;

 

while(LeftSon <= LastNode){

if(RightSon <= LastNode && a[LeftSon] < a[RightSon])

{ Son = RightSon; comparision++; }

else {Son = LeftSon; comparision++;}

if(RootValue < a[Son]){

comparision++;

a[Parent] = a[Son];

Parent = Son;

LeftSon = Parent*2+1;

RightSon = LeftSon+1;

}

else break

}

a[Parent] = RootValue;

}

void
heapsort(itemType a[], int N)

{

 

int i;

for(i=N/2; i>=1; i--)

makeHeap(a, i-1, N-1);

for(i=N-1; i>=1; i--)

{

swap(a, 0, i);

makeHeap(a, 0, i-1);

}

}

 

void merge(int a[], int low, int mid, int high)

{

 

int i, leftptr, rightptr, bufptr;

leftptr = low; rightptr = mid+1; bufptr = low;

 

// 합병이 진행되고 있는 두 부분배열 모두에 아직 키가 남아있을 때 이들을 합병

while(leftptr <= mid && rightptr <= high)

if(a[leftptr] < a[rightptr])

{ b[bufptr++] = a[leftptr++]; data_swap++; }

else {b[bufptr++] = a[rightptr++]; data_swap++;}

 

// 두 부분배열 중 한 개의 배열에만 키가 남았을 때 이 키들을 배열 b의

// 합병된 원소들 뒤에 그대로 복사

if(leftptr > mid)

for(i = rightptr; i<= high; i++)

{ b[bufptr++] = a[i]; comparision++; }

else

for(i=leftptr; i<=mid; i++)

{ b[bufptr++] = a[i]; comparision++; }

 

// 합병이 끝나면 b에 있는 정렬된 키들을 a에 옮긴다

for(i = low; i <=high; i++)

a[i] = b[i];

}

 

void mergesort(itemType a[], int l, int r)

{

int mid;

 

if(l<r)

{

mid = (l+r)/2; // 배열의 원소가 둘 이상이면

 

mergesort(a, l, mid); // 분할된 왼쪽 부분 배열에 대하여

// mergesort 순환호출

 

 

mergesort(a, mid+1, r); // 분할된 오른쪽 부분 배열에 대하여

// mergesort 순환호출

 

merge(a, l, mid, r); // 정렬된 왼쪽과 오른쪽을 merge

}

}

 

void result() // 결과출력함수

{

printf("\n 비교연산회수는 %d번수행되었습니다.\n", comparision);

 

if(data_swap != 0)

printf(" 데이터교환회수는 %d번수행되었습니다.\n", data_swap);

 

comparision = 0; // 비교연산카운터변수초기화

data_swap = 0; // 자료이동카운터변수초기화

}

 

void main()

{

itemType heap[MAX];

itemType merge[MAX];

int worst_num = MAX;

 

printf("\n================= 5-2 MERGE SORT =================\n");

//////////////// Random Case array & Result /////////////////////

for(int i=0; i < MAX; i++)

heap[i] = merge[i] = rand() % MAX+1;

printf("\n----------------- Random Case --------------------\n");

printf(" [Heap sort]");

heapsort(heap, MAX);

result();

 

printf("\n [Merge sort]");

mergesort(merge, 0, MAX-1);

result();

printf("\n--------------------------------------------------\n");

/////////////////////////////////////////////////////////////////

 

//////////////// Worst Case array & Result //////////////////////

for(int i=0; i < MAX; i++){

heap[i] = merge[i] = worst_num;

worst_num--;

}

printf("\n----------------- Worst Case ---------------------\n");

printf(" [Heap sort]");

heapsort(heap, MAX);

result();

 

printf("\n [Merge sort]");

 

mergesort(merge, 0, MAX-1);

result();

printf("\n--------------------------------------------------\n\n\n");

/////////////////////////////////////////////////////////////////

}

 

▣ 결과 출력

 

 

 

 

 

5-3. n(>1000)개의 양의 정수자료를 랜덤함수로서 발생하여, partition() 연산을 사용하여 k번째 원소를 찾는 Select(a, l, r, k)을 사용해서 최소치, 최대치 및 중앙치를 찾고 비교연산 회수를 각각 출력하시오.

 

#include<iostream>

#include<stdlib.h>

using namespace std;

 

#define MAX 1500

 

typedef int itemType;

 

int data_swap = 0;

int comparision = 0;

 

inline void swap(itemType a[], int i, int j){

data_swap++;

itemType t = a[i]; a[i] = a[j]; a[j] = t;

};

 

int partition(int a[], int l, int r)

{

int i,j;

itemType v;

if(r>l)

{

// 정렬한 리스트의 가장왼쪽 데이터를 피벗으로 선택

v=a[l];i=l;j=r+1;

 

for(;;)

{

while(a[++i]<v) comparision++;

while(a[--j]>v) comparision++;

 

if(i>=j) break // low와 high가 교차하지 않았으면

swap(a,i,j); // left, right swap

}

}

 

swap(a,j,l); // 피벗을중앙에위치시킨다

return j;

 

}

 

 

int select(int a[], int l, int r, int k)

{

// ㅣ:배열의최소치, r:배열의최대치, k:찾는수의위치

int j;

 

 

if(r>l)

{

// 퀵 정렬의 Partition 함수를 이용해 분할정복 방법을 적용

j=partition(a,l,r);

if(j>l+k-1) return select(a,l,j-1,k);

else if(j<l+k-1) return select(a,j+1,r,k-j+l-1);

else return a[j];

}

return a[l];

}

 

void result() // 결과출력함수

{

cout<<"\n비교연산회수는"<< comparision <<"번수행되었습니다.\n\n"

cout<<"자료이동회수는"<< data_swap <<"번수행되었습니다.\n\n"

comparision = 0; // 비교연산 카운터 변수 초기화

data_swap = 0; // 자료이동 카운터 변수 초기화

}

 

void main()

{

int a[MAX];

for(int i=0;i<MAX;i++)

a[i]=rand()%MAX+1;

 

cout << "\n============= 5-3 Select,Partition ============\n" << endl;

 

cout << "------------------- 최소치--------------------\n" << endl;

cout << "최소치값은: " << select(a,0,MAX-1,1) << endl;

result();

cout << "-----------------------------------------------\n" << endl;

cout << "------------------- 중앙치--------------------\n" << endl;

cout << "중앙치값은: " << select(a,0,MAX-1,MAX/2) << endl;

result();

cout << "-----------------------------------------------\n" << endl;

cout << "------------------- 최대치--------------------\n" << endl;

cout << "최대치값은: " << select(a,0,MAX-1,MAX) << endl;

result();

cout << "-----------------------------------------------\n\n\n" << endl;

}


 

▣ 결과 출력

 

 

 

'Univ Study > 알고리즘과 실습' 카테고리의 다른 글

알고리즘(Algorithm) 실습7  (0) 2010.02.15
알고리즘(Algorithm) 실습6  (0) 2010.02.15
알고리즘(Algorithm) 실습5  (0) 2010.02.15
알고리즘(Algorithm) 실습4  (0) 2010.02.15
알고리즘(Algorithm) 실습3  (0) 2010.02.15
알고리즘(Algorithm) 실습2  (0) 2010.02.15