《050》演習3-11


演習3-11 次に示す関数 quicksort は、あらゆる型の配列に対してクイックソートを行う汎用関数である。
 また、関数 void memswap(void* x, void* y, size_t n); は、
x, y の指す nバイトの領域を交換する関数である。
 比較関数を用意して、この quicksort関数を利用するプログラムを作成せよ。

// x, yの指すnバイトの領域を交換する関数。 void memswap(void* x, void* y, size_t n) { unsigned char* a = reinterpret_cast<unsigned char*>(x); unsigned char* b = reinterpret_cast<unsigned char*>(y); for (; n--; a++, b++) { unsigned char c = *a; *a = *b; *b = c; } } // ------------------------------------ void quicksort( void* base, // 配列へのポインタ size_t nmemb, // 要素の個数 size_t size, // 要素1つ分の大きさ // 比較関数用の仮引数 int(*compar)(const void*, const void*)) { if (nmemb > 1) { // 配列 base の先頭要素へのポインタを // キャストして、char* v に代入 const char* v = reinterpret_cast<const char*>(base); size_t pl = 0; // 検索範囲左端 size_t pr = nmemb - 1; // 検索範囲右端 size_t pt = (pl + pr) / 2; // 基準値の位置 do { // &v[pt * size] は基準値への // ポインタ &base[pt] に対応します。 while ( compar( reinterpret_cast<const void*>(&v[pl * size]), &v[pt * size] ) < 0 ) { // 検索範囲左端からチェックしていき、 // 基準値のほうが大きければ、 // 検索範囲左端の位置 pl を // インクリメント。 // 基準値以上の値を見つけたら、pl // はその位置で停止。 pl++; } while ( compar( reinterpret_cast<const void*>(&v[pr * size]), &v[pt * size] ) > 0 ) { // 検索範囲右端からチェックしていき、 // 基準値のほうが小さければ、 // 検索範囲右端の位置 pr を // デクリメント。 // 基準値以下の値を見つけたら、pr // はその位置で停止。 pr--; } if (pl <= pr) { // 検索範囲の左端と右端が逆転していないとき。 pt = (pl == pt) ? pr : (pr == pt) ? pl : pt; // 検索範囲の左端が基準値の位置に達している // 場合は、基準値の位置を現時点での // 右端の位置に更新。 // 検索範囲の右端が基準値の位置に達している // 場合は、基準値の位置を現時点での // 左端の位置に更新。 // それ以外なら、基準値の位置は更新しません。 // ※以上の操作は、関数 memswapが値を交換し // ても基準値の値が変化しないように // するため。 // 配列要素 base[pl], base[pr] の値を交換 memswap( const_cast<void*> (reinterpret_cast<const void*>(&v[pl * size])), const_cast<void*> (reinterpret_cast<const void*>(&v[pr * size])), size ); pl++; if (pr == 0) // 符号無し整数 0 からのデクリメントを避ける。 goto LABEL; pr--; } } while (pl <= pr); if (0 < pr) // 左側 0、要素数 pr + 1 として、quicksort関数を再帰呼出し。 quicksort( const_cast<void*> (reinterpret_cast<const void*>(&v[0])), pr + 1, size, compar ); LABEL: if (pl < nmemb - 1) // 左側 pl、要素数 nmemb - pl として、quicksort関数を再帰呼出し。 quicksort( const_cast<void*> (reinterpret_cast<const void*>(&v[pl * size])), nmemb - pl, size, compar ); } }

解答
#include <random>
#include <string>
#include <iostream>
using namespace std;

// x, yの指すnバイトの領域を交換する関数。
void memswap(void* x, void* y, size_t n)
{
    unsigned char* a
        = reinterpret_cast<unsigned char*>(x);
    unsigned char* b
        = reinterpret_cast<unsigned char*>(y);

    for (; n--; a++, b++) {
        unsigned char c = *a;
        *a = *b;
        *b = c;
    }
}

