はじめに
去年の夏休みにソートアルゴリズムの復習をしました。
その時の痕跡をブログに投下しておきます。
ソートアルゴリズムそのものについては簡単な説明しかしていませんが、参考程度に。詳しくはWikipediaで。
ソースコード
各ソートが関数になっています。
基本的に同じ形で使えるようにしたので、良かったら使ってください。
見出しのカッコ書きがソースコードで定義されている関数名です。この名前で呼び出す事ができます。
スワップ関数（swap）
いくつかのソートで必要になる関数なので、この記事のソートプログラムをコピーする場合にはこの関数も定義しておいてください。
この関数は引数にポインタで与えられた二変数の値を交換します。
//ポインタスワップ
void swap(int *a,int *b){
int temp = *a; //一時格納
//スワップ
*a = *b;
*b = temp;
}
クイックソート関数（quick）
実用する上で最も効率が良いとされているソートアルゴリズムで、基準を設けて要素を大小のグループに分けるという動作を繰り返す（グループに分けてさらにその中でもグループに分けて…と繰り返す）ことで並び替えをしていく方法です。
大学の課題でも出やすいと思います。とりあえずコピペで提出してしまえばOK！
//中央値探索(クイックソート内部で利用)
int mid(int x, int y, int z){
//3点の中央値を返す
if((x < y && x > z) || (x < z && x > y)){ //xが中央値
return x;
}else if((x < y && y < z) || (x > y && y > z)){ //yが中央値
return y;
}else{ //xでもyでもない場合(zが中央値ではない場合も含む)
return z;
}
}
//クイックソート(クイックソート内部で利用)
void quick(int sort[],int top,int last){
if(top < last){ //再帰の終了条件
int i = top, j = last; //内部で利用するため
int pivot = mid(sort[i],sort[i+(j-i)/2],sort[i]); //３点の中央値をピボットに指定
//ループ処理(1度のループで2分割する)
while(1){
//pivotより大きな値を先頭から探す
while(sort[i] < pivot){
i++; //探索位置をずらす
}
//pivotより小さな値を最後から探す
while(sort[j] > pivot){
j--; //探索位置をずらす
}
//交換する必要がなくなればループを抜ける(iとjの位置関係が正順ならばループを抜ける)
if(i > j-1){
break;
}
//スワップ
swap(&sort[i],&sort[j]);
//スワップを行なった場合範囲を一つずつ狭めて(スワップした場所を探索しないで)再探索
i++;
j--;
}
//2分割した範囲をそれぞれで更に分割する(再帰的に繰り返す)
quick(sort,top,i-1);
quick(sort,j+1,last);
}
}
//クイックソート(他のソートと同じように入力するため)
void quick(int sort[],int array_num){ //sort[]は配列,array_numは要素数
quick(sort,0,array_num-1); //クイックソート
}
挿入ソート関数（insert）
隣り合った要素を比べて順番にソートする方法で、ソートが終わっている部分に対して後ろにある要素をどこに入れるのかを探るというアルゴリズムです。
//挿入ソート
void insert(int sort[],int array_num){ //sort[]は配列,array_numは要素数
//左からソート
for(int i = 0; i < array_num-1; i++){
int temp = sort[i+1]; //挿入する要素を保管
//比較(1回目)
if(sort[i] > temp){
int j = i; //要素番号のコピー
//挿入場所の探索,挿入場所を空ける(挿入地点より右の整列要素を1つずつずらす)
do{
sort[j+1] = sort[j]; //要素を右にずらす
j--; //調べる要素を左にずらす
}while(j+1 > 0 && sort[j] > temp); //継続条件,整列済要素に挿入する要素より値の大きい要素が存在
sort[j+1] = temp; //挿入
}
}
}
シェルソート関数（shell）
注意：この関数では外部ライブラリ「cmath」を使っています。
挿入ソートを改良してできたソートアルゴリズムです。
間隔hを空けて比較を行い。次は間隔hを小さくして比較を行い。…と繰り返して、最終的には隣り合った要素と比較を行うことで並び替える方法です。
#include <cmath>
//シェルソート
void shell(int sort[],int array_num){ //sort[]は配列,array_numは要素数
int i = 0; //間隔用変数
//適切な間隔の探索
while((pow(3,i)-1)/2 < array_num){
i++;
}
int h = (pow(3,i)-1)/2; //間隔の初期値(要素数より大きい,以前のコムソートに似せて作るため)
bool flag = false; //間隔1の時の判定用
while(h > 1 || flag){
//間隔の変更
if(h > 1){
h = (h-1)/3;
}
//フラグの初期化
flag = false;
//間隔でグループ分け
for(int i = 0; i < array_num-h; i++){
//グループ毎に挿入ソートの実施
int temp = sort[i+h];
//比較(1回目)
if(sort[i] > temp){
int j = i; //要素番号のコピー
//挿入場所の探索,挿入場所を空ける(挿入地点より右の整列要素を1つずつずらす)
do{
sort[j+h] = sort[j]; //要素を間隔分右にずらす
j -= h; //調べる要素を左にずらす
}while(j+h > 0 && sort[j] > temp); //継続条件,整列済要素に挿入する要素より値の大きい要素が存在
sort[j+h] = temp; //挿入
flag = true;
}
}
}
}
バブルソート関数（bubble）
このソートはとてもシンプルなアルゴリズムです。
隣り合った要素を比較して入れ替えるという動作を要素数-1回繰り返すというアルゴリズムです。
//バブルソート
void bubble(int sort[],int array_num){//sort[]は配列,array_numは要素数
//N-1回操作
for(int i = 0; i < array_num-1; i++){
//右からソート（左からやると変数が1つ増える）
for(int j = array_num-1; i < j; j--){
if(sort[j] < sort[j-1]){ //左の数値が大きければスワップ（交換）
//スワップ
swap(&sort[j],&sort[j-1]);
}
}
}
}
コムソート関数（comb）
バブルソートを改良したソートアルゴリズムです。
間隔を開けて要素の比較を行って、その感覚を徐々に減らしていく事で並び替える方法です。
//コムソート
void comb(int sort[],int array_num){//sort[]は配列,array_numは要素数
int h = array_num; //間隔用変数
bool flag = false; //間隔1の時の変更フラグ
while(h > 1 || flag){
//間隔の変更
if(h > 1){
h /= 1.3;
}
//フラグを初期化
flag = false;
//比較
for(int i = 0; i < array_num-h; i++){
//左からソート
if(sort[i] > sort[i+h]){
//スワップ
swap(&sort[i],&sort[i+h]);
flag = true; //フラグの変更
}
}
}
}
シェーカーソート関数（shaker）
バブルソートを改良したソートアルゴリズムです。
バブルソートでは毎度片方向からのみ探索していたのを、往復するようにして探索する方法です。
//シェーカーソート
void shaker(int sort[],int array_num){//sort[]は配列,array_numは要素数
int top = 0,bottom = array_num-1; //ソートの開始位置と終了位置
while(top != bottom){ //開始位置と終了位置が一致すればソート終了
int w_swap = top; //スワップ位置
//左からソート
for(int i = top; i < bottom; i++){
//右のデータより大きければ交換
if(sort[i] > sort[i+1]){
//スワップ
swap(&sort[i],&sort[i+1]);
w_swap = i;
}
}
bottom = w_swap;
w_swap = bottom;
//右からソート
for(int i = bottom; i > top; i--){
//左のデータより小さければ交換
if(sort[i] < sort[i-1]){
//スワップ
swap(&sort[i],&sort[i-1]);
w_swap = i;
}
}
top = w_swap;
}
}
ノームソート関数（gnome）
挿入ソートとバブルソートを混ぜたようなアルゴリズムです。
後ろの要素と比較して入れ替えていくと、入れ替えた時のみ前に戻って比較を行右ことで並び替える方法です。
//ノームソート
void gnome(int sort[],int array_num){ //sort[]は配列,array_numは要素数
int top = 0; //比較元
//左からソート
while(top < array_num-1){
//比較
if(sort[top] > sort[top+1]){
//スワップ
swap(&sort[top],&sort[top+1]);
//前に戻る
if(top > 0){
top--;
}
}else{
//次に進む
top++;
}
}
}
選択ソート関数（selection）
誰でも思いつきそうな単純なソートアルゴリズムです。
全ての要素から最も小さい要素を順番に抜き出して先頭から順に並べていくという方法です。
//選択ソート
void selection(int sort[],int array_num){ //sort[]は配列,array_numは要素数
//左から順にソート
for(int i = 0; i < array_num-1; i++){
int min = i; //最小値,初期値は未定の部分の先頭
//未定の部分の先頭から最後までを探索
for(int j = i+1; j < array_num; j++){
//暫定の最小値より小さい数値があれば変更
if(sort[j] < sort[min]){
min = j;
}
}
//スワップ（この時点で最小値の要素は判別済）
swap(&sort[i],&sort[min]);
}
}
配列を表示する関数
特に必要はないですが、ソート関数と同じように使う事ができます。
//配列表示
void show_sort(int sort[],int array_num){ //sort[]は配列,array_numは要素数
for(int i = 0; i < array_num; i++){
std::cout << sort[i] << ' '; //標準出力
}
std::cout << std::endl; //標準出力
}
使い方
例えば、選択ソートを実装したい場合。
上にあるソースコードからスワップ関数と選択ソート関数をコピペして次のように選択ソート関数の呼び出しをします。
//クイックソート selection(配列,配列の要素数);
具体的な例を挙げると。次のようになります。
#include <iostream>
/*
コピペする。
*/
int main(){
//配列作成
int sort[5] = {0,4,2,3,1}; //配列
//クイックソート
selection(sort,5);
for(int i = 0; i < 5; i++){
std::cout << sort[i] << ' '; //標準出力
}
std::cout << std::endl;
return 0;
}
最後に
ソートアルゴリズムの種類自体はまだまだたくさんあるので、もしかすると次の長期休暇の時に更新するかもしれません。
個人的にはソートを理解する必要はあれど、実装する必要はないと思います。ライブラリとかに関数が存在しますからね。
コメント