Data Structures in Python, modify the code so that the pivot is always chosen at a random location from the list (or sublist) to be sorted.

Description (please read all of it)

TASKS TO BE COMPLETED:

STRINGGENERATOR.PY

import random #stringGenerator.py

import string

import time

from itertools import permutations

def anagramSolution1(s1,s2):

alist = list(s2)

pos1 = 0

stillOK = True

while pos1

pos2 = 0

found = False

while pos2

if s1[pos1] == alist[pos2]:

found = True

else:

pos2 = pos2 + 1

if found:

alist[pos2] = None

else:

stillOK = False

pos1 = pos1 + 1

return stillOK

def anagramSolution2(s1,s2):

alist1 = list(s1)

alist2 = list(s2)

alist1.sort()

alist2.sort()

pos = 0

matches = True

while pos

if alist1[pos]==alist2[pos]:

pos = pos + 1

else:

matches = False

return matches

#anagramSolutions3 is not implemented in Miller notes

def anagramSolution3(s1,s2):

perms = [''.join(p) for p in permutations(s2)]

found=False

for s in perms:

if s1 == s:

found = True

break

return found

def anagramSolution4(s1,s2):

c1 = [0]*26

c2 = [0]*26

for i in range(len(s1)):

pos = ord(s1[i])-ord('a')

c1[pos] = c1[pos] + 1

for i in range(len(s2)):

pos = ord(s2[i])-ord('a')

c2[pos] = c2[pos] + 1

j = 0

stillOK = True

while j

if c1[j]==c2[j]:

j = j + 1

else:

stillOK = False

return stillOK

def buildMyString(n):

s=""

for i in range(n):

aletter=random.choice(string.letters)

s=s+aletter

return(s)

#-- the root (main) program starts here

string.letters = 'abcdefghijklmopqrstuvwxyz'

n=11

s1=buildMyString(n)

if random.uniform(0.0,1.0)<.5:>

r=random.randrange(0,n-1)

aletter = random.choice(string.letters)

s2=s1[0:r]+aletter+s1[r+1:n]

else:

s2=s1

print("s1 is: ",s1)

print("s2 is: ",s2)

print(" ...timing anagramSolution1 with n = ",n)

start=time.time()

print(anagramSolution1(s1,s2))

print(time.time()-start)

print(" ...timing anagramSolution2 with n = ",n)

start=time.time()

print(anagramSolution2(s1,s2))

print(time.time()-start)

print(" ...timing anagramSolution3 with n = ",n)

start=time.time()

print(anagramSolution3(s1,s2))

print(time.time()-start)

print(" ...timing anagramSolution4 with n = ",n)

start=time.time()

print(anagramSolution4(s1,s2))

print(time.time()-start)

!!!!!THE CODE THAT NEEDS TO BE MODIFIED!!!!!!

def quickSort(alist):

quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist,first,last):

if first

splitpoint = partition(alist,first,last)

quickSortHelper(alist,first,splitpoint-1)

quickSortHelper(alist,splitpoint+1,last)

def partition(alist,first,last):

pivotvalue = alist[first]

leftmark = first+1

rightmark = last

done = False

while not done:

while leftmark

alist[leftmark]

leftmark = leftmark + 1

while alist[rightmark] >= pivotvalue and \

rightmark >= leftmark:

rightmark = rightmark -1

if rightmark

done = True

else:

temp = alist[leftmark]

alist[leftmark] = alist[rightmark]

alist[rightmark] = temp

temp = alist[first]

alist[first] = alist[rightmark]

alist[rightmark] = temp

return rightmark

alist = [54,26,93,17,77,31,44,55,20]

quickSort(alist)

print(alist)

Recall that the argument is (or will be) that an implementation of quicksort that always chooses the first element (or the last element) of the list (or sublist) to be sorted will perform badly (O(n2)) if the list is already sorted. Also recall that we have claimed (or will claim) that the list performs, on the average, in O (n lg n) fashion if the pivot is always chosen at random from the list (or sublist). The objective of the lab is to: Become familiar with the details of Miller's quicksort code which always chooses the first element in the list (or the sublist) as the pivot. Empirically validate that Miller's quicksort code applied to a list that is already sorted is (O(n2).. Modify Miller's code so that the pivot is always chosen at a random location from the list (or sublist) to be sorted. Empirically validate that your modified code will sort, on the average, any list (and, in particular, a list that is already sorted or nearly sorted) in (O(n lg n)) time if the pivot is always chosen at a random location