IT 취미생활.  
Front Page
Tag | Location | Media | Guestbook | Admin   
 
'알고리즘'에 해당하는 글(4)
2008.10.18   [알고리즘] Insertion Sort(삽입정렬)
2008.10.17   [알고리즘] Priority Queue (우선 순위큐)
2008.10.17   [알고리즘] Selection Sort
2008.10.16   [알고리즘] BubbleSort


[알고리즘] Insertion Sort(삽입정렬)
간단하게 작성한 삽입 정렬입니다.


간단하게 원리를 설명드리면, 배열에 index는 1에서 부터 시작해서(1 <= x < N ) N까지
정렬을 합니다.  index한 녀석을 집어 넣을 위치를 찾는 것입니다.

코드는 따로 설명 드리지 않겠습니다.

void InsertSort( int *_arrayBuffer, int _bufferSize )
{
  for( int i = 1; i < _bufferSize; i++ )
  {
    int insertionValue= _arrayBuffer[ i ];
    int nInsertPosition = i;
    while( _arrayBuffer[nInsertPosition-1] > insertionValue && nInsertPosition > 0 )
    {
      _arrayBuffer[nInsertPosition ] = _arrayBuffer[ nInsertPosition - 1 ];
      nInsertPosition--;
    }
    _arrayBuffer[ nInsertPosition ] = insertionValue;
  }
}

배열안에 값들이 정렬이 이루어져 있으면 N 에 대한 성능을 가질 수 있다고 하는군요.

그럼 고운하루 되세요.



[알고리즘] Priority Queue (우선 순위큐)

Project에 적용하기 위해서 작성한 Heap을 기반으로한 Priority Queue Class 입니다.
MultiThread-Safe 하긴한데 performance가 따라 줄지는 모르겟습니다.
성능 개선을 위한 부분 있다면 언제든지 코멘트 부탁 드립니다 ㅜㅜ;;;;

딱 보면 아시겠지만, 생각하는 프로그래머에 Code를 그대로 옮겨 놓은 듯 합니다.
^0^ 그럼 고운하루 되세요.

template< class T >
class CPriQueue
{
private:
 int m_nCurIndex, m_nMaxsize;
 CRITICAL_SECTION m_cs;
 T *m_pTemplateArray;

 void swap( int i, int j )
 {  
  T t = m_pTemplateArray[i];
  m_pTemplateArray[i] = m_pTemplateArray[j];
  m_pTemplateArray[j] = t;
 }

public:
 CPriQueue()
 {
  m_pTemplateArray = NULL;
  InitializeCriticalSection( &m_cs );
 }

 ~CPriQueue()
 {
  FlushQueue();
  delete []m_pTemplateArray;
  DeleteCriticalSection( &m_cs );
  m_pTemplateArray = NULL;
 }

 void SetQueueSize( unsigned int QueueSize )
 {
  if( QueueSize <= 0 )
   QueueSize = 1;

  m_pTemplateArray = new T[ QueueSize +1 ];
  if( m_pTemplateArray )
  {
   m_nMaxsize = QueueSize;
   m_nCurIndex = 0;
  }
 }

 void Push( T t )
 {
  if( m_nCurIndex >= m_nMaxsize   )
  {
   FlushQueue();
   printf("******FULL Queue ******* ");
   return;
  }

  int nParentIndex;
  EnterCriticalSection( &m_cs );
  m_pTemplateArray[ ++m_nCurIndex ] = t;


  if(  m_nCurIndex >  1 && m_pTemplateArray[ nParentIndex = m_nCurIndex >> 1  ] > m_pTemplateArray[m_nCurIndex] )
  { 
   for ( int nCurrentIndex = m_nCurIndex;
    nCurrentIndex > 1 && m_pTemplateArray[ nParentIndex = nCurrentIndex >> 1  ] > m_pTemplateArray[nCurrentIndex];
    nCurrentIndex = nParentIndex )
   {
    swap( nParentIndex, nCurrentIndex );
   }
  }
  LeaveCriticalSection( &m_cs );
 }


 T Pop()
 {
  if ( m_nCurIndex == 0 )
  {
   return 0;
  }

  int nChild = 0;
  EnterCriticalSection( &m_cs );
  T  t = m_pTemplateArray[ 1 ];
  m_pTemplateArray[ 1 ] = m_pTemplateArray[ m_nCurIndex-- ];

  for(  int i = 1; ( nChild =  i << 1 ) <= m_nCurIndex ; i = nChild )
  {
   if( nChild + 1 <= m_nCurIndex && m_pTemplateArray[ nChild + 1 ] < m_pTemplateArray[ nChild ] )
   {
    nChild++;
   }

   if( m_pTemplateArray[ i ] <= m_pTemplateArray[ nChild ]  )
   {
    break;
   }
   swap( nChild, i );
  }
  LeaveCriticalSection( &m_cs);
  return t;
 }
 
 void FlushQueue()
 {
  UINT nfreameCount = 0;
  T tFrame  = NULL;
  while( tFrame = Pop() )
  {
   delete tFrame;
   tFrame  = NULL;
   nfreameCount++;
  }
  m_nCurIndex = 0;
  printf("******Flush Queue *******  :: %d \n", nfreameCount );
 }
};



[알고리즘] Selection Sort

