Быстрая сортировка Хоара: Python 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Быстрая сортировка Хоара: Python



Этот алгоритм, чаще называемый просто «быстрая сортировка» (англ. Quicksort) придуман английским ученым Чарльзом Хоаром в 1960 году.

Во многом идея быстрой сортировки такая же, как у алгоритма сортировки слиянием. Выберем некоторый элемент q, называемый барьерным элементом. Разобьем массив на две части, переупорядочив его элементы. В первой части соберем элементы, меньшие или равные q, а во второй части — большие или равные q. Теперь достаточно отсортировать обе части, после чего выполнить их конкатенацию безо всякого дополнительного слияния.

Простая реализация быстрой сортировки Хоара выглядит так:

def QuickSort(A):
if len(A) <= 1:
return A
else:
q = random.choice(A)
L = []
M = []
R = []
for elem in A:
if elem < q:
L.append(elem)
elif elem > q:
R.append(elem)
else:
M.append(elem)
return QuickSort(L) + M + QuickSort(R)

В данном примере в списке L собираются элементы, меньшие q, в списке R — большие q, а в списке M — равные q. Разделение на три списка, а не на два используется для того, чтобы алгоритм не зацикливался, например, в случае, когда в списке остались только равные элементы. Барьерный элемент q выбирается случайным образом из списка при помощи функции choice из модуля random.

Тот же алгоритм можно записать еще проще в «функциональном» стиле:

def QuickSort(A):
if len(A) <= 1:
return A
else:
q = random.choice(A)
L = [elem for elem in A if elem < q]

M = [q] * A.count(q)
R = [elem for elem in A if elem > q]
return QuickSort(L) + M + QuickSort(R)

Однако, такая реализация алгоритма, как и сортировка слиянием, требует O(n) дополнительной памяти. Возможна реализация алгоритма сортировки слиянием без использования дополнительной памяти:

def QuickSort(A, l, r):
if l >= r:
return
else:
q = random.choice(A[l:r + 1])
i = l
j = r
while i <= j:
while A[i] < q:
i += 1

while A[j] > q:
j -= 1
if i <= j:
A[i], A[j] = A[j], A[i]
i += 1
j -= 1
QuickSort(A, l, j)
QuickSort(A, i, r)

Эта реализация не возвращает никакого значения, а сортирует элементы списка A «на месте», то есть модифицирует переданный список A. Два дополнительный параметра l и r указывают на номер первого и последнего элемента того фрагмента списка, который нужно отсортировать (включая эти элементы), то есть элемент сортирует срез A[l:r+1]. Для сортировки всего списка A необходимо вызвать QuickSort(A, 0, len(A) – 1).

Если l >= r, то ничего сортировать не нужно, срез пустой или содержит один элемент. Иначе случайным образом выбирается барьерный элемент. Далее заводятся два указателя i = l и j = r. Затем элементы списка переставляются так, чтобы элементы, которые меньше или равны q оказывались слева от указателя i, а те, которые больше или равны q оказывались справа от j. После окончания распределения рекурсивно сортируются две получившиеся части списка.

Данная реализация не требует дополнительной памяти (за исключением памяти, необходимой для организации рекурсии).

Асимптотика алгоритма

Сложность алгоритма быстрой сортировки Хоара зависит от метода выбора барьерного элемента. В лучшем случае при каждом выборе барьерного элемента должен выбираться медианный элемент массива. Но поиск медианного элемента — сложная задача, её нельзя решить быстро. Если выбрать первый элемент фрагмента списка A[l] или последний A[r], то если список A уже упорядочен, сложность алгоритма будет O(n2), так как на каждом рекурсивном вызове от большей части списка будет отделяться всего один элемент.

Поэтому в алгоритме быстрой сортировки Хоара, как правило, в качестве барьерного элемента выбирается случайный элемент списка. Тогда алгоритм становится вероятностным — время его работы зависит от того, каким будет случайно выбранный элемент. Возможна (но крайне маловероятна) ситуация, когда всегда будет выбираться наименьший элемент, и в этом случае алгоритм будет работать за O(n2).

В теории вероятностей доказывается, чти при случайном выборе элемента списка и разбиении его на две части, размер большей из двух получившихся частей будет в среднем равен 3n/4. В этом случае глубина рекурсии в среднем будет составлять порядка logn, а средняя сложность алгоритма быстрой сортировки Хоара — O(nlogn).

Права доступа к файлам на NTFS

При выполнении каких-либо операций с файлом или папкой сначала проверяется список имеющихся для него (нее) разрешений, и если для текущего пользователя разрешение на осуществление конкретного действия отсутствует, то пользователю будет отказано в выполнении данного действия.

Механизм разрешений используется только на разделах с файловой системой NTFS. На разделах с файловой системой FAT/FAT32 любой пользователь имеет полный доступ ко всем файлам.

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

· Любой пользователь имеет полный доступ к папкам своего профиля и может управлять правами доступа к ним.

· При использовании учетной записи с правами обычного пользователя нельзя получить доступ к папкам других пользователей. Однако если учетная запись администратора не защищена паролем, то любой пользователь может с ее помощью войти в систему и получить доступ к файлам.

· Все пользователи могут создавать и изменять свои файлы в папке Общие или одной из ее подпапок. Файлы других пользователей можно только просматривать.

· Чтобы получить доступ к папкам другого пользователя без его разрешения, нужно обладать правами администратора. При этом пользователь автоматически будет добавлен в список разрешений для данного объекта.

· Пользователям запрещено изменение системных папок, например Windows или Program Files. Для выполнения этих операций нужно подтвердить ваши права в окне UAC. В целях безопасности некоторые действия запрещены даже для администраторов, но изменить системный файл можно, став его владельцем (см. далее).

Почти все папки имеют в списке доступа группу Администраторы, но поведение системы при попытке получить доступ к такой папке будет различаться, в зависимости от того, включен ли контроль учетных записей (UAC). При включенном UAC появится окно с просьбой подтвердить действия или ввести пароль учетной записи с правами администратора. При отключенном UAC для учетной записи с правами администратора доступ будет предоставлен автоматически, а для обычных пользователей доступ будет запрещен. Если же доступ к папке или файлу запрещен даже администраторам, для его получения понадобится изменить разрешения вручную.



Поделиться:


Последнее изменение этой страницы: 2017-02-19; просмотров: 766; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 54.226.68.181 (0.005 с.)