Homework SoursePlease I want a detailed complete answers for each partThen
Please I want a detailed complete answers for each part.Then make sure you provide clear picture(s) of soultions that I can read. Try making all numbers and letters clrearly readable easy to recognize. You also can type it which I prefer so I can copy all later, paste them in Microsoft Word to enlarge & edit if needed. Thanks for all :)
Solution
QuickSort:
QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.
The key process in quickSort is partition(). Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time
elements:
9 34 17 6 15 38
9 34 17 6 15 38
9 34 17 6 15 38
9 34 17 6 15 38
9 34 17 6 15 38
9 34 17 6 15 38
9 6 17 34 15 38
swapping 15 and 34
15 is choosing pivot
compare with i-1 value
Program
def quickSort(alist):
quickSortHelper(alist,0,len(alist)-1)
def quickSortHelper(alist,first,last):
if first<last:
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 <= rightmark and alist[leftmark] <= pivotvalue:
leftmark = leftmark + 1
while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
rightmark = rightmark -1
if rightmark < leftmark:
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 = [9,34,17,6,15,8]
quickSort(alist)
print(alist)
Mergesort:
MergeSort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, l, m, r) is key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one. See following C implementation for details.
9 34 17 6 15 38
divide two parts
9 34 17 6 15 38
divide separate parts
9 34 17 6 15 38
compare two elements in each section
9 34 17 6 15 38
compare section to section
9 17 34 6 15 38
compare two section
6 9 15 17 34 38
Merges two subarrays of arr[].
# First subarray is arr[l..m]
# Second subarray is arr[m+1..r]
def merge(arr, l, m, r):
n1 = m - l + 1
n2 = r- m
# create temp arrays
L = [0] * (n1)
R = [0] * (n2)
# Copy data to temp arrays L[] and R[]
for i in range(0 , n1):
L[i] = arr[l + i]
for j in range(0 , n2):
R[j] = arr[m + 1 + j]
# Merge the temp arrays back into arr[l..r]
i = 0 # Initial index of first subarray
j = 0 # Initial index of second subarray
k = l # Initial index of merged subarray
while i < n1 and j < n2 :
if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
# Copy the remaining elements of L[], if there
# are any
while i < n1:
arr[k] = L[i]
i += 1
k += 1
# Copy the remaining elements of R[], if there
# are any
while j < n2:
arr[k] = R[j]
j += 1
k += 1
# l is for left index and r is right index of the
# sub-array of arr to be sorted
def mergeSort(arr,l,r):
if l < r:
# Same as (l+r)/2, but avoids overflow for
# large l and h
m = (l+(r-1))/2
# Sort first and second halves
mergeSort(arr, l, m)
mergeSort(arr, m+1, r)
merge(arr, l, m, r)
Output:
Heapsort:
def heapsort( aList ):
# convert aList to heap
length = len( aList ) - 1
leastParent = length / 2
for i in range ( leastParent, -1, -1 ):
moveDown( aList, i, length )
# flatten heap into sorted array
for i in range ( length, 0, -1 ):
if aList[0] > aList[i]:
swap( aList, 0, i )
moveDown( aList, 0, i - 1 )
def moveDown( aList, first, last ):
largest = 2 * first + 1
while largest <= last:
# right child exists and is larger than left child
if ( largest < last ) and ( aList[largest] < aList[largest + 1] ):
largest += 1
# right child is larger than parent
if aList[largest] > aList[first]:
swap( aList, largest, first )
# move down to largest child
first = largest;
largest = 2 * first + 1
else:
return # force exit
def swap( A, x, y ):
tmp = A[x]
A[x] = A[y]
A[y] = tmp
BinSort:
Time Complexity of Solution:
# Best Case O(n); Average Case O(n); Worst Case O(n)
In the presented program insertionsort is used to sort
each bucket. This is to inculcate that the bucket sort algorithm
does not specify which sorting technique to use on the buckets.
A programmer may choose to continuously use bucket sort on each
bucket until the collection is sorted (in the manner of the radix
sort program below). Whichever sorting method is used on the
buckets, bucket sort still tends toward O(n).
Program:
def bucketsort( A ):
# get hash codes
code = hashing( A )
buckets = [list() for _ in range( code[1] )]
# distribute data into buckets: O(n)
for i in A:
x = re_hashing( i, code )
buck = buckets[x]
buck.append( i )
# Sort each bucket: O(n).
# I mentioned above that the worst case for bucket sort is counting
# sort. That\'s because in the worst case, bucket sort may end up
# with one bucket per key. In such case, sorting each bucket would
# take 1^2 = O(1). Even after allowing for some probabilistic
# variance, to sort each bucket would still take 2-1/n, which is
# still a constant. Hence, sorting all the buckets takes O(n).
for bucket in buckets:
insertionsort( bucket )
ndx = 0
# merge the buckets: O(n)
for b in range( len( buckets ) ):
for v in buckets[b]:
A[ndx] = v
ndx += 1
import math
def hashing( A ):
m = A[0]
for i in range( 1, len( A ) ):
if ( m < A[i] ):
m = A[i]
result = [m, int( math.sqrt( len( A ) ) )]
return result
def re_hashing( i, code ):
return int( i / code[0] * ( code[1] - 1 ) )
Radix Sort:
Time Complexity of Solution:
Best Case O(kn); Average Case O(kn); Worst Case O(kn),
where k is the length of the longest number and n is the
size of the input array.
radix sort, like counting sort and bucket sort, is an integer based
algorithm (i.e. the values of the input array are assumed to be
integers). Hence radix sort is among the fastest sorting algorithms
around, in theory. The particular distinction for radix sort is
that it creates a bucket for each cipher (i.e. digit); as such,
similar to bucket sort, each bucket in radix sort must be a
growable list that may admit different keys.
Program:
def radixsort( aList ):
RADIX = 10
maxLength = False
tmp , placement = -1, 1
while not maxLength:
maxLength = True
# declare and initialize buckets
buckets = [list() for _ in range( RADIX )]
# split aList between lists
for i in aList:
tmp = i / placement
buckets[tmp % RADIX].append( i )
if maxLength and tmp > 0:
maxLength = False
# empty lists into aList array
a = 0
for b in range( RADIX ):
buck = buckets[b]
for i in buck:
aList[a] = i
a += 1
# move to next digit
placement *= RADIX
