Javascriptを用いたクイックソートアルゴリズムの修正

Question

前提・実現したいこと

Javascriptを用いたクイックソートアルゴリズムについて困っていることがあるので質問します。以下のプログラムではキーを用いて入力列を二つの部分に分けてソートを行っており、どこかが間違っていてうまく機能しないという前提があります。しかし実行すると正しいソートの結果が得られてしまいます。//Q//の箇所が修正してほしい箇所になります。お力添えのほどよろしくお願いします。

該当のソースコード

function qsort(lst){
    if(lst.length <= 1) return lst;
    else{
        
        var le = [] , gt =[];
        var key = lst[0];
        for(var i=1; i<lst.length;　i++){
            var ele = lst[i];
            if(ele<=key) le.push(ele);
            else gt.push(ele);
        }
        
        le.push(key);　　　//**Q**//
        return qsort(le).concat(qsort(gt));
        
        
    }
}　

Comments

[luuguas]

>どこかが間違っていてうまく機能しないという前提があります。
本やサイトで「誤りを含むコードを修正せよ」という問題として、このコードが載っていたということですか？

[ku__ra__ge]

最悪計算量の回避
https://ja.wikipedia.org/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88#%E6%9C%80%E6%82%AA%E8%A8%88%E7%AE%97%E9%87%8F%E3%81%AE%E5%9B%9E%E9%81%BF
……を考慮せよって話かな？
でもその場合修正すべきは//**Q**//の箇所じゃない気がするけど。

[plzcarryme]

これは自分が作成したコードではなく問題として与えられたものです。ヒントとしてlst=[4,2,3,8,7,1,9]としてqsort(lst)を実行したときの動作について考え、どの部分に問題があるのかという問いです。再帰部分の動きも書き出してみたりこのコード自体を実行したりもしたのですが正しい結果が得られてしまったため困っています。どうしても見つからないとなると可能性は低いですが問題自体の不備というのもあり得るかもしれません。

[luuguas]

一応出典を記載してもらえますか。

Answer 1

lst = [3,1,4,1,5,9,2]で動かせば正しい結果は得られないでしょう。
ヒントとしてうまくいく例を与える出題意図が分かりませんが、自分でいろんな例を試してみるぐらいのことは期待されてるんじゃないでしょうか。