Стандартная сортировка и случайное перемешивание массива в Python

Алгоритм стандартной сортировки Timsort

В Python реализован встроенный алгоритм сортировки, известный как Timsort. Этот алгоритм совмещает в себе сортировку слиянием для больших списков и сортировку вставками для небольших фрагментов. Он оптимизирован для работы в Python и может быстро сортировать списки, которые почти отсортированы, за линейное время.

Существует два способа вызова сортировки: метод `sort` и функция `sorted`

Метод `sort`

Метод `sort` вызывается непосредственно для списка и производит сортировку "на месте", меняя порядок элементов.

```python

import random

List = [random.randint(1, 1000) for i in range(1000)]

List.sort()

```

Этот метод не возвращает значения, поэтому результат нельзя использовать в арифметических выражениях или при выводе.

Функция `sorted`

Функция `sorted` не изменяет переданный ей список, а возвращает новый отсортированный список. Использовать ее можно так:

```python

import random

List = [random.randint(1, 1000) for i in range(1000)]

Sorted_List = sorted(List)

```

Пример программы, которая считывает список чисел, разделенных пробелами, сортирует его и выводит результат:

```python

print(" ".join(map(str, sorted(map(int, input().split())))))

```

Параметр `reverse`

Как методу `sort`, так и функции `sorted` можно передать дополнительный параметр `reverse`. Если `reverse` установлен в `True`, то сортировка производится в обратном порядке (по невозрастанию).

Случайное перемешивание массива в Python

Термином "shuffle" (перетасовать) обозначается задача случайного перемешивания массива. Эта задача не так проста, как может показаться, так как требует выбора случайной перестановки.

В библиотеке `random` имеется функция, которая позволяет перемешивать массив на месте:

```python

random.shuffle(ListA)

```

Другой вариант перемешивания — использование случайного ключа для сортировки:

```python

ListB = sorted(yourList, key=lambda ListA: random.random())

```

Следует помнить, что даже для сравнительно небольших массивов количество возможных перестановок `len(ListA)` значительно превышает период наилучших генераторов случайных чисел. Это означает, что большинство перестановок длинной последовательности никогда не будут созданы.