[대학교 과제] 미디어처리 알고리즘, Insert Sort / Shell Sort / Bubble Sort

 

4-1 Insertion Sort 알고리즘을 구현하고, 비교연산과 자료이동 연산회수를 conut 해서 출력하시오.

#include <stdlib.h>

#include <iostream>

using namespace std;

 

 

class sort

{

public:

sort() // 클래스 변수 선언시 실행

{

insertinit(); // 삽입정렬의 필요한 변수 초기화

insertion(rand_arr, 10000); // 정렬을 시작한다.

print_sort(); // 정렬된 데이터 출력

}

void insertinit() // 삽입정렬 변수 초기화함수

{

rand_arr[0] = -1; // 삽입정렬의 더미키로써 어느값보다 작은 역활을 한다.

count = 0; // 연산회수를 카운터할 변수의 초기화

for(i=1; i<=10000; i++) // rand 함수를 이용해 10000개의 변수를 생성한다. 더미값을 제외하고 10000개 생성

rand_arr[i] = rand() % 20000;

}

void insertion(int a[], int N) // 삽입정렬을 수행하는 함수이다.

{

for(i=2;i<=N;i++) //2번째 배열부터 왼쪽배열과의 비교를 수행한다. 1부터 시작하면 더미값과 비교하기에 쓸모가없다.

{

v = a[i]; // 비교할 값을 다른 변수에 넣어서 사용한다.

j = i; // 비교연산을 하기 위한 인덱스이다.

while(a[j-1]>v) // 자신과 자신의 값보다 왼쪽에 있는 값과 비교하여 왼쪽에 있는 값이 더 크다면 실행한다.

{

a[j] = a[j-1]; // 왼쪽의 값을 오른쪽에 위치에 넣는다.

j--; // 인덱스 1을 감소시켜 반복한다.

count++; // 연산회수를 카운트한다.

}

a[j] = v; // 비교가 끝난후 처음비교대상의 값을 왼쪽에 넣는다.

}

}

void print_sort() // 정렬이 끝난 배열을 출력하기 위한 함수이다.

{

cout << "삽입정렬로 정렬된 배열" << endl;

for(i = 1; i<10001; i++) // 더미키를 제외한 배열의 1~10000까지의 수를 차례대로 출력한다.

cout << rand_arr[i] << ' ';

cout << endl << "비교연산과 자료이동 연산회수 : " << count << endl; // 마지막으로 연산회수를 출력한다.

 

}

 

 

private:

int i, j, v, count; // 반복문을 수행하기 위한 변수와 자리이동을 위한 변수 그리고 비교연산과 자리이동연산 카운트를 위한 변수 선언

int rand_arr[10001]; // 더미키를 제외한 비교값을 포함하여 10001의 배열 선언

};

 

 

int main(void)

{

sort s;

}

삽입정렬은 자신의 왼쪽값하고만 비교를 수행한다. 다만 이 비교를 반복문으로서 반복함으로써 자신보다 큰 수는 자신의 오른쪽으로 위치하게 됨으로써 정렬이 완성된다. 최선의 경우는 오름차순으로 정렬된 배열을 정렬할때고 최악의 경우는 내림차순으로 정리된 배열을 정렬할 때 이다. 내림차순의 경우는 항상 비교연산과 자료이동을 수행함으로써 수행시간이 최고를 이룬다.

 

4-2 최악의 경우에 해당하는 data로서 Shell Sort 알고리즘을 구현하고, 4-1의 Insertion Sort 할 때와 비교해서 비교연산고 자료이동 연산회수를 출력하시오.

#include <stdlib.h>

#include <iostream>

using namespace std;

 

 

class sort

