昇順ソートを行い、末尾に０の値で埋めたい。

[山田]

C++でソートの勉強をしており、特殊なソートを試したいと考えています。

ネットを参考にして構造体をソートすることまでは出来たのですが、
特殊なソートの仕方をしたい場合に、どうすればよいかわからなくて・・・。

{ 0, 1, 2, 7, 0, 2 }

みたいな配列があった際に

{ 1, 2, 2, 7, 0, 0 }

のような昇順ソートをしつつも０は最後に
付加をするといった変わったことを行いたいです。

比較関数を理解出来ておらず、
ここが理解できれば、出来るのかなと推測しております。
お分かりになる方おりませんでしょうか？

以下のソースは構造体で用意した配列を
Countキーを軸としてソートしております。

コード:

typedef struct{
    int Count;
    int Ptn;
    int StopCount;
    float Speed;
}STAGE_DATA;

int CompDate(const void* pElem1, const void* pElem2){

    // ポインタ取得用
    const STAGE_DATA* pmem1 = (const STAGE_DATA*)pElem1;
    const STAGE_DATA* pmem2 = (const STAGE_DATA*)pElem2;
    
    int nDiff;  // 両要素の差
    
    nDiff = pmem1->Count - pmem2->Count;
    return nDiff;
    
}

static STAGE_DATA Stage[STAGE_MAX];

qsort( Stage, numof(Stage), sizeof *Stage, CompDate );

[box]

{ 1, 2, 2, 7, 0, 0 }

いったん
0, 0, 1, 2, 2, 7
とソートします。

その後で、「先頭から探索し、0を見つけたら、
先頭の次以降を1個ずつ前へずらし、あいた場所（つまりいちばん最後）へ
0を移動させる」というロジックを手で組み込む必要があります。

qsort()の比較関数とは無関係です。

[みけCAT]

素直に比較関数を

• どっちかが0なら、0の方が大きい
• そうでなければ、普通に比較する

としたらどうですか？(テストしていません)

コード:

int CompDate(const void* pElem1, const void* pElem2){

    // ポインタ取得用
    const STAGE_DATA* pmem1 = (const STAGE_DATA*)pElem1;
    const STAGE_DATA* pmem2 = (const STAGE_DATA*)pElem2;
    
    if (pmem1->Count == 0) {
        retuen pmem2->Count == 0 ? 0 : 1;
    } else if (pnem2->Count == 0) {
        /* pmem1->Count != 0 */
        return -1;
    } else if (pmem1->Count > pmem2->Count) {
        return 1;
    } else if (pmem1->Count < pmem2->Count) {
        return -1;
    } else {
        return 0;
    }
}

[みけCAT]

テストしました。typoがあったので修正しました。

コード:

#include <stdio.h>
#include <stdlib.h>

#define STAGE_MAX 6
#define numof(x) (sizeof(x)/sizeof((x)[0]))

typedef struct{
    int Count;
    int Ptn;
    int StopCount;
    float Speed;
}STAGE_DATA;

int CompDate(const void* pElem1, const void* pElem2){

    // ポインタ取得用
    const STAGE_DATA* pmem1 = (const STAGE_DATA*)pElem1;
    const STAGE_DATA* pmem2 = (const STAGE_DATA*)pElem2;
    
    if (pmem1->Count == 0) {
        return pmem2->Count == 0 ? 0 : 1;
    } else if (pmem2->Count == 0) {
        /* pmem1->Count != 0 */
        return -1;
    } else if (pmem1->Count > pmem2->Count) {
        return 1;
    } else if (pmem1->Count < pmem2->Count) {
        return -1;
    } else {
        return 0;
    }
}

static STAGE_DATA Stage[STAGE_MAX] = {
    {0, 0, 0, 0.0f},
    {1, 1, 1, 1.0f},
    {2, 2, 2, 2.0f},
    {7, 3, 3, 3.0f},
    {0, 4, 4, 4.0f},
    {2, 5, 5, 5.0f}
};

void printStage(void) {
    int i;
    printf("Count = { %d", Stage[0].Count);
    for (i = 1; i < STAGE_MAX; i++) printf(", %d", Stage[i].Count);
    printf(" }\n");
    printf("Ptn   = { %d", Stage[0].Ptn);
    for (i = 1; i < STAGE_MAX; i++) printf(", %d", Stage[i].Ptn);
    printf(" }\n");
}

int main(void) {
    puts("before qsort:");
    printStage();
    qsort( Stage, numof(Stage), sizeof *Stage, CompDate );
    puts("after qsort:");
    printStage();
    return 0;
}

出力

コード:

before qsort:
Count = { 0, 1, 2, 7, 0, 2 }
Ptn   = { 0, 1, 2, 3, 4, 5 }
after qsort:
Count = { 1, 2, 2, 7, 0, 0 }
Ptn   = { 1, 2, 5, 3, 0, 4 }

いったん
0, 0, 1, 2, 2, 7
とソートします。

その後で、「先頭から探索し、0を見つけたら、
先頭の次以降を1個ずつ前へずらし、あいた場所（つまりいちばん最後）へ
0を移動させる」というロジックを手で組み込む必要があります。

こんな下手に実装するとO(N^2)かかりそうな、無駄に手間がかかることをする必要はありません。

[山田]

みけCAT様

ありがとうございます！
比較関数について少しだけ理解出来た気がします。

動作につきましても問題なくソートできました。
特殊な例だったので参考サイトが見つからなく助かりました。

[box]

こんな下手に実装するとO(N^2)かかりそうな、無駄に手間がかかることをする必要はありません。

ヘタな実装をしてしまい、大変申し訳ありませんでした。以後気をつけます。
まあ、いくら気をつけてもやっぱりヘタな実装をしてしまうかもしれませんが、そこは大目に見てやってください。
私のレベルはしょせんあんな程度です。

# 今後は心して投稿せねばならんな。あらぬ方向からツッコミが入る可能性があることを多少は意識しよう。