purebasic.info

PureBasic forum
Текущее время: Ср янв 17, 2018 1:36 pm

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ 1 сообщение ] 
Автор Сообщение
 Заголовок сообщения: Рассортировка
СообщениеДобавлено: Пт сен 26, 2008 8:55 pm 
Не в сети
МОДЕРАТОР

Зарегистрирован: Вт дек 05, 2006 8:46 am
Сообщений: 6220
Благодарил (а): 16 раз.
Поблагодарили: 173 раз.
Пункты репутации: 48
В некоторых программах требуется выполнение операции, обратной сортировке. Получив список элементов, программа должна расположить их в случайном порядке. Рандомизацию (unsorting) списка несложно выполнить, используя алгоритм, похожий на сортировку выбором.
Для каждого положения в списке, алгоритм случайным образом выбирает элемент, который должен его занять из тех, которые еще не были помещены на свое место. Затем этот элемент меняется местами с элементом, который, находится на этой позиции.
Код:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
Global Dim Massiv(100);Массив на 101 элемент
;заполним массив числами от 0 до 100
For i = 0 To 100
Massiv(i)=i
Next i
; процедура рассортировки
Procedure Unsort( min.l, max.l)
 
        For i = min To max
                pos = Int( Random((max - i)) + i)
                tmp = Massiv(pos)
                Massiv(pos) = Massiv(i)
                Massiv(i) = tmp
        Next i
EndProcedure
 
Unsort(0,100)
;Проверяем результат
For i = 0 To 100
Debug Massiv(i)
Next i
 


Т.к. алгоритм заполняет каждую позицию только один раз, его сложность порядка O(N).
Несложно показать, что вероятность того, что элемент окажется на какой либо позиции, равна 1/N. Поскольку элемент может оказаться в любом положении с равной вероятностью, этот алгоритм действительно приводит к случайному размещению элементов.
Результат зависит от того, насколько хорошим является генератор случайных чисел. Функция Random в PureBasic дает приемлемый результат для большинства случаев.
Заметим, что для алгоритма не важен первоначальный порядок расположения элементов. Если вам необходимо неоднократно рандомизировать список элементов, нет необходимости его предварительно сортировать.

По материалам книги "Готовые алгоритмы на Visual Basic"


Вернуться наверх
 Профиль  
 
Показать сообщения за:  Сортировать по:  
Начать новую тему Ответить на тему  [ 1 сообщение ] 

Часовой пояс: UTC + 3 часа


Кто сейчас на форуме

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group (блог о phpBB)
Сборка создана CMSart Studio
Русская поддержка phpBB