Golang クイックソートでの並び順について

Question

前提

Golangのクイックソートとエクセルでのソートの違いをご教授ください。

実現したいこと

以下極端な例ですが

No | 担当 | 担当No|
1  |太郎  |2      |
2  |花子  |2      |
3  |花子  |4      |
4  |三郎  |3      |

上記を踏まえてgoのクイックソートについては
2 => 2 => 3 => 4 になる可能性もあるかと思いますが、
担当名については、プログラムが
どう解釈するかは分からないため、どちらが先に来るかわがわららないということを

システムを全く知らない人にどう説明したら理解してくれるのか分からず質問させていただきました。

クイックソートは、同値の場合他の並び順は法則性がないため、
どうなるか分からないのは知っているのですが、人に説明する材料として分かり易い回答例などはありますでしょうか。

Comments

[melian]

一応、golang にも stable sort があります。

https://pkg.go.dev/sort#SliceStable

[maisumakun]

> 上記を踏まえてgoのクイックソートについては
2 => 3 => 1 => 4 になる可能性もあるかと思いますが、

どうしてあるのですか？担当Noが一意である以上、ソート結果も一意に定まります（ソート基準に対して順序が正しくないものは、もはやソートではありません）。

[Zuishin]

何度読み直しても質問の主張がわかりません。もし他の人に説明したのに理解を得られずここで質問したのであれば、まずその人ではなく自分が間違っている可能性を受容する覚悟をするのが良いでしょう。

なお、標準のソートで使われているのはクイックソートではなく、複数のアルゴリズムを組み合わせたもののようです。
この質問でいう「クイックソート」がもし自作のものであるなら、その実装方法もしくは使い方が間違っている可能性もあります。

[melian]

golang の場合、ソート対象のスライスもしくは配列の要素数によってソートアルゴリズムを変更します。

6 個以下 => insertion sort
7 〜 12個 => shell sort

基本は quick sort ですが、再帰の深さがある閾値以上になる場合は heap sort が使われます。

[prr4e]

皆様ご回答ありがとうございました。

私も質問内容を読み返して、記述内容に誤りがあることに気づきました。
訂正いたしました。

[Zuishin]

> システムを全く知らない人にどう説明したら理解してくれるのか分からず

あなたではなくわかっている人が説明するのが良いと思います。
クイックソートのアルゴリズムを説明したサイトは数多くあるので、それを直接見てもらうのも良いでしょう。
わからない人が聞きかじったことを説明してもわかりません。
要素数が四つの場合、挿入ソートになるので順番は保証されます。

[episteme]

> どちらが先に来るかわがわららないということを
> システムを全く知らない人にどう説明したら理解してくれるのか

「非安定なソートを行うので、同値要素の並びは不定です」じゃダメ?
# "非安定なソート" を説明せにゃならんのか?

[prr4e]

ありがとうございます。
「プログラムがどう解釈するかは分からないため、どちらが先に来るかわがわららないということ」

この件をクライアントに説明してなんとか分かってもらいました。
システムを知らないクライアントに説明するにはどう説明すればいいのかを悩んでましたが、
上記でわかっていただけたので、少し取り越し苦労でした。

[Zuishin]

SliceStable という安定ソートを教えて貰っているんだから、必要なら説明しなくてもそれを使えばいいだけですね。

[prr4e]

ありがとうございます。
色々ご丁寧なご説明ありがとうございいました。

Answer 1

この件をクライアントに説明してなんとか分かってもらいました。
システムを知らないクライアントに説明するにはどう説明すればいいのかを悩んでましたが、
上記でわかっていただけたので、少し取り越し苦労でした