퀵정렬, 퀵소트, Quick sort 를 구현해보았다.

실행화면




소스코드

#include<stdio.h>
#include<stdlib.h>

void shuffle(int *arr);
void swap(int *a, int *b);
void print(int * arr, int st, int ed);
void quick(int *arr);
void partition(int *arr,int _st, int _ed);

int main(int argc, char *argv[])
{
    int arr[16];
    for(int r=0; r<50; r++){
        for(int i=0; i<16; i++){
            arr[i] = i;
        }
     srand(r);
     shuffle(arr);
     printf("%10s : ","shuffle");
     print(arr,0,15);

     quick(arr);
     printf("%10s : ","quick");
     print(arr,0,15);

     printf("=============================================================\n");
     //break;
    }
    system("pause > nul");
    return 0;
}

void quick(int *arr){
    partition(arr,0,15);
}
void partition(int *arr,int _st, int _ed){
    int p = _ed;
    int buf_p = arr[p];
    int st=_st,ed=_ed-1;
    while(st<ed){
        //if(st<p){
        if( arr[st]<arr[p]){
            st++;
            continue;
        }
        if( arr[ed]>arr[p]){
            ed--;
            continue;
        }
        if( arr[st] > arr[ed]){
            swap(arr+st, arr+ed);
        }
    }
    //printf("st=%d,ed=%d,p=%d\n",st,ed,p);
    if( st < p ){
        if( arr[st]>arr[p]){
            swap(arr+st, arr+p);
            int t = p;
            p = st;
            st = t;
        }
    }

    st = _st;
    ed = _ed;
    printf("(%2d)%6s : ",buf_p,"quick");
    print(arr,st,ed);
    if (st < p) 
        partition(arr, st, p-1); 
          if (ed > p) 
              partition(arr, p+1, ed); 
}

void shuffle(int *arr){
    int n = 100;
    int a,b;
    while(n--){
        a = rand()%16;
        b = rand()%16;
        swap(arr+a,arr+b);
    }
}

void swap(int *a, int *b){
    int t = *a;
    *a = *b;
    *b = t;
}

void print(int * arr, int st, int ed){
    for(int i=0; i<16; i++){
        if( st<=i && i<=ed){
            printf("%3d",arr[i]);
        }
        else{
            printf("   ");
        }
    }printf("\n");
}

 
참고자료
http://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC#.EC.95.8C.EA.B3.A0.EB.A6.AC.EC.A6.98
Posted by Нуеоп







무료로 다운 받아 사용할수 있는 IDE들이다.
몇몇 제품은 기능의 제약이 있는데, 사용하는데 별 무리는 없다.





1. microsoft visual c++ express

visual c++ 2005 express
http://www.microsoft.com/korea/msdn/vstudio/express/visualc/download/
visual c++ 2008 express
http://www.microsoft.com/express/Downloads/#2008-Visual-CPP
visual c++ 2010 express
http://www.microsoft.com/express/Downloads/#2010-Visual-CPP




설치후 30일 이내에 간단한 등록만 하면 기간 제한 없이 무료로 사용할 수 있다.
등록 절차 http://www.microsoft.com/express/support/regins/

대학생이라면, 대학교 e-mail계정을 통해 Dreamspark로 최신 visual studio를 받을 수 있다.
https://www.dreamspark.com/default.aspx



2. code::blocks
http://www.codeblocks.org/downloads





3. dev-cpp
http://www.bloodshed.net/dev/devcpp.html
http://sourceforge.net/projects/dev-cpp/





4. sharp develop
http://www.icsharpcode.net/OpenSource/SD/Download/





5. 기타

이클립스
http://www.eclipse.org/downloads/

넷빈
http://netbeans.org/downloads/index.html


 

Posted by Нуеоп

명령모드에서

gg=G

'linux' 카테고리의 다른 글

ftp 보안  (0) 2012.12.19
서버 명령어  (0) 2012.12.12
ubuntu 우분투 한글  (0) 2012.08.16
vim suspend ctrl-z ^z  (0) 2012.08.03
vim 소스코드를 html로 변환하기  (0) 2011.11.01
Posted by Нуеоп

명령모드에서

:so $VIMRUNTIME/syntax/2html.vim

'linux' 카테고리의 다른 글

ftp 보안  (0) 2012.12.19
서버 명령어  (0) 2012.12.12
ubuntu 우분투 한글  (0) 2012.08.16
vim suspend ctrl-z ^z  (0) 2012.08.03
vim 소스코드 자동정렬  (0) 2011.11.01
Posted by Нуеоп
2011. 10. 31. 18:27

