C++はじめました
ある講義で諸々あって早急にC++を使えないといけない状態になったので
ともかく何か書いてみた
同じタイミングで別の講義でソートにおける速さを比較せよって割と軽めの課題が出たので可能な限りC++を意識して書いてみた。
内容的にオブジェクト指向を使わなくてもなんとかなってしまったのでその辺は近々みっちりやりたいところ。
バイナリソートについて
- その数の存在を保存する配列Aを容易する
- 乱数の先頭から内容を確認し、それに対応する配列Aの箇所をfalse->trueに変更
- 乱数の最後まで確認が終了したら、配列Aのtrueとなってる箇所に対応する数値を出力
使用するメモリ領域も少なく処理も軽いが、重複する値の情報が消えてしまう。
リソースに制限がある中で、電話番号の並べ替えなど限られた状況でのみ威力を発揮する。
引っかかった点
- bool配列は最初に全部falseで埋める必要がある
- 初期状態だとtrueとfalseが混在しており正確なソート結果が出ない
- 参照,ポインタ関連
- 苦手を引きずりまくってるので一回基礎からやり直したいところ
実装
// // main.cpp // SysEngHW1 // // Created by zhuravlik on 2016/10/12. // Copyright © 2016年 zhuravlik. All rights reserved. // #include <iostream> #include <time.h> #include <string.h> #include <stdlib.h> #define NUM_OF_RANDS 10 #define MAX_RANDS 15 using namespace std; inline void initRand(){ srand((unsigned int)time(NULL)); } void makeRandArray(int *init){ initRand(); int temp[MAX_RANDS + 1]; int randKey, randNum = MAX_RANDS + 1; for(int i = 0; i <= MAX_RANDS; i++) temp[i] = i; cout << "-----Init Array-----" << endl; for(int i = 0; i < NUM_OF_RANDS; i++){ randKey = rand() % randNum; *init = temp[randKey]; temp[randKey] = temp[randNum - 1]; --randNum; cout << *init << " "; ++init; } cout << "\n-----Init Array-----\n" << endl; } void binarySort(int *result){ cout << "-----Binary Sort-----" << endl; clock_t start = clock(); int sorted[NUM_OF_RANDS]; int *temp = result; bool presence[MAX_RANDS + 1] = {0}; //cout << "-----init-----" << endl; for(int i = 0; i < NUM_OF_RANDS; i++){ //cout << *result << " "; presence[*result] = true; ++result; } cout << "----result----" << endl; //for(int i = 0; i <= MAX_RANDS; i++) cout << i << " : " << presence[i] << endl; int counter = 0; for(int i = 0; i <= MAX_RANDS; i++){ if(presence[i] == true){ sorted[counter] = i; cout << i << " "; counter++; } } cout << "\n"; clock_t end = clock(); cout << "duration = " << (double)(end - start) / CLOCKS_PER_SEC << "sec." << endl; cout << "-----Binary Sort-----" << endl; for(int i = 0; i < NUM_OF_RANDS; i++){ *temp = sorted[i]; ++temp; } } int compareInt(const void *a, const void *b){ return *(int*)a - *(int*)b; } int main(int argc, const char * argv[]) { if(NUM_OF_RANDS > MAX_RANDS){ cout << "Error! Plz check NUM_OF_RANDS and MAX_RANDS" << endl; return 1; } int init[NUM_OF_RANDS], res1[NUM_OF_RANDS], res2[NUM_OF_RANDS]; makeRandArray(init); memcpy(res1, init, sizeof(init)); memcpy(res2, init, sizeof(init)); binarySort(init); cout << "\n-----Quick Sort-----" << endl; clock_t start = clock(); qsort(res2, NUM_OF_RANDS, sizeof(int), compareInt); cout << "----result----" << endl; for(int i = 0; i < NUM_OF_RANDS; i++) cout << res2[i] << " "; cout << "\n"; clock_t end = clock(); cout << "duration = " << (double)(end - start) / CLOCKS_PER_SEC << "sec." << endl; cout << "-----Quick Sort-----" << endl; return 0; }
実行結果
-----Init Array----- 12 11 15 6 2 4 1 5 3 13 -----Init Array----- -----Binary Sort----- ----result---- 1 2 3 4 5 6 11 12 13 15 duration = 2.2e-05sec. -----Binary Sort----- -----Quick Sort----- ----result---- 1 2 3 4 5 6 11 12 13 15 duration = 2.1e-05sec. -----Quick Sort----- Program ended with exit code: 0