Skip to content

Instantly share code, notes, and snippets.

@albow-net albow-net/sort_test.cpp
Last active Aug 22, 2017

Embed
What would you like to do?
再帰型マージソート
#include <vector>
#include <string>
#include <iostream>
#include <ctime>
class Person {
private:
int id;
std::string name;
public:
Person( int id, const char* name ) {
this->id = id;
this->name = name;
}
Person() {
this->id = 0;
this->name = "";
}
int get_id() { return id; };
std::string get_name() { return name; };
bool operator< ( Person &p2 ) {
return this->name < p2.name;
};
Person &operator=( const Person &p ) {
this->id = p.id;
this->name = p.name;
return *this;
}
};
template<class T> class sort {
T *buf;
std::vector<T> *array;
public:
Sort() {
};
private:
// ソート済みの2つの領域 (index_b〜index_c-1 と index_c〜index_e) をマージする関数
void merge( int index_b, int index_c, int index_e ) {
// 2つの領域が1つずつしかない場合は2つの大小関係だけ見る
if ( index_b + 1 == index_e ) {
if ( (*array)[index_e] < (*array)[index_b] ) {
auto tmp = (*array)[index_e];
(*array)[index_e] = (*array)[index_b];
(*array)[index_b] = tmp;
}
return;
}
// index_1とindex_2を動かしながら,小さい方を順次index_bufへ書き込む
int index_1 = index_b;
int index_2 = index_c + 1;
int index_buf = index_b;
while ( true ) {
if ( (*array)[index_1] < (*array)[index_2] ) {
buf[index_buf++] = (*array)[index_1];
// index_1が最後まで到達したらindex_2側を順番に見て終了
if ( index_1++ == index_c ) {
while ( index_2 <= index_e ) {
buf[index_buf++] = (*array)[index_2++];
}
break;
}
} else {
buf[index_buf++] = (*array)[index_2];
// index_2が最後まで到達したらindex_1側を順番に見て終了
if ( index_2++ == index_e ) {
while ( index_1 <= index_c ) {
buf[index_buf++] = (*array)[index_1++];
}
break;
}
}
}
// バッファから元配列へコピー
for ( int i = index_b; i <= index_e; i++ ) {
(*array)[i] = buf[i];
}
return;
};
// 再帰的に呼び出す関数
void merge_sort( int index_b, int index_e ) {
int index_c = ( index_b + index_e ) / 2;
// 左側をソート
if ( index_b != index_c )
merge_sort( index_b, index_c );
// 右側をソート
if ( (index_c + 1) != index_e )
merge_sort( index_c + 1, index_e );
// 左と右をマージ
merge( index_b, index_c, index_e );
return;
};
public:
// mainから呼ぶソート関数
void merge_sort( std::vector<T> *vec ) {
// ソート対象の配列
this->array = vec;
// マージ中のソート結果を一時的に記憶するバッファ
this->buf = new T[ vec->size() ];
// マージソート
merge_sort( 0, vec->size() - 1 );
delete [] buf;
};
};
int main(int argc, char *argv[]) {
// 時間測定のための変数
struct timespec tp_start, tp_end;
/******** 標準入力からデータを読み込み ********/
std::vector<Person> vec_people;
int id;
std::string name;
clock_gettime(CLOCK_REALTIME, &tp_start);
while ( std::cin >> id && std::cin >> name ) {
vec_people.push_back( Person( id, name.c_str() ) );
}
clock_gettime(CLOCK_REALTIME, &tp_end);
std::cout << "reading : " << (double(tp_end.tv_sec - tp_start.tv_sec) + double(tp_end.tv_nsec - tp_start.tv_nsec) / 1000000000.0) << std::endl;
/******** 読み込んだデータをソート ********/
Sort<Person> sort;
clock_gettime(CLOCK_REALTIME, &tp_start);
sort.merge_sort( &vec_people );
clock_gettime(CLOCK_REALTIME, &tp_end);
std::cout << "sorting : " << (double(tp_end.tv_sec - tp_start.tv_sec) + double(tp_end.tv_nsec - tp_start.tv_nsec) / 1000000000.0) << std::endl;
// ソート済み確認
for ( int i = 1; i < vec_people.size(); i++ ) {
if ( vec_people[i] < vec_people[i-1] ) {
std::cerr << "ERROR" << std::endl;
}
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.