void quicksort(
    void* base,     // 配列へのポインタ
    size_t nmemb,   // 要素の個数
    size_t size,    // 要素1つ分の大きさ

    // 比較関数用の仮引数
    int(*compar)(const void*, const void*))
{
    if (nmemb > 1) {
        // 配列 base の先頭要素へのポインタを
        //             キャストして、char* v に代入
        const char* v = reinterpret_cast<const char*>(base);

        size_t pl = 0;              // 検索範囲左端
        size_t pr = nmemb - 1;      // 検索範囲右端
        size_t pt = (pl + pr) / 2;  // 基準値の位置

        do {
            // &v[pt * size] は基準値への
            //      ポインタ &base[pt] に対応します。
            while (
                compar(
                    reinterpret_cast<const void*>(&v[pl * size]),
                    &v[pt * size]
                ) < 0
            ) {                
                // 検索範囲左端からチェックしていき、
                //         基準値のほうが大きければ、
                //         検索範囲左端の位置 pl を
                //         インクリメント。
                // 基準値以上の値を見つけたら、pl
                //         はその位置で停止。
                pl++;
           }

            while (
                compar(
                    reinterpret_cast<const void*>(&v[pr * size]),
                    &v[pt * size]
                ) > 0
            ) {
                // 検索範囲右端からチェックしていき、
                //         基準値のほうが小さければ、
                //         検索範囲右端の位置 pr を
                //         デクリメント。
                // 基準値以下の値を見つけたら、pr
                //         はその位置で停止。
                pr--;
            }

            if (pl <= pr) {
                // 検索範囲の左端と右端が逆転していないとき。
                pt = (pl == pt) ? pr : (pr == pt) ? pl : pt;
                // 検索範囲の左端が基準値の位置に達している
                //         場合は、基準値の位置を現時点での
                //         右端の位置に更新。
                // 検索範囲の右端が基準値の位置に達している
                //         場合は、基準値の位置を現時点での
                //         左端の位置に更新。
                // それ以外なら、基準値の位置は更新しません。
                // ※以上の操作は、関数 memswapが値を交換し
                //         ても基準値の値が変化しないように
                //         するため。

                // 配列要素 base[pl], base[pr] の値を交換
                memswap(
                    const_cast<void*>
                        (reinterpret_cast<const void*>(&v[pl * size])),
                    const_cast<void*>
                        (reinterpret_cast<const void*>(&v[pr * size])),
                    size
                );

                pl++;
                if (pr == 0)    // 符号無し整数 0 からのデクリメントを避ける。
                    goto LABEL;
                pr--;
            }
        } while (pl <= pr);

        if (0 < pr)
            // 左側 0、要素数 pr + 1 として、quicksort関数を再帰呼出し。
            quicksort(
                const_cast<void*>
                    (reinterpret_cast<const void*>(&v[0])),
                pr + 1,
                size,
                compar
            );
    LABEL:
        if (pl < nmemb - 1)
            //  左側 pl、要素数 nmemb - pl として、quicksort関数を再帰呼出し。
            quicksort(
                const_cast<void*>
                    (reinterpret_cast<const void*>(&v[pl * size])),
                nmemb - pl,
                size,
                compar
            );
    }
}


int acmp(char* x, char* y) {    // 比較関数
    return strcmp(x, y);
}

int pcmp(char** x, char** y) {  // 比較関数
    return strcmp(*x, *y);
}

int ncmp(int* x, int* y) {      // 比較関数
    return *x < *y ? -1 : *x > *y ? 1 : 0;
}


int main() {
    char a[][5]
        = { "cba", "cabd", "abc", "bcd",
            "cab", "b", "a", "cba", "aa" };
    const char* p[]
        = { "cba", "cabd", "abc", "bcd",
            "cab", "b", "a", "cba", "aa" };

    // ------------------------------------
    cout << "◆ ";
    for (int i = 0; i < 9; i++)
        cout << a[i] << "  ";
    cout << '\n';

    quicksort(a, sizeof(a) / sizeof(a[0]), sizeof(a[0]),
        reinterpret_cast<int(*)(const void*, const void*)>(acmp));

    cout << "→ ";
    for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
        std::cout << a[i] << "  ";
    std::cout << "\n\n";


    // ------------------------------------
    cout << "\n◆ ";
    for (int i = 0; i < 9; i++)
        cout << p[i] << "  ";
    cout << '\n';

    quicksort(p, sizeof(p) / sizeof(p[0]), sizeof(p[0]),
        reinterpret_cast<int(*)(const void*, const void*)>(pcmp));

    cout << "→ ";
    for (int i = 0; i < sizeof(p) / sizeof(p[0]); i++)
        std::cout << p[i] << "  ";
    std::cout << "\n\n";


    // ------------------------------------
    random_device rd;

    int num[20];
    cout << "\n◆ ";
    for (int i = 0; i < 20; i++) {
        num[i] = rd() % 90 + 10;
        cout << num[i] << ' ';
    }
    cout << '\n';

    quicksort(num, sizeof(num) / sizeof(num[0]), sizeof(num[0]),
        reinterpret_cast<int(*)(const void*, const void*)>(ncmp));

    cout << "→ ";
    for (int i = 0; i < sizeof(num) / sizeof(num[0]); i++)
        std::cout << num[i] << ' ';
    std::cout << '\n';
}

fca03_0017.png

2018-03-10 23:45 : 未分類 : コメント : 0 :
コメントの投稿
非公開コメント

« next  ホーム  prev »

検索フォーム

こうすけ kousuke_cpp@outlook.jp

スポンサーリンク

新版 明解C 中級編 (明解シリーズ)

新品価格
¥2,916から
(2018/3/24 23:58時点)