work through Shell Sort 3 (HW) and Quicksort 4 (HW) on Shell Sort & Quicksort For Shell Sort 3, use the gap sequence 11, 4, 1 For Quicksort 4, work through the first three partition operations

Answer 1

import random

def ShellSort( array, N, gapSequence):

nGap = len(gapSequence)

for gapLoop in range(nGap):

gap = gapSequence[gapLoop]

i=gap

while (i<N):

temp = array[i]

j = i

while (j>=gap) and (array[j-gap]>temp):

array[j] = array[j-gap]

j = j - gap

array[j]=temp

i=i+1

return

##############################################

gapSequence=[40,11,4,1]

array = []

for i in range(100):

array.append(random.randint(1,32500))

ShellSort(array,100,gapSequence)

print(array)

#################################################################################

# quicksort

####################################

import random

def quicksort(array, first, last):

if first<last:

pivot = first

i = first

j = last

while i<j:

while (array[i]<array[pivot]) and (i<last):

i=i+1

while (array[j]>array[pivot]):

j=j-1

if (i<j):

temp=array[i]

array[i]=array[j]

array[j]=temp

temp = array[pivot]

array[pivot]=array[j]

array[j]=temp

quicksort(array,first,j-1)

quicksort(array,j+1,last)

##################################################

A=[]

n=100

for i in range(n):

A.append(random.randint(1,32500))

quicksort(A,0,n-1)

print(A)