プログラマの考えが・・身につく本より(Python)：ソートについて

前回条件付き検索として与えられた値に対し最大値をもとめる問題(解答はありますが(汗)をPythonにて勉強がてら書いていますが、今回ソートを解説ありでC++コードが記載されており、いつも通りPythonにと思っていましたが、自分の力では直せず、ググって掲載されているコードに覚書として。

問題：クイックソート

C++の解答コード

int compareFunc(const void * voidA, const void * voidB) {
    int * intA = (int *)(voidA);
    int * intB = (int *)(voidB);
return *intA - *intB;
}

const int ARRAY_SIZE = 10;
int intArray[ARRAY_SIZE] = {87,28,100,78,84,98,75,70,81,68};
qsort(intArray, ARRAY_SIZE, sizeof(int), compareFunc);

qsort関数で実装されていました。

自分(拝借Code)与えられた配列をクイックソートで並び替えて返すPython

参考サイト→クイックソート [Quick Sort]

test35.py

#!/usr/bin/env python
#coding:utf-8

def quicksort(seq):             
    if len(seq) < 1:             #与えられたseq配列が1個未満ならそのものを返す
        return seq

    pivot = seq[0]               #pivotへseq配列[0]番目を代入　※再帰された時、一番左の配列番目がpivotへ割り当てられる
    left = []                    #left配列どんどん溜める為に作る「ここの理解が違うのかな」
    right = []                   #right配列　同じく

    for x in range(1, len(seq)): #seq配列の0を除く1から長さ分繰り返す
        if seq[x] <= pivot:      #最初にseq配列[1]がpivotと比較して小さいか？
            left.append(seq[x])  #小さい場合、pivot中心に配列の右left配列へ溜める
        else:
            right.append(seq[x]) #大きい場合、pivot中心に配列の左right配列へ溜める

    left = quicksort(left)       ###貯められたleft配列をleft変数へ代入している
    right = quicksort(right)     ###上記と同じ
    foo = [pivot]                ###※問題はここですが、pivotは再帰的に呼ばれている配列の[0]番目の値だから、それを集めたもの？？
    return left + foo + right

seq = [87,28,100,78,84,98,75,70,81,68]
mx = quicksort(seq)
print(mx)

・・・(ターミナル実行結果)
>>> from test35 import quicksort
[28, 68, 70, 75, 78, 81, 84, 87, 98, 100]
>>> 

あまりに理解に苦しんだので pivot代入部分にprint文で中にをチェックしつつ、return部分を変えながら実行して返って来るものを確認してみる

return leftのみにしてみる

test35.py

#!/usr/bin/env python
#coding:utf-8

def quicksort(seq):
    if len(seq) < 1:
        return seq
    pivot = seq[0]
    print(pivot)
    left = []
    right = []
    for x in range(1, len(seq)):
        if seq[x] <= pivot:
            left.append(seq[x])
        else:
            right.append(seq[x])
    left = quicksort(left)
    right = quicksort(right)
    foo = [pivot]
    #return left + foo + right
    return left

seq = [87,28,100,78,84,98,75,70,81,68]
mx = quicksort(seq)
print(mx)

・・・(実行結果)
>>> from test35 import quicksort
87
28
78
75
70
68
84
81
100
98
[]
>>> 
うん、なんで？？やっぱり左に貯めているわけではない様な自分の中ではきっと[87,28,100・・・]などを
期待していました。pivot部分を先にprintでだしているのですが、ここはなんとなく理解できる。
pivotは与えられた配列の[0]番目の要素を代入されているからそのままが出てきている.

これを変だなと思ってreturn foo + rightで変速にして試してみたのですが、
結果のみ

・・・(実行結果)
>>> from test35 import quicksort
[87, 100]
>>> 
あれ、もしかしたら最後に与えられた配列が戻っている？pivotは？謎です。

最後に return fooで試すと、
結果のみ

>>> from test35 import quicksort
[87]
>>> 
うん、やっぱり最後に与えられた配列の[0]番目要素だけ返している。

参考サイトにはこのように解説されていました。

リストを昇順に整列させる実装例です。
ピボットをリストの先頭要素として、値の小さな要素は left リストに、値の大きな要素は right リストに格納して最後にピボットを中心としてリストを結合しています。

コメントにてアドバイス頂いた通り出力結果理解しました。質問ばかりになってしまい申し訳ありませんでした。