You will implement quick sort algorithm. Your function should take an array of i

Q: You will implement quick sort algorithm. Your function should take an array of i

def quickSort(alist): quickSortHelper(alist,0,len(alist)-1) def quickSortHelper(alist,first,last): if first

ID: 3592989 • Letter: Y

Question

You will implement quick sort algorithm. Your function should take an array of integers and the size of that array and then sort it in increasing order. Add two counters to count the number of key comparisons and the number of data moves during sorting. For the quick sort algorithm, you are supposed to take the last element of the array as pivot. Your function should have the following prototype:

void quickSort(int *arr, int size, int &compCount, int &moveCount);

For key comparisons, you should count each comparison like k1 < k2 as one comparison, where k1 and k2 correspond to the value of an array entry (that is, they are either an array entry like arr[i] or a local variable that temporarily keeps the value of an array entry). For data moves, you should count each assignment as one move, where either the right-hand side of this assignment or its left-hand side or both of its sides correspond to the value of an array entry.

Explanation / Answer

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 = [54,26,93,17,77,31,44,55,20]
quickSort(alist)
print(alist)

Navigate

You will implement merge sort algorithm. Your function should take an array of i

You will implement the Matrix class: class matrix { public: matrix(); // Copy ct

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

You will implement quick sort algorithm. Your function should take an array of i

Question

Explanation / Answer

Related Questions

Navigate