独学でノートを並べ替える

  
  
  
  

   
   
   
   
#include <algorithm> 
   
   
   
   
#include <list> 
   
   
   
   
#include <vector> 
   
   
   
   
#include <iostream> 
   
   
   
   
#include <string> 
   
   
   
   
 
   
   
   
   
void InsertionSort( std::list< std::string > & ls ) ; 
   
   
   
   
void InsertAndKeepOrder( std::list< std::string > &ls, const std::string& str ) ;  
   
   
   
   
void SelectionSort( std::list< std::string > & ls) ; 
   
   
   
   
//void ShellSort( std::list< std::string> &ls ) ; 
   
   
   
   
void QuickSort( std::list< std::string > &ls ) ; 
   
   
   
   
void MergeSort( std::list< std::string > &ls ) ; 
   
   
   
   
void Print( const std::list< std::string > &ls ) ; 
   
   
   
   
 
   
   
   
   
int main( int argc, char* argv[] ) { 
   
   
   
   
 
   
   
   
   
  std::list< std::string > ls ; 
   
   
   
   
  ls.push_back( "zera" ) ; 
   
   
   
   
  ls.push_back( "b" ) ; 
   
   
   
   
  ls.push_back( "e" ) ; 
   
   
   
   
  ls.push_back( "a" ) ; 
   
   
   
   
  ls.push_back( "f" ) ; 
   
   
   
   
  ls.push_back( "go" ) ; 
   
   
   
   
  ls.push_back( "make" ) ; 
   
   
   
   
  ls.push_back( "hello" ) ; 
   
   
   
   
  ls.push_back( "alalalal" ) ; 
   
   
   
   
  ls.push_back( "sony" ) ; 
   
   
   
   
  ls.push_back( "apple" ) ; 
   
   
   
   
  ls.push_back( "yahoo" ) ; 
   
   
   
   
  ls.push_back( "google" ) ; 
   
   
   
   
  ls.push_back( "microsoft" ) ;  
   
   
   
   
 
   
   
   
   
  std::cout << "before sorting: " <<  std::endl ;  
   
   
   
   
  Print( ls ) ;  
   
   
   
   
 
   
   
   
   
  // InsertionSort( ls ) ; 
   
   
   
   
  // SelectionSort( ls ) ; 
   
   
   
   
  // ShellSort( ls ) ; 
   
   
   
   
  // std::sort( ls.begin(), ls.end() ) ; 
   
   
   
   
  // QuickSort( ls ) ; 
   
   
   
   
  MergeSort( ls ) ;  
   
   
   
   
   
   
   
   
   
  std::cout << "after sorting: " << std::endl ; 
   
   
   
   
  Print( ls ) ; 
   
   
   
   
   
   
   
   
   
  return 0 ; 
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
void InsertionSort( std::list< std::string > &ls ) { 
   
   
   
   
  std::list< std::string > temp ; 
   
   
   
   
  std::string s ; 
   
   
   
   
  for( std::list< std::string >::iterator it = ls.begin() ; it != ls.end() ; ++it ) { 
   
   
   
   
    s = (*it) ; 
   
   
   
   
    InsertAndKeepOrder( temp, s ) ; 
   
   
   
   
  } 
   
   
   
   
  ls = temp ;  
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
void InsertAndKeepOrder( std::list< std::string > &ls, const std::string& str ) { 
   
   
   
   
  std::list< std::string >::iterator it = ls.begin() ; 
   
   
   
   
  while( it != ls.end() && (*it) < str ) { 
   
   
   
   
    ++it ; 
   
   
   
   
  } 
   
   
   
   
  ls.insert( it, str ) ; 
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
void SelectionSort( std::list< std::string > &ls ) { 
   
   
   
   
  std::list< std::string>::iterator b = ls.begin() ; 
   
   
   
   
  std::list< std::string>::iterator smallest = ls.begin() ; 
   
   
   
   
  std::string tempSwap ; 
   
   
   
   
  std::list< std::string>::iterator it ; 
   
   
   
   
  while( b != ls.end() ) {  
   
   
   
   
    for( it = b ;  it != ls.end() ; ++it ) { 
   
   
   
   
      if( (*it) < (*smallest) ) { 
   
   
   
   
    smallest = it ; 
   
   
   
   
      } 
   
   
   
   
    } 
   
   
   
   
    //swap 
   
   
   
   
    tempSwap = *b ; 
   
   
   
   
    *b = *smallest ; 
   
   
   
   
    *smallest = tempSwap ; 
   
   
   
   
 
   
   
   
   
    smallest = (++b) ;  
   
   
   
   
  } 
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
// void ShellSort( std::list< std::string > &ls ) { 
   
   
   
   
//   int step ; 
   
   
   
   
//   std::list< std::string > temp ; 
   
   
   
   
//   unsigned int it ; 
   
   
   
   
//   unsigned int startPoint ; 
   
   
   
   
 
   
   
   
   
//   for( step = 5 ; step != -1 ; step -= 2 ) { 
   
   
   
   
//     for( int i = 0 ; i < step ; ++i ) { 
   
   
   
   
//       startPoint = i ; 
   
   
   
   
//       it = startPoint ; 
   
   
   
   
//       while( it < ls.size() ) { 
   
   
   
   
//  temp.push_back( ls[it] ) ; 
   
   
   
   
//  it += step ; 
   
   
   
   
//       } 
   
   
   
   
//       InsertionSort( temp ) ; 
   
   
   
   
 
   
   
   
   
//       it = startPoint ; 
   
   
   
   
//       for( unsigned int i = 0 ; i < temp.size() ; ++i ) { 
   
   
   
   
//  ls[ it ] = temp[ i ] ; 
   
   
   
   
//  it += step ; 
   
   
   
   
//       } 
   
   
   
   
//       temp.clear() ; 
   
   
   
   
//     } 
   
   
   
   
//   }             
   
   
   
   
// } 
   
   
   
   
 
   
   
   
   
void QuickSort( std::list< std::string > &ls ) { 
   
   
   
   
  if( ls.empty() or ( ls.size() == 1 ) ) { 
   
   
   
   
    return ; 
   
   
   
   
  } 
   
   
   
   
  std::list< std::string> result ; 
   
   
   
   
  std::string temp ; 
   
   
   
   
  std::string pivot = ls.front() ; 
   
   
   
   
  ls.pop_front() ;  
   
   
   
   
  std::list< std::string > subLeft ; 
   
   
   
   
  std::list< std::string > subRight ; 
   
   
   
   
  for( std::list< std::string >::iterator it = ls.begin() ; it != ls.end() ; ++it ) { 
   
   
   
   
    temp = (*it) ; 
   
   
   
   
    if( temp < pivot ) { 
   
   
   
   
      subLeft.push_back( temp ) ; 
   
   
   
   
    } 
   
   
   
   
    else { 
   
   
   
   
      subRight.push_back( temp ) ; 
   
   
   
   
    } 
   
   
   
   
  } 
   
   
   
   
  QuickSort( subLeft ) ; 
   
   
   
   
  QuickSort( subRight ) ; 
   
   
   
   
 
   
   
   
   
  //combine together 
   
   
   
   
  result.merge( subLeft ) ; 
   
   
   
   
  result.push_back( pivot ) ; 
   
   
   
   
  result.merge( subRight ) ; 
   
   
   
   
  ls = result ;  
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
void MergeSort( std::list< std::string > &ls ) { 
   
   
   
   
  if( ls.empty() or ( ls.size() == 1 ) ) { 
   
   
   
   
    return ; 
   
   
   
   
  } 
   
   
   
   
  std::vector< std::string > l( ls.begin(), ls.end() ) ;  
   
   
   
   
  unsigned int spiltter = l.size() / 2 ; 
   
   
   
   
  std::list< std::string> left ; 
   
   
   
   
  std::list< std::string> right ; 
   
   
   
   
  std::list< std::string> result ; 
   
   
   
   
  std::string temp ; 
   
   
   
   
  //devide 
   
   
   
   
  for( unsigned int i = 0 ; i < l.size() ; ++i ) { 
   
   
   
   
    temp = l[i] ; 
   
   
   
   
    if( i < spiltter ) { 
   
   
   
   
      left.push_back( temp ) ; 
   
   
   
   
    } 
   
   
   
   
    else { 
   
   
   
   
      right.push_back( temp ) ; 
   
   
   
   
    } 
   
   
   
   
  } 
   
   
   
   
  MergeSort( left ) ; 
   
   
   
   
  MergeSort( right ) ; 
   
   
   
   
 
   
   
   
   
  //now merge; 
   
   
   
   
  std::list< std::string>::iterator  leftIterator = left.begin() ; 
   
   
   
   
  std::list < std::string>::iterator rightIterator = right.begin() ; 
   
   
   
   
  while( leftIterator != left.end() and rightIterator != right.end() ) { 
   
   
   
   
    if( (*leftIterator) < (*rightIterator ) ) { 
   
   
   
   
      temp = (*leftIterator ) ; 
   
   
   
   
      ++leftIterator ;  
   
   
   
   
    } 
   
   
   
   
    else { 
   
   
   
   
      temp = (*rightIterator) ;  
   
   
   
   
      ++rightIterator ; 
   
   
   
   
    } 
   
   
   
   
    result.push_back( temp ) ;  
   
   
   
   
  } 
   
   
   
   
  if( leftIterator == left.end() ) { 
   
   
   
   
    std::list< std::string > tempList( rightIterator, right.end() ) ; 
   
   
   
   
    result.merge( tempList ) ;  
   
   
   
   
  } 
   
   
   
   
  if( rightIterator == right.end() ) { 
   
   
   
   
    std::list< std::string > tempList( leftIterator, left.end() ) ;  
   
   
   
   
    result.merge( tempList ) ; 
   
   
   
   
  } 
   
   
   
   
  ls = result ;  
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
void Print( const std::list< std::string > &ls ) { 
   
   
   
   
  for( std::list< std::string >::const_iterator it = ls.begin() ; it != ls.end() ; ++it ) { 
   
   
   
   
    std::cout << (*it) << std::endl ; 
   
   
   
   
  } 
   
   
   
   
}