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

Для случайного перемешивания массива в английском языке используется термин shuffle, что по-русски означает "перетасовать".

Задача случайного перемешивания не так уж и тривиальна, так как для этого требуется выбрать случайную перестановку.

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

random.shuffle(A)

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

B = sorted(yourList, key=lambda A: random.random())

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

Сортировка подсчетом

Иногда сортируемые элементы имеют небольшой диапазон возможных значений. Например, если необходимо отсортировать список натуральных чисел, каждое из которых не более трех-пяти разрядов в длину. Однако количество сортируемых чисел настолько велико, что нужно обработать список за линейное время.

Исходная последовательность чисел длины n, а в конце отсортированная, хранится в массиве A. Также используется вспомогательный массив C с индексами от 0 до k-1 изначально заполняемый нулями.

· Последовательно пройдём по массиву A и запишем в C[i] количество чисел, равных i.

· Теперь достаточно пройти по массиву С и для каждого числа number из диапазона допустимых значений последовательно записать в массив А число number C[number] раз.

ПРИМЕР СОРТИРОВКИ ПОДСЧЕТОМ НА PYTHON

def SimpleCountingSort(A):
scope = max(A) + 1
C = [0] * scope
for x in A:
C[x] += 1
pos = 0
A[:] = []
for number in range(scope):
A += [number] * C[x]

 

 

ПРИМЕР СОРТИРОВКИ ПОДСЧЕТОМ НА ЯЗЫКЕ СИ

void simpleCountingSort(unsigned char A[], size_t N)

{

size_t frequency[256];

for(size_t i = 0; i < N; i++) {

frequency[A[i]]++;

}

size_t position = 0;

for(unsigned char number = 0; number <= 255; number++) {

for(size_t i = 0; i < frequency[number]; i++) {

A[position] = number;

position++;

}

}

}

 

ПРИМЕР СОРТИРОВКИ ПОДСЧЕТОМ НА ЯЗЫКЕ PASCAL

{Пример сортировки по неубыванию массива, все элементы которого по модулю не превосходят 1000}

var

arr: array[-1000..1000] of longint; //arr[i] - количество чисел i в массиве

i, j, n, x: longint;

begin

readln(n);

for i:= -1000 to 1000 do

arr[i]:= 0;

for i:= 1 to n do

begin

read(x);

inc(arr[x]);

end;

for i:= -1000 to 1000 do

for j:= 1 to arr[i] do

write(i, ' ');

end.

Поразрядная сортировка

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

· length – максимальное количество разрядов в сортируемых величинах (например, при сортировке слов необходимо знать максимальное количество букв в слове),

· rang – количество возможных значений одного разряда (при сортировке слов – количество букв в алфавите).

Для сортировки чисел второе число заранее известно: количество цифр равно основанию системы счисления. Поскольку в большинстве случаев сортируемые числа состоят из небольшого количества разрядов, поразрядная сортировка мало того, что применима, но и работает сравнительно быстро.

Допустим, у нас есть числа: 39, 47, 54, 59, 34, 41, 32 (length = 2, rang = 10)

1. Создаем пустые списки, количество которых равно числу rang.

2. Распределяем исходные числа по этим спискам в зависимости от величины младшего разряда (по возрастанию).
Для нашего примера получим:
41
32
54, 34
47
59, 39

(Вообще надо создать 10 (rang) списков, но некоторые из них оказались пустыми)

3. Собираем числа в той последовательности, в которой они находятся после распределения по спискам.
Получим: 41, 32, 54, 34, 47, 59, 39

4. Повторяем пункты 2 и 3 для всех более старших разрядов поочередно.
Для двузначных чисел мы должны сделать еще один проход. Распределение по спискам будет выглядеть так:
32, 34, 39
41, 47
54, 59
Объединив числа в список, получим отсортированный массив.

Запишем алгоритм на Python:

A = [12, 5, 664, 63, 5, 73, 93, 127, 432, 64, 34]
length = len(str(max(A)))
rang = 10
for i in range(length):
B = [[] for k in range(rang)] #список длины range, состоящий из пустых списков
for x in A:
figure = x // 10**i % 10
B[figure].append(x)
A = []
for k in range(rang):
A = A + B[k]
print(A)