# 関数の改良
前と同じ関数をコメント付きで紹介しよう：

```python
def quick_sort(arr: list):
    # if empty or a single element list, nothing to sort
    if len(arr) <= 1:
        return arr

    # select element at index 0 as pivot and initialize
    # lists to store left and right partitions wrt to it
    pivot = arr[0]
    left = []
    right = []
    
    # loop over the rest of the elements (from index 1 onwards)
    # and put them into the left partition if smaller than the pivot
    # and into the right partition otherwise
    for i in range(1, len(arr)):
        if arr[i] < pivot:
            left.append(arr[i])
        else:
            right.append(arr[i])

    # sort the left and right partitions and return merged lists
    return quick_sort(left) + [pivot] + quick_sort(right)
```

最初のチェックをガード条件にすることで、読みやすくなるように少し改良しました（基本的には`else`の部分を削除しました）。

## さらなる技術的改善の可能性
このコードには、まだ多くの改良の可能性があることに注意してください。特に
- パーティショニングをインプレースで行う（メモリを節約する）
- もっと賢いピボットの選択方法：
    - ランダムにピボットを選択する（確率的に$O(N^2)$のワートケース・パフォーマンスを回避しようとする）
    - 中央値を選ぶ（Median-of-medians アルゴリズムなどで）。
    - 平均、最頻値などを選ぶ

# テスト

Python 組み込みの [`sorted`](https://docs.python.org/3/library/functions.html#sorted) 関数に対するテストです：

```python
import random


def test_sorting_function_against_sorted(sorting_fn, size, max_int=10_000):
    # seed for reproducibility as we're using randomness in our tests!
    random.seed(42)  # seed the random number generator

    for size in range(size):
        # generate a random list of integers
        lst = [random.randint(-abs(max_int), abs(max_int)) for _ in range(size)]
        # sort the list using given sorting_fn
        actual = sorting_fn(lst)
        # sort the list using Python's built-in sorted function
        expected = sorted(lst)
        # assert that the two sorted lists are equal
        assert actual == expected, "Oh no! The sorting function doesn't work!"


# test empty list
test_sorting_function_against_sorted(quick_sort, size=0)

# test single list
test_sorting_function_against_sorted(quick_sort, size=1)

# test lists with lots of numbers
test_sorting_function_against_sorted(quick_sort, size=10_000)
```

また何か質問や要望があれば、遠慮なくどうぞ！😊。
# Improving the function
Here's the same function from before but now with comments:

```python
def quick_sort(arr: list):
    # if empty or a single element list, nothing to sort
    if len(arr) <= 1:
        return arr

    # select element at index 0 as pivot and initialize
    # lists to store left and right partitions wrt to it
    pivot = arr[0]
    left = []
    right = []
    
    # loop over the rest of the elements (from index 1 onwards)
    # and put them into the left partition if smaller than the pivot
    # and into the right partition otherwise
    for i in range(1, len(arr)):
        if arr[i] < pivot:
            left.append(arr[i])
        else:
            right.append(arr[i])

    # sort the left and right partitions and return merged lists
    return quick_sort(left) + [pivot] + quick_sort(right)
```

I've slightly improved it for readability by making the first check into a guard condition (essentially I removed the `else` part).

## Further possible technical improvements
Note that there still many potential areas for improvement for this piece of code. In particular, we can:
- make the partitioning be done in-place (save memory)
- do a much more clever way of selecting the pivot via:
    - Choosing a pivot at random (stochastically try to avoid $O(N^2)$ wort-case performance)
    - Choose the median (via the Median-of-medians algorithms, etc.)
    - Choose mean, mode etc.

# Tests

Here are some tests against Python's built-in [`sorted`](https://docs.python.org/3/library/functions.html#sorted) function:

```python
import random


def test_sorting_function_against_sorted(sorting_fn, size, max_int=10_000):
    # seed for reproducibility as we're using randomness in our tests!
    random.seed(42)  # seed the random number generator

    for size in range(size):
        # generate a random list of integers
        lst = [random.randint(-abs(max_int), abs(max_int)) for _ in range(size)]
        # sort the list using given sorting_fn
        actual = sorting_fn(lst)
        # sort the list using Python's built-in sorted function
        expected = sorted(lst)
        # assert that the two sorted lists are equal
        assert actual == expected, "Oh no! The sorting function doesn't work!"


# test empty list
test_sorting_function_against_sorted(quick_sort, size=0)

# test single list
test_sorting_function_against_sorted(quick_sort, size=1)

# test lists with lots of numbers
test_sorting_function_against_sorted(quick_sort, size=10_000)
```

If you have any further questions or requests, please do not hesitate! 😊