프로그래밍 불여일타!!의 프로젝트의 일환으로, 퇴근후 배깔고 하는 알고리즘 공부를 시작!!
그 결과물로 간단 간단한 알고리즘을 작성하고, Blog에 올리기로 했습니다.

오늘은 간단하게 Selection Sort를 만들어 보았습니다.

* 원리는 : 총 1...n개의 정렬 되지 않은 요소에서, 첫번째 놈을 가져다가 가장 작은 값을
              가진다라 가정 하고  나머지 n-1개와 비교를 하게 합니다. 그래서 그중 가장
              작은 녀석을 기억 하고 있다가, 1번째 자리와 바꿉니다. 그리고 index을 하나 더
              증가 해서 두번째 요소를 가지고  n-2 만큼 loop를 돌아서 다시 최소값을 찾고
              바꿔 줍니다. 이렇게 반복하면 정렬이 됩니다.( 사실 그림으로 보면 아무것도
              아닙니다. 그림은 귀찮아서 안그렸습니다.)

* 성능 :  O(N^2)

* 코드

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

void SelectionSort( int *_arrayBuffer, const unsigned int _arraySize )
{
     for( int i = 0; i < _arraySize; i++ )
     {
          int nMinIndex = i;
          for( int j = i + 1; j < _arraySize; j++ )
          {
               if( _arrayBuffer[j] < _arrayBuffer[nMinIndex] )
               {
                   nMinIndex = j;
               }
          }
          swap( _arrayBuffer[nMinIndex], _arrayBuffer[ i ] );
      }  
}


[알고리즘] BubbleSort

간단하게 Bubble Sort을 만들어 보았습니다.

정렬 방식은 Buffer 마지막에 가장 큰 값을 옮겨두고, 첫 번째 for loop의 index를 -- 하여
뒤에서 부터 큰 값들이 정렬되도록 하는 sorting 방법입니다.
알고리즘 효율은 O(N^2) 입니다.

Function 이름은 "한눈에 보이는 C 알고리즘"이라는 책에서 가져다 사용 했습니다. - 귀차니즘

프로그래밍의 왕도는 역시 불여일타!!!!





#include <cstdlib>
#include <iostream>

using namespace std;


#define MAX_SIZE 100

int NumberExit( int *_arrayBuffer, int _number, int _index)
{
    for( int i=1 ; i < _index; i++ )
    {
            if( _arrayBuffer[i] == _number )
            {
                return true;
            }
    }
    return false;
}

void MakeRendomNumber( int *_arrayBuffer )
{
     int nNum = 0;
     srand( (unsigned)time( NULL ) );
     _arrayBuffer[0] = MAX_SIZE;
     int i = 1;
     while( i < MAX_SIZE )
     {
            nNum = rand() % MAX_SIZE;
            if( false == NumberExit( _arrayBuffer, nNum, i ))
            {
                _arrayBuffer[i] = nNum;
                i++;
            }
     }
}

void DisplayBuffer( int *_arrayBuffer )
{
     for( int i = 0; i < MAX_SIZE; i ++ )
     {
          if( (i % 10) == 0 )
          {
              cout << "\n";
          }
          cout << _arrayBuffer[i] << "\t";
     }
     cout << "\n";
}


 

void BubbleSort( int *_arrayBuffer, const unsigned int _arraySize )
{
     for( int i = _arraySize - 1; i >= 0; i-- )
     {
          for( int j = 1; j <= i ; j++ )
          {
               if( _arrayBuffer[ j - 1 ] > _arrayBuffer[ j ] )
               {
                   int nDummy  = _arrayBuffer[ j - 1 ];
                   _arrayBuffer[ j - 1 ] = _arrayBuffer[ j ];
                   _arrayBuffer[ j ] = nDummy;
               }
          }
     }
}

int main(int argc, char *argv[])
{
    int Buffer[ MAX_SIZE ] = { 0 };
   
    MakeRendomNumber( Buffer );
    DisplayBuffer( Buffer );
    cout << "\n";
   
    BubbleSort( Buffer, MAX_SIZE );
    cout << "\n";
    DisplayBuffer( Buffer );
   
    system("PAUSE");
       
    return EXIT_SUCCESS;
}



BLOG main image
취미생활
 Notice
 Category
분류 전체보기 (191)
매일매일갱생 (83)
서버개발 (1)
임베디드개발 (12)
Programming (80)
Personal Projects (6)
유용한 프로그램 (0)
 TAGS
ISDB-T DVB Wince5.0 Dshow 1seg M480 warning Error Case English It MP3 음식 DVB-T 티스토리초대 debugging DirectShow project 서태지 Algorithm Windows Mobile6.0 티스토리 초대장 영어 이메일 미라지폰 isdbt C english email VC++ Linux 군대 퇴사 Brazil Java 개발자 Debug 벨소리 변경 spam mail C++ 출장 알고리즘
 Calendar
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
 Recent Entries
 Recent Comments
 Recent Trackbacks
 Archive
 Link Site
zextor
괴짜 프로그래머의 일상사~@@
Gag & Peace, and more..
Kazakhstan Almaty.......
Min-A
Sadgarret
Steve Yoon's log
가슴 뛰는 삶을 살아라
오스틴 파워
GUI sin
melanie parker_Lady
제레미의 TV 2.0 이야기..
 Visitor Statistics
Total :
Today :
Yesterday :
rss