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");

}

 

 

▣ 결과 출력