二分挿入ソート

Question

###前提・実現したいこと
二分挿入ソート

###発生している問題・エラーメッセージ
エラーは特になし
正しくソートされない

###該当のソースコード
#include <stdio.h>

int binarySearch( int *a, int item, int left, int right ){

    if(left <= right)
            return (item > a[left])? (left+1) : left;

    int mid = (left + right)/2;

    if(item == a[mid])
            return mid+1;

    if(item > a[mid])
            return binarySearch(a, item, mid+1, right);
    return binarySearch(a, item, left, mid-1);

}

void insertionSort(int *a, int n){
int i, j, loc, selected;

    for(i=1; i < n; ++i){
            j = i - 1;
            selected = a[i];
            loc = binarySearch(a, selected, 0, j);

            while(j >= loc){
                    a[j+1] = a[j];
                    j--;
            }
            a[j+1] = selected;
    }

}

int main(void){
int a[] = { 1, 4, 2, 3 };
int n = sizeof(a)/sizeof(a[0]), i;

            insertionSort(a, n);

            printf("Sorted array: \n");
            for(i = 0; i < n; i++){
                    printf("%d ", a[i]);
            }
            puts("");

            return 0;

}
~

###補足情報(言語/FW/ツール等のバージョンなど)
より詳細な情報
海外のサイトで拾ったプログラムです。
見た感じしっかりと組まれているように思いますが、ソートがうまくいきません。

gcc-4.4.7-4.el6.x86_64
centOS6.5

Comments

[nob.]

質問が乱暴過ぎます。デバッガでステップ実行してみましたか? どういう結果を期待して、実際はどうなったのですか? 「海外のサイト」にはどのような説明があったのですか?

[raccy]

引用の場合はわかる形で引用し、かつ、引用元を明記してください。サンプルであっても著作権は存在します。このままでは著作権違反の疑いがある通報せざるを得ません。(改善が見られない場合、通報します。)

[setsu_tenhou]

http://quiz.geeksforgeeks.org/binary-insertion-sort/

[setsu_tenhou]

記述ミスが原因だったようです。　引用元を明記するのは常識でしたね　すみませんでした

Answer 1

こんにちは。

見た感じしっかりと組まれているように思いますが、ソートがうまくいきません。

なるほど。
ところで、質問が書かれていないようです。推奨していない質問に記載されているようにコードをください・デバッグしてください等の丸投げの質問はここでは非推奨ですので、質問の記載漏れと捉えました。違っていたらごめんなさい。

質問するときのヒントには回答しやすい質問をするための有用なアイデアが書かれています。参考にされると良いですよ。

Comments

[setsu_tenhou]

このサイトの使い方をしっかりと理解していなかったようです
問題は解決しました。