[알고리즘] 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;
}