알고리즘(Algorithm) 실습4
N(>1000)개의 양의 정수자료에 대한 worst case, best case 및 랜덤 data(rand()함수로 발생)로서 내부정렬하고자 한다.
4-1. Insertion Sort 알고리즘을 구현하고, 비교연산과 자료이동 연산회수를 count 해서 출력하시오
#include <iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
#define MAX 1500
typedef int itemType;
int data_swap = 0;
int comparision = 0;
void insertion(itemType a[], int N) // 삽입 정렬
{
int i, j;
itemType v;
for(i=2; i<=N; i++){
comparision++; // 비교연산 카운터 증가
v = a[i]; //현재 삽입될 숫자를 v변수로 복사
j=i;
while(a[j-1] > v){ // 이전배열의 값이 키 값보다 크면
data_swap++; // 자료이동 카운터 증가
a[j] = a[j-1]; // 데이터 이동
j--; // j 감소
}
a[j] = v;
}
};
void result() // 결과 출력 함수
{
cout<<"\n비교연산 회수는 "<< comparision <<"번 수행 되었습니다.\n";
cout<<"자료이동 회수는 "<< data_swap <<"번 수행 되었습니다.\n\n";
comparision = 0; // 비교연산 카운터 변수 초기화
data_swap = 0; // 자료이동 카운터 변수 초기화
}
void main()
{
// 삽입,쉘 정렬에 사용되는 배열
itemType a[MAX+1];
a[0] = -1; // 첫번째 배열에 더미값 초기화
int j=1; // Worst Case 배열을 위한 변수
printf("\nInserttion Sort : %d개의 양의정수 Case 비교\n\n", MAX);
//////////////// Best Case array & Result //////////////////
for(int i=1; i<=MAX; i++) a[i] = i;
printf("--------------------------------------------------");
insertion(a, MAX);
cout << "\n--- Best Case ---";
result();
////////////////////////////////////////////////////////////
//////////////// Worst Case array & Result /////////////////
for(int i=MAX; i>=1; i--){
a[j] = i;
j++;
}
printf("--------------------------------------------------");
insertion(a, MAX);
cout << "\n--- Worst Case ---";
result();
////////////////////////////////////////////////////////////
//////////////// Random Case array & Result ////////////////
for(int i=1; i<=MAX; i++)a[i] = rand() % MAX+1;
printf("--------------------------------------------------");
insertion(a, MAX);
cout << "\n--- Random Case ---";
result();
////////////////////////////////////////////////////////////
printf("--------------------------------------------------\n\n");
}
▣ 결과 출력
4-2. Quik Sort 알고리즘을 구현하고, 비교연산과자료교환 연산회수를 출력하시오.
#include<stdio.h>
#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){ // partition함수에서 호출되는 swap
data_swap++; // 자료이동 카운터 증가
itemType t = a[i]; a[i] = a[j]; a[j] = t; // data swap
};
int partition(itemType a[], int l, int r) // quicksort함수에서 호출되는 partition
{
int i, j; itemType v;
if(r>l)
{
// 정렬한 리스트의 가장 왼쪽 데이터를 피벗으로 선택
v = a[l]; i=l; j=r+1;
while(1){
while(a[++i] < v);
while(a[--j] > v);
if(i >= j)break; // low와 high가 교차하지 않았으면
swap(a, i, j); // left, right swap
}
swap(a, j, l); // 피벗을 중앙에 위치시킨다
}
return j; // 피벗의 위치 반환
};
void quicksort(itemType a[], int l, int r) // 퀵 정렬
{
int j;
if(r>l){ // 정렬한 범위가 2개 이상의 데이터면
comparision++; // 비교연산 카운터 증가
j = partition(a, l, r); // partition 함수 호출
// 피벗을 기준으로 2개의리스트로 분할한다
quicksort(a, l, j-1); // left에서 피벗 위치 바로 앞까지 대상으로 순환호출
quicksort(a, j+1, r); // 피벗 위치 다음부터 right까지 대상으로 순환호출
}
}
void result() // 결과 출력 함수
{
cout<<"\n비교연산 회수는 "<< comparision <<"번 수행 되었습니다.\n";
cout<<"자료이동 회수는 "<< data_swap <<"번 수행 되었습니다.\n\n";
comparision = 0; // 비교연산 카운터 변수 초기화
data_swap = 0; // 자료이동 카운터 변수 초기화
}
void main()
{
// 퀵 정렬에 사용되는 배열
itemType a[MAX];
int j=0; // Worst Case 배열을 위한 변수
printf("\nQuick Sort : %d개의 양의정수 Case 비교\n\n", MAX);
//////////////// Best Case array & Result //////////////////
for(int i=0; i<MAX; i++) a[i] = i;
printf("--------------------------------------------------");
quicksort(a, 0, MAX-1);
cout << "\n--- Best Case ---";
result();
////////////////////////////////////////////////////////////
//////////////// Worst Case array & Result /////////////////
for(int i=MAX; i>=1; i--){
a[j] = i; j++;
}
printf("--------------------------------------------------");
quicksort(a, 0, MAX-1);
cout << "\n--- Worst Case ---";
result();
////////////////////////////////////////////////////////////
//////////////// Random Case array & Result ////////////////
for(int i=0; i < MAX; i++)a[i] = rand() % MAX+1;
printf("--------------------------------------------------");
quicksort(a, 0, MAX-1);
cout << "\n--- Random Case ---";
result();
////////////////////////////////////////////////////////////
printf("--------------------------------------------------\n\n");
}
▣ 결과 출력
4-3. 최악의 경우에 해당하는 data로서 Sheel Sort 알고리즘을 구현하고, 4-1의 Insertion Sort할 때와 비교해서 비교연산과 연산회수를 출력하시오.
#include <iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
#define MAX 1500
typedef int itemType;
int data_swap = 0;
int comparision = 0;
void shellsort(itemType a[], int N) // 쉘 정렬
{
int i, j, h; itemType v;
h = 1;
do{ h = 3*h+1;}while(h<N); // 배열의 크기보다 작으면서 가장 큰
// h의 값을 찾는다
do{ // h값을 줋이면서 각 부분배열에 삽입정렬을 적용
h = h / 3; // h값을 3으로 나누는 정수형 나눗셈
for(i=h; i<=N; i++){
comparision++; // 비교연산 카운터 증가
v = a[i]; j = i;
while(a[j-h] > v){
data_swap++; // 자료이동 카운터 증가
a[j] = a[j-h];
j-=h;
if(j <= h-1)break;
}
a[j] = v;
}
}while(h>1);
};
void result() // 결과 출력 함수
{
cout<<"\n비교연산 회수는 "<< comparision <<"번 수행 되었습니다.\n";
cout<<"자료이동 회수는 "<< data_swap <<"번 수행 되었습니다.\n\n";
comparision = 0; // 비교연산 카운터 변수 초기화
data_swap = 0; // 자료이동 카운터 변수 초기화
}
void main()
{
// 삽입,쉘 정렬에 사용되는 배열
itemType a[MAX+1];
a[0] = -1; // 첫번째 배열에 더미값 초기화
int j=1; // Worst Case 배열을 위한 변수
printf("\nInsertion Sort 와 Shell Sort 의 Worst Case 비교_
_[%d개의 양의정수]\n\n", MAX);
//////// Insertion Sort Worst Case array & Result //////////
for(int i=MAX; i>=1; i--){
a[j] = i;
j++;
}
printf("--------------------------------------------------");
shellsort(a, MAX);
cout << "\n--- Insertion Sort Worst Case ---";
result();
////////////////////////////////////////////////////////////
////////// Shell Sort Worst Case array & Result ////////////
j=1
for(int i=MAX; i>=1; i--){
a[j] = i;
j++;
}
printf("--------------------------------------------------");
shellsort(a, MAX);
cout << "\n--- Shell Sort Worst Case ---";
result();
////////////////////////////////////////////////////////////
printf("--------------------------------------------------\n\n");
}
▣ 결과 출력
'Univ Study > 알고리즘과 실습' 카테고리의 다른 글
알고리즘(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 |
알고리즘(Algorithm) 실습1 (0) | 2009.05.05 |