Это правильная реализация рандомизированной быстрой сортировки? - PullRequest
Новая
       9

Это правильная реализация рандомизированной быстрой сортировки?

0 голосов
/ 10 июня 2018 
#Randomized Quick Sort
import random
def partition(array , low , high):
   i = low - 1
   pivot = array[high]

   for j in range( low , high):

       if array[j] <= pivot:

           i += 1
           array[i],array[j] = array[j],array[i] # Swapping 

   arr[i+1],arr[high] = arr[high],arr[i+1] 
   return(i+1)
def QuickSort(array,low,high):

   if low < high:
       random_value = random.randint(low,high)
       array[random_value] , array[high] = array[high], array[random_value] 
       mid = partition(array,low,high)
       QuickSort(array,low,mid-1)
       QuickSort(array,mid+1,high)

arr = [1,2,3,4,5,6,7,8,9,10]
n = len(arr)
QuickSort(arr,0,n-1)
print ("Sorted array is:")
for i in range(n):
   print (arr[i])

Я реализовал алгоритм рандомизированной быстрой сортировки с python.Но я не уверен, правильно это или нет.Кроме того, есть ли способ проверить сложность времени как обычной быстрой сортировки, так и рандомизированной быстрой сортировки с некоторым набором данных?

Спасибо

...