'학과수업들/알고리즘'에 해당되는 글 12건
- 2007/11/06 Project #2 / 배열기반 해싱
- 2007/11/06 Project #1 / 히프정렬, 기수정렬 / 비교
- 2007/10/03 알고리즘 / 기수 정렬 알고리즘
- 2007/10/03 알고리즘 / 계수 정렬 알고리즘
- 2007/10/03 알고리즘 / 히프 정렬 알고리즘(1)
- 2007/10/03 알고리즘 / 합병 정렬 알고리즘
- 2007/10/03 알고리즘 / 퀵 정렬 알고리즘
- 2007/09/16 알고리즘 / 쉘 정렬 알고리즘
- 2007/09/16 알고리즘 / 삽입 정렬 알고리즘
- 2007/09/09 알고리즘 / 버블 정렬 알고리즘(2)
- 2007/09/09 알고리즘 / 선택 정렬 알고리즘
- 2007/09/03 알고리즘 / 에라토스테네스의 체, 알고리즘 ADL
/*
Porject #2
배열을 기반으로 해싱하는 프로그램 작성 - 선형탐사법
>데이터의 삽입, 삭제, 탐색 기능 필요
- 삽입, 삭제 시에는 매번 배열의 내용 출력
- 탐색 시에는 데이터의 위치 출력
>데이터는 key field 만으로 구성
>데이터의 수는 10개 이상
Compiler : Borland C++ 5.5
Coding Program : EditPlus 2.31
*/
#include <iostream.h>
#include <time.h>
#include <stdlib.h>
const int N = 17; //데이터의 갯수
const int M = 19; //해쉬테이블의 크기
class Dict
{
public:
Dict() {
a = new int[M]; //해쉬테이블 크기만큼
for (int i=0; i<M; i++) a[i] = -1; // -1로 해쉬테이블 초기화
}
int search(int v);
void insert(int v);
int del(int v);
void print();
private:
int *a;
};
int hash(int v, int M) //해쉬 함수
{
return (v % M);
}
void Dict::print() //출력 함수
{
for (int i=0; i<M; i++) //해쉬테이블 크기만큼 반복
{
if (a[i] != -1) cout << a[i] << ' '; //데이터가 있으면 출력
else cout << '#' << ' '; //데이터가 없으면 # 출력
if ((i+1) % M == 0) cout << endl; // M개 만큼 출력하고 한줄 아래로
}
}
void Dict::insert(int v) //삽입 함수
{
int x;
x = hash(v, M); //해쉬값을 구하여 x 변수로
while (a[x] != -1)
x = (x + 1) % M; //순환구조
a[x] = v; //키값을 a배열에
}
int Dict::search(int v) //탐색 함수
{
int x;
int count = 0;
x = hash(v, M); //해쉬값을 구하여 x 변수로
while (a[x] != -1){ //데이터가 있으면 반복
if (count == M){
cout << "찾는 데이터가 없습니다." << endl;
break;
}
if (v == a[x]){
cout << "데이터가 위치한 번지 : " << x << endl; // 탐색값 위치 출력
return a[x]; //찾는 데이터가 있으면 해당 값 리턴
}
else{
x = (x + 1) % M; //대체 번지
count++;
}
}
return -1;
}
int Dict::del(int v) //삭제 함수
{
int x;
int count = 0;
x = hash(v, M); //해쉬값을 구하여 x 변수로
while (a[x] != -1){ //데이터가 있으면 반복
if (count == M){
cout << "찾는 데이터가 없습니다." << endl;
break;
}
if (v == a[x]){
cout << "삭제전 : ";
print(); // 삭제전 배열상태 출력
a[x] = -1; //찾은값 삭제
cout << "삭제후 : ";
print(); // 삭제후 배열상태 출력
return x; //삭제된 번지 값 리턴
}
else{
x = (x + 1) % M; //대체 번지
count++;
}
}
return -1;
}
void main()
{
Dict d;
int i, result, key[N], search_key[N];
int select, idata, sdata, ddata;
double start_time; //탐색 시간 체크를 위한 변수
Dict(); //데이터 초기화
cout << "메뉴를 선택하세요." << endl;
cout << "1. 데이터 삽입" << endl;
cout << "2. 데이터 탐색" << endl;
cout << "3. 데이터 삭제" << endl;
cout << "4. 프로그램 종료" << endl;
while (1)
{
cout << "메뉴선택>" ;
scanf("%d",&select);
if (select == 1){
cout << "데이터를 삽입하세요." << endl;
//데이터 삽입
for (i=0; i<N; i++)
{
if (i > M-1)
{
cout << "overflow!!" << endl;
break;
}
printf("삽입값 %d : ",i);
scanf("%d",&idata);
key[i] = search_key[i] = idata;
d.insert(key[i]); //데이터 삽입
d.print(); // 삽입시마다 배열상태 출력
}
}else if(select == 2){
//데이터 탐색
printf("찾을값 : ");
scanf("%d",&sdata);
start_time = clock();//현재 시간을 start_time 변수에
result=d.search(sdata);
if (result == -1)
{
cout << "찾는 데이터가 없습니다." << endl;
}else{
cout << "선형 탐사법의 실행 시간 (N = " << N <<
") : " << clock() - start_time << endl;
}
d.print(); // 배열상태 출력
}else if(select == 3){
//데이터 삭제
printf("삭제할값 : ");
scanf("%d",&ddata);
result=d.del(ddata);
if (result == -1)
{
cout << "찾는 데이터가 없습니다." << endl;
}
}else if(select == 4){
//프로그램 종료
exit(0);
}
}
}
#include <iostream.h>
#include <time.h>
#include <stdlib.h>
#include "sort.h"
const int M = 2; //digit 수
const int N = 10; //원소의 개수
class Queue
{
public:
Queue();
~Queue();
void enqueue(int v);
int dequeue();
int empty();
private:
struct node
{
int data;
struct node *link;
};
struct node *front, *rear;
};
Queue::Queue()
{
front = new node;
rear = new node;
front = NULL;
rear = NULL;
}
Queue::~Queue()
{
struct node *t = front;
while (t != NULL) {
front = t; t->link = t; delete front;
}
}
void Queue::enqueue(int v)
{
struct node *t = new node;
t->data = v;
t->link = NULL;
if (front == NULL) {
front = t;
rear = t;
}
else {
rear->link = t;
rear = t;
}
}
int Queue::dequeue()
{
int x;
struct node *t = front;
if (front == NULL) {
cout << "큐가 공백임." << endl;
exit(1);
return 0;
}
else {
x = t->data;
front = t->link;
if (front == NULL) rear = NULL;
delete t;
return x;
}
}
int Queue::empty()
{
return front == NULL;
}
int digit(int d, int k)
{
int i, temp = 1;
for (i=1; i<k; i++) temp *= 10;
d /= temp;
d %= 10;
return d;
}
void RadixSort(int a[], int n, int m, Queue q[])
{
int k, i, p, kd;
for (k=1; k<=m; k++) {
for (i=1; i<=n; i++) {
kd = digit(a[i], k);
q[kd].enqueue(a[i]);
}
p = 0;
for (i=0; i<=9; i++)
while (!q[i].empty())
a[++p] = q[i].dequeue();
//정렬과정 출력 START
for (int x=1; x<=N; x++)
{
printf("%3d ",a[x]);
if (x%10==0)
{
printf("\n");
}
}
printf("\n---------------------------------------\n");
//정렬과정 출력 END
}
}
main()
{
int i;
double start_time;
Queue Q[10];
int a[N+1]={0,35,81,12,67,93,46,23,26,10,15};
start_time = clock();
RadixSort(a, N, M, Q);
cout << "기수 정렬의 실행 시간 (N = " << N << ") : " << clock() - start_time << endl;
CheckSort(a, N);
}
#include <iostream.h>
#include <time.h>
#include <stdlib.h>
#include "sort.h"
const int N = 10;
void heapify(int a[], int h, int m)
{
//정렬과정 출력 START
for (int x=1; x<=N; x++)
{
printf("%3d ",a[x]);
if (x%10==0)
{
printf("\n");
}
}
printf("\n---------------------------------------\n");
//정렬과정 출력 END
int j, v;
v = a[h];
for (j=2*h; j <= m; j *= 2)
{
if (j < m && a[j] < a[j+1]) j++;
if (v >= a[j]) break;
else a[j/2] = a[j];
}
a[j/2] = v;
}
void HeapSort(int a[], int n)
{
int i;
for (i=n/2; i >=1; i--)
heapify(a, i, n);
for (i=n-1; i >=1; i--) {
swap(a, 1, i+1);
heapify(a, 1, i);
}
}
void main()
{
int i;
double start_time;
int a[N+1]={0,35,81,12,67,93,46,23,26,10,15};
start_time = clock();
HeapSort(a, N);
cout << "히프 정렬의 실행 시간 (N = " << N << ") : " << clock() - start_time << endl;
CheckSort(a, N);
}
/* 기수 정렬 알고리즘
RadixSort(a[], n)
for (k ← 1; k ≤ m; k ← k+1) do {
// m은 digit 수, k=1은 최하위 자리
for (i ← 0; i < n; i ← i+1) do {
kd ← digit(a[i], k); // k번째 숫자를 kd에 반환
enqueue(Q[kd], a[i]); // Q[kd]에 a[i]를 삽입
}
p ← 0;
for (i ← 0; i ≤ 9; i ← i+1) do {
while (Q[i] ≠ Ø) do { // Q[i]의 모든 원소를 a[]로 이동
p ← p+1;
a[p] ← dequeue(Q[i]);
}
}
}
end RadixSort()
int digit(int d, int k)
{
int i, temp = 1;
for (i=1; i<k; i++) temp *= 10; // temp = temp * 10
d/= temp; // d = d / temp
d% = 10; // d = d % 10
return d;
end digit()
*/
/* sort.h */
const int TRUE = 1;
const int FALSE = 0;
inline void swap(int a[], int i, int j)
{
int t = a[i]; a[i] = a[j]; a[j] = t;
}
void CheckSort(int a[], int n)
{
int i, Sorted;
Sorted = TRUE;
for (i=1; i < n; i++)
{
if (a[i] > a[i+1]) Sorted = FALSE;
if (!Sorted) break;
}
if (Sorted) cout << "정렬완료." << endl;
else cout << "정렬 오류 발생." << endl;
}
#include <iostream.h>
#include <time.h>
#include <stdlib.h>
#include "sort.h"
const int M = 5;
const int N = 100000;
class Queue
{
public:
Queue();
~Queue();
void enqueue(int v);
int dequeue();
int empty();
private:
struct node
{
int data;
struct node *link;
};
struct node *front, *rear;
};
Queue::Queue()
{
front = new node;
rear = new node;
front = NULL;
rear = NULL;
}
Queue::~Queue()
{
struct node *t = front;
while (t != NULL) {
front = t; t->link = t; delete front;
}
}
void Queue::enqueue(int v)
{
struct node *t = new node;
t->data = v;
t->link = NULL;
if (front == NULL) {
front = t;
rear = t;
}
else {
rear->link = t;
rear = t;
}
}
int Queue::dequeue()
{
int x;
struct node *t = front;
if (front == NULL) {
cout << "큐가 공백임." << endl;
exit(1);
return 0;
}
else {
x = t->data;
front = t->link;
if (front == NULL) rear = NULL;
delete t;
return x;
}
}
int Queue::empty()
{
return front == NULL;
}
int digit(int d, int k)
{
int i, temp = 1;
for (i=1; i<k; i++) temp *= 10;
d /= temp;
d %= 10;
return d;
}
void RadixSort(int a[], int n, int m, Queue q[])
{
int k, i, p, kd;
for (k=1; k<=m; k++) {
for (i=1; i<=n; i++) {
kd = digit(a[i], k);
q[kd].enqueue(a[i]);
}
p = 0;
for (i=0; i<=9; i++)
while (!q[i].empty())
a[++p] = q[i].dequeue();
}
}
main()
{
int i, a[N+1];
double start_time;
Queue Q[10];
srand(time(NULL));
for (i=1; i <= N; i++) a[i] = rand();
start_time = clock();
RadixSort(a, N, M, Q);
cout << "기수 정렬의 실행 시간 (N = " << N << ") : " << clock() - start_time << endl;
CheckSort(a, N);
}
/* 계수 정렬 알고리즘
CountingSort(a[], n, m) // n : 데이터 개수, m : 최대 키값
for (j ← 1; j ≤ m; j ← j + 1) do count[j] ← 0;
// count[]를 0으로 초기화
for (i ← 1; i ≤ n; i ← i + 1) do count[a[i]] ← count[a[i]] + 1;
// 원소의 개수를 세어 count[]에 저장
for (j ← 2; j ≤ m; j ← j + 1) do count[j] ← count[j-1] + count[j];
// 원소가 들어 갈 위치 계산
for (i ← n; i ≥ 1; i ← i - 1) do {
b[count[a[i]]] ← a[i];
// a[]의 원소를 b[]의 계산된 위치로 이동
count[a[i]] ← count[a[i]] - 1; // count[]의 값 하나 감소
}
for (i ← 1; i ≤ n; i ← i + 1) do a[i] ← b[i]; // b[]를 a[]로 다시 이동
end CountingSort()
*/
/* sort.h */
const int TRUE = 1;
const int FALSE = 0;
inline void swap(int a[], int i, int j)
{
int t = a[i]; a[i] = a[j]; a[j] = t;
}
void CheckSort(int a[], int n)
{
int i, Sorted;
Sorted = TRUE;
for (i=1; i < n; i++)
{
if (a[i] > a[i+1]) Sorted = FALSE;
if (!Sorted) break;
}
if (Sorted) cout << "정렬완료." << endl;
else cout << "정렬 오류 발생." << endl;
}
#include <iostream.h>
#include <time.h>
#include <stdlib.h>
#include "sort.h"
const int M = 1000;
const int N = 100000;
void CountingSort(int a[], int n, int m)
{
int i, j, b[N+1], count[M+1];
for (j=1; j<=m; j++) count[j] = 0;
for (i=1; i<=n; i++) count[a[i]]++;
for (j=2; j<=m; j++) count[j] += count[j-1];
for (i=n; i>=1; i--) b[count[a[i]]--] = a[i];
for (i=1; i<=n; i++) a[i] = b[i];
}
main()
{
int i, a[N+1];
double start_time;
srand(time(NULL));
for (i=1; i <= N; i++) a[i] = rand() % M + 1;
start_time = clock();
CountingSort(a, N, M);
cout << "계수 정렬의 실행 시간 (N = " << N << ") : " << clock() - start_time << endl;
CheckSort(a, N);
}
/* 히프 정렬 알고리즘
HeapSort(a[])
n ← a.length - 1; // n은 히프 크기(원소의 수)
// a[1 : n]의 원소를 오름차순으로 정렬
// a[0]은 사용하지 않음
for (i ← n/2; i ≥ 1; i ← i-1) do // 배열 a[]를 히프로 변환
heapify(a, i, n); // i는 내부 노드
for (i ← n-1; i ≥ 1; i ← i-1) do {// 배열 a[]를 오름차순으로 정렬
swap(a, 1, i+1); // a[1]과 a[i+1]을 교환
heapify(a, 1, i);
}
end heapSort()
heapify(a[], h, m) // 노드의 최대 레벨 순서 번호는 m
v ← a[h];
for (j ← 2*h; j ≤ m; j ← 2*j) do {
if (j < m and a[j] < a[j+1]) then j ← j+1;
// j는 큰 값을 갖는 자식 노드의 위치
if (v ≥ a[j]) then exit;
else a[j/2] ← a[j]; // a[j]를 부모 노드로 이동
}
a[j/2] ← v;
end heapify()
*/
/* sort.h */
const int TRUE = 1;
const int FALSE = 0;
inline void swap(int a[], int i, int j)
{
int t = a[i]; a[i] = a[j]; a[j] = t;
}
void CheckSort(int a[], int n)
{
int i, Sorted;
Sorted = TRUE;
for (i=1; i < n; i++)
{
if (a[i] > a[i+1]) Sorted = FALSE;
if (!Sorted) break;
}
if (Sorted) cout << "정렬완료." << endl;
else cout << "정렬 오류 발생." << endl;
}
#include <iostream.h>
#include <time.h>
#include <stdlib.h>
#include "sort.h"
const int N = 100000;
void heapify(int a[], int h, int m)
{
int j, v;
v = a[h];
for (j=2*h; j <= m; j *= 2)
{
if (j < m && a[j] < a[j+1]) j++;
if (v >= a[j]) break;
else a[j/2] = a[j];
}
a[j/2] = v;
}
void HeapSort(int a[], int n)
{
int i;
for (i=n/2; i >=1; i--)
heapify(a, i, n);
for (i=n-1; i >=1; i--) {
swap(a, 1, i+1);
heapify(a, 1, i);
}
}
void main()
{
int i, a[N+1];
double start_time;
srand(time(NULL));
for (i=1; i <= N; i++) a[i] = rand();
start_time = clock();
HeapSort(a, N);
cout << "히프 정렬의 실행 시간 (N = " << N << ") : " << clock() - start_time << endl;
CheckSort(a, N);
}
-
ajc 2008/05/18 01:36
전북대학교 알고리즘 합병정렬 5조 홈페이지 입니다.
http://alg.devlife.net/Index/Index.aspx
http://alg.devlife.net/Index/Index.aspx
http://alg.devlife.net/Index/Index.aspx
합병정렬과 알고리즘에 관한 내용이 있으니 한번 방문 해 주시기 바랍니다.
Trackback : http://my.silpir.net/trackback/250
/* 합병 정렬 알고리즘
MergeSort(a[], l, r)
if (r > l) then {
m ← (r+l)/2;
MergeSort(a[], l, m);
MergeSort(a[], m+1, r);
Merge(a[], l, m, r);
}
end MergeSort()
Merge (a[], l, m, r)
i ← l; j ← m+1; k ← l;
while (i ≤ m and j ≤ r) do {
if (a[i] < a[j]) then {
b[k] ← a[i]; k ← k+1; i ← i+1;
}
else {
b[k] ← a[j]; k ← k+1; j ← j+1;
}
}
while (i ≤ m) do { // 첫번째 리스트의 나머지 원소를 배열 b에 복사
b[k] := a[i]; k := k + 1; i := i + 1;
}
while (j ≤ r) do { // 두번째 리스트의 나머지 원소를 배열 b에 복사
b[k] := b[j]; k := k + 1; j:= j + 1;
}
End Merge()
*/
/* sort.h */
const int TRUE = 1;
const int FALSE = 0;
inline void swap(int a[], int i, int j)
{
int t = a[i]; a[i] = a[j]; a[j] = t;
}
void CheckSort(int a[], int n)
{
int i, Sorted;
Sorted = TRUE;
for (i=1; i < n; i++)
{
if (a[i] > a[i+1]) Sorted = FALSE;
if (!Sorted) break;
}
if (Sorted) cout << "정렬완료." << endl;
else cout << "정렬 오류 발생." << endl;
}
#include <iostream.h>
#include <time.h>
#include <stdlib.h>
#include "sort.h"
const int N = 100000;
int b[N+1];
void MergeSort(int a[], int l, int r)
{
int i, j, k, m;
if (r > l)
{
m = (r+l) / 2;
MergeSort(a, l, m);
MergeSort(a, m+1, r);
for (i = m+1; i > l; i--) b[i-1] = a[i-1];
for (j = m; j < r; j++) b[r+m-j] = a[j+1];
for (k = l; k <= r; k++)
a[k] = (b[i] < b[j]) ? b[i++] : b[j--];
}
}
void main()
{
int i, a[N+1];
double start_time;
srand(time(NULL));
for (i=1; i <= N; i++) a[i] = rand();
start_time = clock();
MergeSort(a, 1, N);
cout << "합병 정렬의 실행 시간 (N = " << N << ") : " << clock() - start_time << endl;
CheckSort(a, N);
}
/* 퀵 정렬 알고리즘
QuickSort(a[], l, r)
Int I, j, v;
if (r > l) then {
v ← a[r]; i ← l-1; j ← r;
for ( ; ; ) do {
while(a[++i] < v);
while(a[--j] > v);
if (i >= j) then break;
swap(a, i, j);
}
swap(a, i, r);
QuickSort(a[], l, i-1);
QuickSort(a[], i+1, r);
}
end QuickSort()
*/
/* sort.h */
const int TRUE = 1;
const int FALSE = 0;
inline void swap(int a[], int i, int j)
{
int t = a[i]; a[i] = a[j]; a[j] = t;
}
void CheckSort(int a[], int n)
{
int i, Sorted;
Sorted = TRUE;
for (i=1; i < n; i++)
{
if (a[i] > a[i+1]) Sorted = FALSE;
if (!Sorted) break;
}
if (Sorted) cout << "정렬완료." << endl;
else cout << "정렬 오류 발생." << endl;
}
#include <iostream.h>
#include <time.h>
#include <stdlib.h>
#include "sort.h"
const int N = 100000;
void QuickSort(int a[], int l, int r)
{
int i, j, v;
if (r > l)
{
v = a[r]; i = l-1; j = r;
for (; ; )
{
while (a[++i] < v);
while (a[--j] > v);
if (i >= j) break;
swap(a, i, j);
}
swap(a, i, r);
QuickSort(a, l, i-1);
QuickSort(a, i+1, r);
}
}
void main()
{
int i, a[N+1];
double start_time;
a[0] = -1; // 감시키
srand(time(NULL));
for (i=1; i <= N; i++) a[i] = rand();
start_time = clock();
QuickSort(a, 1, N);
cout << "퀵 정렬의 실행 시간 (N = " << N << ") : " << clock() - start_time << endl;
CheckSort(a, N);
}
/* 쉘정렬 알고리즘
ShellSort(a[], n)
for (h ← 1; h < n; h ← 3*h+1) do { }; // 첫 번째 h 값 계산
for ( ; h > 0; h ← h/3) do { // h 값을 감소시키며 진행
for (i ← h + 1; i ≤ n; i ← i+1) do {
v ← a[i];
j ← i;
while (j > h and a[j-h] > v) do {
a[j] ← a[j-h];
j ← j-h;
} // while
A[j] ← v;
} // for
} // for
end ShellSort()
*/
/* sort.h */
const int TRUE = 1;
const int FALSE = 0;
inline void swap(int a[], int i, int j)
{
int t = a[i]; a[i] = a[j]; a[j] = t;
}
void CheckSort(int a[], int n)
{
int i, Sorted;
Sorted = TRUE;
for (i=1; i < n; i++)
{
if (a[i] > a[i+1]) Sorted = FALSE;
if (!Sorted) break;
}
if (Sorted) cout << "정렬완료." << endl;
else cout << "정렬 오류 발생." << endl;
}
/*쉘정렬*/
#include <iostream.h>
#include <time.h>
#include <stdlib.h>
#include "sort.h"
const int N = 10000;
void ShellSort(int a[], int N)
{
int i,j,h,v;
for (h=1; h < N; h = 3*h+1) ;
for (; h > 0; h/=3)
{
for (i=h+1; i <= N; i++)
{
v = a[i]; j = i;
while (j > h && a[j-h] > v)
{
a[j] = a[j-h]; j-=h;
}
a[j] = v;
}
}
}
void main()
{
int i, a[N+1];
double start_time;
a[0] = -1; //감시키
srand(time(NULL));
for (i=1; i <= N; i++) a[i] = rand();
start_time = clock();
ShellSort(a, N);
cout << "쉘 정렬의 실행 시간 (N = " << N << ") : " << clock() - start_time << endl;
CheckSort(a, N);
}
/* 삽입정렬 알고리즘
InsertionSort(a[], n)
for (i ← 2; i ≤ n; i ← i+1) do { // 두 번째 원소 a[2]부터
v ← a[i]; // v는 임시 저장소
j ← i;
while (a[j-1] > v) do {
a[j] ← a[j-1]; // a[j-1]을 오른쪽으로 한자리 이동시켜 빈자리를 만듦
j ← j-1;
} // while
A[j] ← v; // v를 빈자리에 삽입
} // for
end InsertionSort()
*/
/* sort.h */
const int TRUE = 1;
const int FALSE = 0;
inline void swap(int a[], int i, int j)
{
int t = a[i]; a[i] = a[j]; a[j] = t;
}
void CheckSort(int a[], int n)
{
int i, Sorted;
Sorted = TRUE;
for (i=1; i < n; i++)
{
if (a[i] > a[i+1]) Sorted = FALSE;
if (!Sorted) break;
}
if (Sorted) cout << "정렬완료." << endl;
else cout << "정렬 오류 발생." << endl;
}
/*삽입정렬*/
#include <iostream.h>
#include <time.h>
#include <stdlib.h>
#include "sort.h"
const int N = 10000;
void InsertionSort(int a[], int N)
{
int i,j,v;
for (i=2; i <= N; i++)
{
v = a[i]; j = i;
while (a[j-1] > v)
{
a[j] = a[j-1]; j--;
}
a[j] = v;
}
}
/*
// while문의 단순화로 기능개선
void InsertionSort(int a[], int N)
{
int i,j,v;
for (i=2; i <= N; i++)
{
v = a[i]; j = i;
while (a[j-1] > v && j > 1)
{
a[j] = a[j-1]; j--;
}
a[j] = v;
}
}
*/
/*
// v대신 a[0]을 저장공간으로 사용
void InsertionSort(int a[], int N)
{
int i,j;
for (i=2; i <= N; i++)
{
a[0]=a[i]; //보초값을 a[0]에 저장
j = i;
while (a[j-1] > a[0])
{
a[j] = a[j-1]; j--;
}
a[j] = a[0]; //a[0]값을 빈자리에 삽입
}
}
*/
void main()
{
int i, a[N+1];
double start_time;
a[0] = -1; //감시키
srand(time(NULL));
for (i=1; i <= N; i++) a[i] = rand();
start_time = clock();
InsertionSort(a, N);
cout << "삽입 정렬의 실행 시간 (N = " << N << ") : " << clock() - start_time << endl;
CheckSort(a, N);
}
/*버블정렬 알고리즘
BubbleSort(a[], n)
for (i ← n; i ≥ 1; i ← i-1) do {
for (j ← 1; j < i; j ← j+1) do {
if (a[j] > a[j+1]) then A[j]와 A[j+1]을 교환;
}
}
end BubbleSort()
*/
/* sort.h */
const int TRUE = 1;
const int FALSE = 0;
inline void swap(int a[], int i, int j)
{
int t = a[i]; a[i] = a[j]; a[j] = t;
}
void CheckSort(int a[], int n)
{
int i, Sorted;
Sorted = TRUE;
for (i=1; i < n; i++)
{
if (a[i] > a[i+1]) Sorted = FALSE;
if (!Sorted) break;
}
if (Sorted) cout << "정렬완료." << endl;
else cout << "정렬 오류 발생." << endl;
}
/*버블 정렬*/
#include <iostream.h>
#include <time.h>
#include <stdlib.h>
#include "sort.h"
const int N = 10000;
void BubbleSort(int a[], int N)
{
int i,j;
for (i=N; i > 1; i--)
{
for (j=1; j < i; j++)
{
if (a[j] > a[j+1])
{
swap(a,j,j+1);
}
}
}
}
void main()
{
int i, a[N+1];
double start_time;
srand(time(NULL));
for (i=1; i <= N; i++) a[i] = rand();
start_time = clock();
BubbleSort(a, N);
cout << "버블 정렬의 실행 시간 (N = " << N << ") : " << clock() - start_time << endl;
CheckSort(a, N);
}
Trackback : http://my.silpir.net/trackback/236
/*선택정렬 알고리즘
SelectionSort(a[], n)
for (i ← 1; i < n; i ← i + 1) do {
배열 a[i], … , a[n] 중에서 가장 작은 원소 a[k]를 선택;
a[k]를 a[i]와 교환;
}
end SelectionSort()
*/
/* sort.h */
const int TRUE = 1;
const int FALSE = 0;
inline void swap(int a[], int i, int j)
{
int t = a[i]; a[i] = a[j]; a[j] = t;
}
void CheckSort(int a[], int n)
{
int i, Sorted;
Sorted = TRUE;
for (i=1; i < n; i++)
{
if (a[i] > a[i+1]) Sorted = FALSE;
if (!Sorted) break;
}
if (Sorted) cout << "정렬완료." << endl;
else cout << "정렬 오류 발생." << endl;
}
/*선택 정렬*/
#include <iostream.h>
#include <time.h>
#include <stdlib.h>
#include "sort.h"
const int N = 10000;
void SelectionSort(int a[], int N)
{
int i,j,min;
for (i=1; i < N; i++)
{
min=i;
for (j=i+1; j <= N; j++)
if (a[j] < a[min]) min=j;
swap(a, min, i);
}
}
void main()
{
int i, a[N+1];
double start_time;
srand(time(NULL));
for (i=1; i <= N; i++) a[i] = rand();
start_time = clock();
SelectionSort(a, N);
cout << "선택 정렬의 실행 시간 (N = " << N << ") : " << clock() - start_time << endl;
CheckSort(a, N);
}
/* 05. 에라토스테네스의 체를 사용하여 소수를 찾는 알고리즘을 ADL로 작성하라. 에라토스테네스의 체 [Erathosthenes'sieve] 그리스의 수학자이자 지리학자인 에라토스테네스가 고안한 소수(素數)를 찾는 방법으로, 이 방법으로 소수를 찾으려면, 2부터 시작해 자연수를 차례로 쓴 다음, 2 이외의 2의 배수, 3 이외의 3의 배수, 4 이외의 4의 배수의 순서로 수를 지워나가 끝에 남는 수가 소수이다. */ /* ADL로 작성 */ /* primeNumber(number[],max)
for (i ← 0; i<max; i ← i+1) do { number[i] ← 0; } for (i ← 2; i<max; i ← i+1) do { if (number[i] == 0) { print(i); for (j ← i*2; j<max; j ← j+i) do { number[j] ← 1; } } } end primeNumber() */ #include <stdio.h> #define MAX 100 //소수를 찾을 최대값 void main() { char number[MAX] ; int i, j; for(i=0; i<MAX; i++) //값 초기화 { number[i] = 0; //0부터 MAX까지 0으로 초기화 } //소수인지 구분 for(i=2; i<MAX ; i++){ if(number[i] == 0) // 초기화 시킨 0이면 출력 { printf("%3d", i); for(j = i*2; j <MAX; j+=i){ //i의 배수가 되는 숫자를 1로 바꾼다. number[j] = 1; } } } printf("\n"); }
Recent Comment