{

public:

sort()

{

insert_init(); // 삽입정렬의 필요한 변수 초기화

insertion(rand_arr, 10000); // 정렬을 시작한다.

Worst_Sort(); // 이미 정렬된 데이터를 역순으로 정렬함으로써 최악의 자료형태로 만든다.

insert_init(); // 초기화 과정을 거치지만 역순으로 정렬된 데이터에 영향을 주지않기때문에 count를 위해 함수실행.

insertion(worst_arr, 10000); // 최악의 자료로 정렬을 수행하고 그 연산회수를 count한다.

Worst_Sort(); // shell정렬을 위해 다시한번 역순으로 정렬한다.

shell_init(); // shell정렬을 위해 초기화

shellSort(worst_arr, 10000); // shell정렬을 실행하는 함수이다.

print_sort(); // 정렬된 데이터의 연산회수 출력

}

void insert_init() // 삽입정렬 변수 초기화함수

{

rand_arr[0] = -1; // 삽입정렬의 더미키로써 어느값보다 작은 역활을 한다.

count_insert = 0; // 삽입정렬의 연산회수를 카운터할 변수의 초기화

for(i=1; i<=10000; i++) // rand 함수를 이용해 10000개의 변수를 생성한다. 더미값을 제외하고 10000개 생성

rand_arr[i] = rand() % 20000;

}

void insertion(int a[], int N) // 삽입정렬을 수행하는 함수이다.

{

for(i=2;i<=N;i++) //2번째 배열부터 왼쪽배열과의 비교를 수행한다. 1부터 시작하면 더미값과 비교하기에 쓸모가없다.

{

v = a[i]; // 비교할 값을 다른 변수에 넣어서 사용한다.

j = i; // 비교연산을 하기 위한 인덱스이다.

while(a[j-1]>v) // 자신과 자신의 값보다 왼쪽에 있는 값과 비교하여 왼쪽에 있는 값이 더 크다면 실행한다.

{

a[j] = a[j-1]; // 왼쪽의 값을 오른쪽에 위치에 넣는다.

j--; // 인덱스 1을 감소시켜 반복한다.

count_insert++; // 연산회수를 카운트한다.

}

a[j] = v; // 비교가 끝난후 처음비교대상의 값을 왼쪽에 넣는다.

}

}

void print_sort() // 정렬이 끝난 배열을 출력하기 위한 함수이다.

{

for(i=0;i<10000;i++)

cout << worst_arr[i] << ' ';

cout << "삽입정렬로 정렬된 배열의" << endl << "비교연산과 자료이동 연산회수 : " << count_insert << endl;;

cout << "쉘정렬로 정렬된 배열의" << endl << "비교연산과 자료이동 연산회수 : " << count_shell << endl;;

}

void shell_init() // shell정렬을 사용하기위해 변수들의 초기화이다.

{

count_shell = 0; // 연산회수를 count할 변수를 초기화한다.

h = 1; // shell정렬을 사용하기위한 변수 초기화

do h = 3*h+1; // 쉘정렬의 간격을 위해 10000넘을 때 까지 곱해준다.

while(h < 10000);

for(i=0; i<10000; i++) // 10000개의 랜덤 변수를 생성해준다

rand_arr[i] = rand() % 20000; // 최대의 수가 20000을 넘지 않게 해준다.

}

 

void shellSort(int a[], int N)

{

do{

h = h/3; // 간격을 3으로 나누어서 다시 넣어준다.

for(i=h; i<N; i++) // h부터 N까지만큼 반복한다.

{

v = a[i]; // 위치를 교환하기전 현재의 값을 v에 넣어준다.

j = i; // i를 인덱스 j의 값에 넣어준다.

while(a[j-h]>v) // a에 있는 값이 현재의 값보다 크면 실행

{

count_shell++; // 연산 count

a[j] = a[j-h]; // 큰 값을 현재의 값 위치에 넣어준다.

j -= h; // 다음 간격으로 옮겨준다.

if(j <= h-1) break;

}

a[j] = v; // 저장해두었던 값을 연산이 끝난 자리에 넣어준다.

}

}while(h>1); // h가 1보다 클때까지 반복한다.

}

void Worst_Sort(){ // 최악의 자료형으로 만들어 주기 위한 함수

i=0; // 역순으로 정렬하기 위한 변수

arr_ptr = &rand_arr[10000]; // 마지막 주소값에 포인터를 연결한다.

while(i!=10001){

worst_arr[i++] = *arr_ptr; // 포인터는 감소하면서 배열은 증가하면서 역순으로 집어넣는다.

arr_ptr--;

}

}

 

private:

int i, j, v, h, count_insert, count_shell;

int rand_arr[10001], worst_arr[10001];

int *arr_ptr;

};

 

 

int main(void)

{

sort s;

}

최악의 자료형은 내림차순으로 배열되어 있는 것이라 생각하고 이미 그렇게 정렬된 배열을 다시 정렬한 방식이다. 삽입 정렬보다 확실히 연산 회수가 적어 좋은 알고리즘이라는 것을 알 수가 있다. 코드 형식이 복잡해서 처음엔 이해하기 힘들지만 잘 알아두면 좋은 알고리즘이라는 생각이 든다.

 