'windows' 카테고리의 다른 글

_CrtIsValidHeapPointer() 관련 오류 발생시 해결방법  (0) 2011.11.01
코어수 알아내기  (0) 2011.10.31
Posted by Нуеоп
2011. 10. 31. 17:30

프로세서 코어수를 알아내는 방법

GetLogicalProcessorInformation() 함수를 이용


#include <windows.h>
#include <malloc.h>    
#include <stdio.h>
#include <tchar.h>

DWORD CountSetBits(ULONG_PTR bitMask)
{
	DWORD LSHIFT = sizeof(ULONG_PTR)*8 - 1;
	DWORD bitSetCount = 0;
	ULONG_PTR bitTest = (ULONG_PTR)1 << LSHIFT;    
	DWORD i;

	for (i = 0; i <= LSHIFT; ++i) {
		bitSetCount += ((bitMask & bitTest)?1:0);
		bitTest/=2;
	}

	return bitSetCount;
}


int getProcessorNumber(int *core, int *logical){
	typedef BOOL (WINAPI *LPFN_GLPI)(PSYSTEM_LOGICAL_PROCESSOR_INFORMATION, PDWORD);
	LPFN_GLPI glpi;

	DWORD returnLength = 0;
	DWORD logicalProcessorCount = 0;
	DWORD numaNodeCount = 0;
	DWORD processorCoreCount = 0;
	DWORD processorL1CacheCount = 0;
	DWORD processorL2CacheCount = 0;
	DWORD processorL3CacheCount = 0;
	DWORD processorPackageCount = 0;
	DWORD byteOffset = 0;
	PCACHE_DESCRIPTOR Cache;

	PSYSTEM_LOGICAL_PROCESSOR_INFORMATION buffer = NULL;
	PSYSTEM_LOGICAL_PROCESSOR_INFORMATION ptr = NULL;

	*core = *logical = 0;

	glpi = (LPFN_GLPI) GetProcAddress( GetModuleHandle("kernel32"),"GetLogicalProcessorInformation");
	if (NULL == glpi) {
		printf("\nGetLogicalProcessorInformation is not supported.\n");
		return (0);
	}

	DWORD rc = glpi(buffer, &returnLength);
	if (FALSE == rc) {
		if (GetLastError() == ERROR_INSUFFICIENT_BUFFER) {
			if (buffer) 
				free(buffer);

			buffer = (PSYSTEM_LOGICAL_PROCESSOR_INFORMATION)malloc(returnLength);
		}
		rc = glpi(buffer, &returnLength);
	}
	if (FALSE == rc) {
		printf("\nError: GetLogicalProcessorInformation() returned false\n");
		return (0);
	}

	ptr = buffer;
	while( byteOffset < returnLength ){
		switch (ptr->Relationship) 
		{
		case RelationNumaNode:
			numaNodeCount++;
			break;

		case RelationProcessorCore:
			processorCoreCount++;
			logicalProcessorCount += CountSetBits(ptr->ProcessorMask);
			break;

		case RelationCache:
			Cache = &ptr->Cache;
			if (Cache->Level == 1) {
				processorL1CacheCount++;
			}
			else if (Cache->Level == 2) {
				processorL2CacheCount++;
			}
			else if (Cache->Level == 3) {
				processorL3CacheCount++;
			}
			break;

		case RelationProcessorPackage:
			processorPackageCount++;
			break;

		default:
			tprintf("\nError: Unsupported LOGICAL_PROCESSOR_RELATIONSHIP value.\n");
			break;
		}
		byteOffset += sizeof(SYSTEM_LOGICAL_PROCESSOR_INFORMATION);
		ptr++;
	}
	free(buffer);
	*core = processorCoreCount;
	*logical = logicalProcessorCount;
	return 1;
}

int main ()
{
	int core, logical;
	getProcessorNumber(&core, &logical);
	printf("Processor Core : %d\n", core);
	printf("Logical Processor : %d\n", logical);

	return 0;
}


소스파일



실행 결과



참고자료

http://msdn.microsoft.com/en-us/library/windows/desktop/ms686694(v=vs.85).aspx
http://msdn.microsoft.com/en-us/library/ms683194%28VS.85%29.aspx
http://msdn.microsoft.com/en-us/library/system.environment.processorcount.aspx

'windows' 카테고리의 다른 글

_CrtIsValidHeapPointer() 관련 오류 발생시 해결방법  (0) 2011.11.01
컴파일 옵션 종류  (0) 2011.10.31
Posted by Нуеоп
이전버튼 1 2 3 4 5 이전버튼