|
/* 본 소스는 이재규씨가 저술한 "C로 배우는 알고리즘"의 정렬 부분에서
그림으로만 나온 각 정렬의 성능을 비교하는 시뮬레이션을 api를
이용해서 실제로 구현해본 소스입니다.
각 정렬의 상세 알고 리즘에 차후의 강의 에서 다룰 것이므로 생략을
했고 시뮬레이션 소스 부분만을 설명 했습니다.
기본적으로 C와 win32api의 기본 지식이 있어야 하며
win32api는 김상형씨가 쓴책이 처음 보기에 좋습니다.
c 책은 좋은게 워낙 많으니깐 ...
알고리즘을 공부 할때는 딱딱한 수식이 즐비한 수학기반의
책을 보기 보담 눈으로 바로 확인 할 수 있는 그래픽한 소스 기반
으로 공부 하는게 질리지 않고 끝까지 할 수 있습니다.
보통 사람들이 알고리즘을 할 때 정렬까지는 엄청 쉬운듯이 말 하지만
정렬 알고리즘은 이 전 세대가 수 백년 동안 작성한 가장 완성도 있는
알고리즘이라 할 수 있습니다.
코드는 짧지만 이해하기는 매우 어려 우며 예제를 보지 않고 구현 하기란
더욱 어렵습니다.
보통 알고리즘의 기본이 되며 기본이 쉽다는것을 의미 하는것은 아닙니다.
알고리즘의 원류를 알고 있는 사람은 어떤 문제가 닥쳐 와도 해결 할 수
있는 능력을 보유 하고 있습니다.
*/
#include <windows.h>
#include <stdio.h>
#include <stdlib.h> //srand(), rand(), RAND_MAX
#include <time.h> //time()
LRESULT WndProc(HWND,UINT,WPARAM,LPARAM);
BOOL InitApp(HINSTANCE hInstance, char *cname)
{
WNDCLASS wc; //윈도우의 공통적인 특성을 정의 하는 구조체
wc.style = CS_HREDRAW | CS_VREDRAW | CS_DBLCLKS;
wc.lpfnWndProc = (WNDPROC)WndProc; //윈도우 프로시저 주소
wc.cbClsExtra = 0;
wc.cbWndExtra = 0;
wc.hInstance = hInstance;
wc.hIcon = LoadIcon(NULL,IDI_APPLICATION);
wc.hCursor = LoadCursor(NULL, IDC_ARROW);
wc.hbrBackground = (HBRUSH)GetStockObject(WHITE_BRUSH);
wc.lpszMenuName = NULL;
wc.lpszClassName = cname; //구조체의 이름, 윈도우 클래스를
//유일하게 식별한다.
return RegisterClass(&wc); //운영체제에게 구조체의 주소를 등록
}
void InitInst(HINSTANCE hInstance, int nCmdShow, char * cname, char *title)
{
HWND hWnd;
hWnd = CreateWindow(
cname,
title,
WS_OVERLAPPEDWINDOW,
CW_USEDEFAULT,
CW_USEDEFAULT,
CW_USEDEFAULT,
CW_USEDEFAULT,
NULL,
NULL,
hInstance,
NULL);
ShowWindow(hWnd, nCmdShow); //메모리에 있는 원도우 객체를
//화면상에 보여줌
UpdateWindow(hWnd); //WM_PAINT 메시지를 생성
}
// 각 정렬 함수의 프로토타입 선언
void bubble_sort(HDC, int *,int);
void select_sort(HDC, int *,int);
void insert_sort(HDC, int *,int);
void shell_sort(HDC, int *,int);
void quick_sort(HDC, int *,int,int);
void radix_sort(HDC, int *, int, int, int);
// 프로그램의 엔트리 포인트
int WINAPI WinMain(HINSTANCE hInstance, HINSTANCE hPreInstance,
LPSTR lpCmdLine, int nShowCmd)
{
MSG msg;
InitApp(hInstance,"init.h");
InitInst(hInstance,nShowCmd,"init.h","bubble_sort");
while( GetMessage(&msg, NULL,0,0))
{
TranslateMessage(&msg); //WM_CHAR 메시지 생성
DispatchMessage(&msg); //프로시져 호출
}
return msg.wParam;
}
#define BLACK RGB(0,0,0) //매크로 상수를 사용하여 코드를 간단하게..
#define WHITE RGB(255,255,255) //RGB()는 매크로 함수
LRESULT WndProc(HWND hWnd, UINT msg, WPARAM wParam, LPARAM lParam)
{
int x, nsu[2000];
int c_width, c_height;
HDC hdc;
switch(msg)
{
case WM_SIZE:
c_width = LOWORD(lParam); //클라이언트 영역의 가로크기
c_height = HIWORD(lParam); //클라이언트 영역의 세로크기
hdc = GetDC(hWnd); //디바이스 컨텍스트의 핸들얻기
for(x=0; x<c_width; x++)
{
// 0 ~ c_height 사이의 랜덤 값을 생성 한다.
// rand()함수의 생성 범위 0~32767
// RAND_MAX 는 0x7fff 즉 32767의 매크로 상수임
nsu[x] = c_height*rand()/RAND_MAX;
// 세로의 픽셀 단위의 한 줄에 가로로 랜덤한 곳에 점을찍음
SetPixel(hdc,x,nsu[x],BLACK);
}
//아래에 있는 함수 중 디스플레이 하고 싶은 함수만 주석을 풀고 실행한다.
// bubble_sort(hdc,nsu,c_width); // 거품 정렬
// select_sort(hdc,nsu,c_width); // 선택 정렬
// insert_sort(hdc,nsu,c_width); // 삽입 정렬
// shell_sort(hdc,nsu,c_width); // 쉘 정렬
// quick_sort(hdc,nsu,c_width,0); // 퀵 정렬
radix_sort(hdc, nsu, c_width, 31, 0); // 기수 정렬
ReleaseDC(hWnd,hdc);
break;
case WM_DESTROY:
PostQuitMessage(0);
break;
default:
return DefWindowProc(hWnd,msg,wParam,lParam);
}
return 0;
}
void bubble_sort(HDC hdc, int *a,int n)
{
int i,j,flag,temp;
for(i=0; i<n-1 ; i++)
{
flag=0;
for(j=0; j<n-i-1 ; j++)
if(a[j] > a[j+1])
{
SetPixel(hdc, j, a[j],WHITE);
SetPixel(hdc,j+1, a[j],BLACK);
SetPixel(hdc, j+1, a[j+1], WHITE);
SetPixel(hdc, j , a[j+1], BLACK);
temp = a[j];
a[j] = a[j+1];
a[j+1]= temp;
flag=1;
}
if(!flag)
return;
Sleep(1);
}
}
void select_sort(HDC hdc, int *a,int n)
{
int i,j,chd,max;
for(i=0; i<n-1 ; i++)
{
chd = i;
max = a[i];
for(j=i+1; j<n; j++)
if(a[j] > max)
{
chd = j;
max = a[j];
}
SetPixel(hdc, chd, a[chd],WHITE);
SetPixel(hdc, i, a[chd],BLACK);
SetPixel(hdc, i, a[i], WHITE);
SetPixel(hdc, chd, a[i], BLACK);
a[chd] = a[i];
a[i] = max;
Sleep(1);
}
}
void insert_sort(HDC hdc, int *a,int n)
{
int i, j, temp;
for(i=1; i<n; i++)
{
temp = a[i];
j = i-1;
while(j>=0 && a[j]>temp)
{
SetPixel(hdc, j, a[j],WHITE);
SetPixel(hdc,j+1, a[j],BLACK);
a[j+1]=a[j];
j--;
}
SetPixel(hdc, i, temp, WHITE);
SetPixel(hdc, j+1 , temp, BLACK);
a[j+1] = temp;
Sleep(10);
}
}
void shell_sort(HDC hdc, int *a,int n)
{
int i, j, temp, term;
int start;
term = n;
while( term > 1)
{
term = term/3 +1;
for(start=0; start<term; start++)
{
for(i=start; i<n; i+=term)
{
temp = a[i];
j = i - term;
while( j>=0 && a[j]>temp)
{
SetPixel(hdc, j, a[j], WHITE);
SetPixel(hdc, j+term , a[j], BLACK);
a[j+term] = a[j];
j -= term;
}
SetPixel(hdc, i, temp, WHITE);
SetPixel(hdc, j+term , temp, BLACK);
a[j+term] = temp;
}
Sleep(10);
}
}
}
void quick_sort(HDC hdc, int *a, int n, int x)
{
int i,j;
int key, temp;
if(n > 1)
{
key = a[0];
i = 0;
j = n;
while(1)
{
while(a[++i] < key);
while(a[--j] > key);
if(i >= j)
break;
SetPixel(hdc, x+i, a[i], WHITE);
SetPixel(hdc, x+j, a[i], BLACK);
SetPixel(hdc, x+j, a[j], WHITE);
SetPixel(hdc, x+i, a[j], BLACK);
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
SetPixel(hdc, x+0, key, WHITE);
SetPixel(hdc, x+j, key, BLACK);
SetPixel(hdc, x+j, a[j], WHITE);
SetPixel(hdc, x+0, a[j], BLACK);
a[0] = a[j];
a[j] = key;
quick_sort(hdc, a , j , x);
quick_sort(hdc, a+j+1, n-j-1, x+j+1);
}
Sleep(10);
}
void radix_sort(HDC hdc, int *a, int n, int b, int x)
{
int i, j, temp;
if(n>1 && b>=0)
{
i = 0 ;
j = n-1;
while(1)
{
while( ((a[i] >> b)&1) == 0 && i<j)
i++;
while( ((a[j] >> b)&1) == 1 && i<j)
j--;
if(j <= i )
break;
SetPixel(hdc, x+i, a[i], WHITE);
SetPixel(hdc, x+j, a[i], BLACK);
SetPixel(hdc, x+j, a[j], WHITE);
SetPixel(hdc, x+i, a[j], BLACK);
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
if( ((a[n-1] >> b)& 1) == 0)
j++;
radix_sort(hdc, a, j, b-1, x);
radix_sort(hdc, a+j, n-j, b-1, x+j);
Sleep(10);
}
}
[C언어전문가과정 문의 = http://www.lesson-web.com/prom/c_main.htm]
|
