[アルゴリズム] マージソートのプログラミング（C言語編）
マージソートでの難関な回になりましたが、なんとか乗り切りました。
解説を診てもらうと、四苦八苦した点がわかってもらえると思いますが、エンジニアで且つC言語を使わない人は今回の記事はおもろくないので、読み飛ばしてください。
C言語で少しトリッキーなやり方、または配列処理に困っている人に少しヒントになればいいかと思って取り組みました。
ソースコード
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
#include <stdio.h> int midPoint(int nums){ return (float) (nums / 2) + 0.5; } int setMerge(int *numbers , int begin1 , int end1 , int begin2 , int end2){ while(end1 - begin1 >-1 || end2 - begin2 >-1){ if(end1 - begin1 == -1){ int tmp = numbers[begin2]; for(int i=begin2; i>begin1; i--){ numbers[i] = numbers[i-1]; } numbers[begin1] = tmp; begin1++; end1++; begin2 ++; } else if(end2 - begin2 == -1){ begin1 ++; } else if(numbers[begin1] > numbers[begin2]){ int tmp = numbers[begin2]; for(int i=begin2; i>begin1; i--){ numbers[i] = numbers[i-1]; } numbers[begin1] = tmp; begin1++; end1++; begin2 ++; } else{ begin1 ++; } } return 0; } int mergeSort(int *numbers , int begin , int end){ int range = end - begin; if(range == 1){ if(numbers[begin] > numbers[begin + 1]){ int tmp = numbers[begin]; numbers[begin] = numbers[begin+1]; numbers[begin+1]=tmp; } } else if(range > 1){ int midNum = midPoint(range); int begin1 = begin; int end1 = begin1 + midNum; int begin2 = end1+1; int end2 = end; mergeSort(numbers , begin1 , end1); mergeSort(numbers , begin2 , end2); setMerge(numbers , begin1 , end1 , begin2 , end2); } return 0; } void arrayView(int *nums , int numsCount){ for (int i=0; i<numsCount; i++) { printf("%d \n",nums[i]); } } int main(void){ int numbers[] = {10,2,12,7,16,8,13}; int numbersCount = (sizeof numbers / sizeof numbers[0]); mergeSort(numbers , 0 , numbersCount -1); arrayView(numbers , numbersCount); return 0; } |
実行
|
1 2 3 4 5 6 7 8 9 |
$ gcc -o mergisort_c mergeSort.c $ ./mergisort_c 2 7 8 10 12 13 16 |
解説
今回のアルゴリズムは、配列のやり取りが盛んに行う必要があったので、配列はポインタ、内部配列を切り取って行うやり取りは、配列内の開始番号〜終了番号をやり取りすることで対応しました。
２つの配列の結合
多言語では、個別に切り取った配列をマージする方式にしてましたが、C言語では、ポインタを使う事が優位性なので、開始番号と終了番号で行ったんですが、ここに一つ落とし穴があり、
フロートしては、配列２つの要素の先頭を大小比較して、小さい方を新規の配列に入れて、入れ込んだ配列は、shift処理をして、先頭の配列を削除するようにしていましたが、C言語では、終了番号-開始番号が0の物は処理をしないようにしていたんですが、配列が１つの場合、終了-開始番号は”0″になってしまうので、ずっと結果が崩れていました。
解決法としては、終了-開始番号を”-1″になった時点で配列を作業対象外にすることで、結果が正常になりました。
floatで処理して整数値でreturnする関数
下記部分の関数では、繰り上げ処理を行い整数を返す事を目的にしてますが、計算自体はfloatで行い、関数の返り値をintにすることでとりあえず、想定の結果が出ています。
型変換処理にはなると思いますが、C言語初心者は比較的つまずきやすいポイントなので、解説に入れておきました。
|
1 2 3 |
int midPoint(int nums){ return (float) (nums / 2) + 0.5; } |
配列のshift処理
今回特殊なやり方を行った、配列のpushとshiftですが、かなり直接的なやり方で記述しています。
まず、配列が２パターンあり、それが全体配列としては、連続している流れになっている事が条件です。
前方の配列と後方の配列になりますが、前方の配列をshiftする事は、begin1を１つシフトするだけなので、”begin++;”と処理するだけなんですが、後方配列は、前方配列全体の位置をずらす事になるので、for文で全ての値を１つ後ろにずらしています。
その時に、予め先頭にする後方配列の先頭値を保持しておき、最後に一番先頭に上書き、さらに、関係する基準値をインクリメントしています。
少しややこしいですが、C言語では、こうした流れが通常なんでしょうか？
|
1 2 3 4 5 6 7 8 |
int tmp = numbers[begin2]; for(int i=begin2; i>begin1; i--){ numbers[i] = numbers[i-1]; } numbers[begin1] = tmp; begin1++; end1++; begin2 ++; |
マージソート記事
解説
JavaScript
PHP
Python
Shell
AWK
C言語