4-3. Bubble Sort 알고리즘을 구현하고, Shell Sort 의 비교연산과 자료교환 연산회수를 비교하여 출력하시오.

 

#include <stdlib.h>

#include <iostream>

using namespace std;

 

 

class sort

{

public:

sort() // 클래스 변수 선언시 실행

{

shell_init(); // 쉘정렬 초기화

shellSort(rand_arr, 10000); // 쉘 정렬 시작

Bubble_init(); // 버블정렬 초기화

BubbleSort(10000); // 버블정렬 실행

print_sort(); // 결과 출력

}

 

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

{

for(i = 0; i<10000; i++) // 버블정렬로 정렬된 배열 출력

cout << rand_arr[i] << ' ';

cout << endl << "쉘정렬로 정렬된 배열의" << endl << "비교연산과 자료이동 연산회수 : " << count_shell << endl;;

cout << "버블정렬로 정렬된 배열의" << endl << "비교연산과 자료이동 연산회수 : " << count_bubble << endl;;

}

void shell_init() // shell정렬을 사용하기위해 변수들의 초기화이다.

{

count_shell = 0; // 연산회수를 count할 변수를 초기화한다.

h = 1; // shell정렬을 사용하기위한 변수 초기화

do h = 3*h+1; // 쉘정렬의 간격을 위해 10000넘을 때 까지 곱해준다.

while(h < 10000);

for(i=0; i<10000; i++) // 10000개의 랜덤 변수를 생성해준다

rand_arr[i] = rand() % 20000; // 최대의 수가 20000을 넘지 않게 해준다.

}

 

void shellSort(int a[], int N)

{

do{

h = h/3; // 간격을 3으로 나누어서 다시 넣어준다.

for(i=h; i<N; i++) // h부터 N까지 만큼 반복한다.

{

v = a[i]; // 위치를 교환하기전 현재의 값을 v에 넣어준다.

j = i; // i를 인덱스 j의 값에 넣어준다.

while(a[j-h]>v) // a에 있는 값이 현재의 값보다 크면 실행

{

count_shell++; // 연산 count

a[j] = a[j-h]; // 큰 값을 현재의 값 위치에 넣어준다.

j -= h; // 다음 간격으로 옮겨준다.

if(j <= h-1) break;

}

a[j] = v; // 저장해두었던 값을 연산이 끝난 자리에 넣어준다.

}

}while(h>1); // h가 1보다 클때까지 반복한다.

}

inline void Swap(int a[],int num1,int num2) // 배열의 위치를 바꿔주기 위한 함수이다.

{

int buf;

buf = a[num1];

a[num1] = a[num2];

a[num2] = buf;

}

void BubbleSort(int n)

{

while(!Sorted){

Sorted = 1; // 이미 정렬된 배열일 경우 반복문을 빠져나간다.

for(i=1;i<n;i++)

if(rand_arr[i-1]>rand_arr[i]){ // 오른쪽보다 왼쪽에 큰 값이 있다면 반복문을 유지하고 자리를바꿔준다.

Swap(rand_arr, i-1, i);

Sorted = 0;

count_bubble++; // 연산 count

}

n--; // 첫번째에 맨마지막에는 제일 큰 숫자가 두번쨰에는 n-1에 제일큰 숫자가 들어가기에 최대값을 -1해준다.

}

 

}

void Bubble_init() // 버블정렬에 필요한 함수를 초기화 해준다.

{

count_bubble = 0;

Sorted = 0;

for(i=0; i<10000; i++)

rand_arr[i] = rand() % 20000;

}

private:

int i, j, v, h, count_shell, count_bubble;

int rand_arr[10001];

int Sorted;

};

 

 

int main(void)

{

sort s;

}

버블정렬은 삽입정렬과는 정반대의 방식이라 보면된다. 삽입정렬같은 경우 제일 작은 수를 왼쪽에 넣는 방식이지만 버블정렬같은 경우는 제일 큰수를 오른쪽에 차곡차곡 쌓아 놓는다. 두 함수의 비교연산회수는 비슷하며 둘다 안정적이다. 나의 프로그래밍 결과에서는 버블정렬이 약간 더 연산에 우위를 차지하였지만 크게 다르지 않음을 볼 수 있다.