[アルゴリズム] クイックソートの実装(C言語編)

2017年2月20日

C言語 テクノロジー プログラミング 特集

t f B! P L
C言語ってオワコンなんでしょうか? エンジニアと話しているとどうしてもそういう流れの話になってしまいます。 Objective-Cも今ではswiftにほぼ変わっていて、Appleにも見放されてる感が否めません。 個人的には、スピードの優位点がダントツであるので、好きな言語の一つなんですけどね。 とりあえず、クイックソートのC言語書いてみました。

ソース

#include <stdio.h> int mid(int x , int y , int z){ if (x < y) { if (y < z){return y;} else if (z < x){return x;} else{return z;}} else { if (z < y){return y;} else if (x < z){return x;} else{return z;}} } void quickSort(int *numbers , int begin , int end){ if(end - begin > 0){ // 左辺と右辺の開始位置を定義 int left = begin; int right = end; // ピボット(中央の値) int mid_num = (left + ((right - left)/2)); int pivot = mid(numbers[left] , numbers[mid_num] , numbers[right]); // ソート処理実行(pivotが交差するまで続行) while(1){ // 左辺のpivotよりも大きい値見つける while(numbers[left] < pivot){left++;} // 右辺のpivotよりも小さい値をみつける while(numbers[right] > pivot){right--;} //pivotが交差したら終了 if(left >= right){break;} // 値の入れ替え処理 int tmp = numbers[left]; numbers[left] = numbers[right]; numbers[right] = tmp; // 繰り返し対応 left++; right--; } // pivotの左辺のソート処理 if(begin < left){quickSort(numbers , begin , left-1);} // pivotの右辺のソート処理 if(right < end){quickSort(numbers , right+1 , end);} } } 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]); quickSort(numbers , 0 , numbersCount -1); arrayView(numbers , numbersCount); return 0; }

実行

$ gcc -o quickSort quickSort.c $ ./quickSort 2 7 8 10 12 13 16

解説

「Segmentation fault: 11」エラーが出たら・・・

今回のプログラムを書いていた時に、42行目、45行目の値で、+1,-1を追加することで解決したんですが、この演算を加えないと、無限ループに陥って「Segmentation fault: 11」エラーが発生していました。 不思議なことに、他の言語では、この演算入れなくても正常に動作できたので、正直何が違うか理解できないまま、終了してしまいました。 単純に考えてみると、同じ値で無限ループするという内容なので、1ずつシフトする記述なんですが、C言語の方が厳密に処理されているんでしょうね。 この真相については、別途研究してみようと思います。

関数のreturn扱い

C言語は関数の戻り値に関しても厳密に管理されている言語です。 他のWEB系ゆるゆる言語であれば、関数の途中で処理しなくていい状態になったら、空やその状態でreturnすることで関数処理自体を抜けられるんですが、 C言語は、厳密に値を戻さなければ行けないし、その戻り値をちゃんと受け取らなければいけません。 更にいうと、受け取った値をちゃんと利用されていないとエラーが出る場合があります。 ゆるゆる言語との差は、こうした事を厳密に設計しなければいけないという事ですね。 今回は、無駄なreturnを無くし、if文で処理判定を行い関数内で対応しました。 ※詳しくは多言語と比較してみてください。

wikipediaにソース載ってた・・・orz

クイックソートの解説も詳細にかかれている上、C言語のみソースコードが載っていました。 https://ja.wikipedia.org/wiki/クイックソート ほとんど同じソースコードだったんですが、独自の配列変数を作って行っている部分が僕の稚拙なソースコードよりもイケてるな〜って感じました。 こういう部分から、ソースコードスキルってアップしていくんですね。 ちなみに、下記にコピっておきました。参考までにどうぞ。 typedef int value_type; /* ソートするキーの型 */ /* x, y, z の中間値を返す */ value_type med3(value_type x, value_type y, value_type z) { if (x < y) { if (y < z) return y; else if (z < x) return x; else return z; } else { if (z < y) return y; else if (x < z) return x; else return z; } } /* クイックソート * a : ソートする配列 * left : ソートするデータの開始位置 * right : ソートするデータの終了位置 */ void quicksort(value_type a[], int left, int right) { if (left < right) { int i = left, j = right; value_type tmp, pivot = med3(a[i], a[i + (j - i) / 2], a[j]); /* (i+j)/2 ではオーバーフローしてしまう */ while (1) { /* a[] を pivot 以上と以下の集まりに分割する */ while (a[i] < pivot) i++; /* a[i] >= pivot となる位置を検索 */ while (pivot < a[j]) j--; /* a[j] <= pivot となる位置を検索 */ if (i >= j) break; tmp = a[i]; a[i] = a[j]; a[j] = tmp; /* a[i], a[j] を交換 */ i++; j--; } quicksort(a, left, i - 1); /* 分割した左を再帰的にソート */ quicksort(a, j + 1, right); /* 分割した右を再帰的にソート */ } }

参考リンク

クイックソート

解説 Javascript PHP Python Shell Awk C言語

アルゴリズム過去記事

http://wordpress.ideacompo.com/?cat=562&tag=Algorithm

このブログを検索

プロフィール

自分の写真
町田市, 東京都, Japan
プログラミングとサーバーを心の底から楽しむクリエーターです。 経営者であり、開発者でもありますが、得意としているのは、アイデア創出です。

ブログ アーカイブ

QooQ