Using the code below, we need to implement the median-of-three method for select
ID: 675124 • Letter: U
Question
Using the code below, we need to implement the median-of-three method for selecting a pivot. If it is possible to add the code needed and any pseudo code as comments, that would be helpful.
Thank you
Code:
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
print(alist)
while alist[rightmark] >= pivotvalue and
rightmark >= leftmark:
rightmark = rightmark -1
print(alist)
if rightmark < leftmark:
done = True
else:
temp = alist[leftmark]
alist[leftmark] = alist[rightmark]
alist[rightmark] = temp
print(alist)
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)
Explanation / Answer
void partition(int a[],int start,int end) { srand (time(NULL)); int pivotpos = 3; //start + rand() % (end-start); int i = start; // index 1 int j = end; // index 2 int flag = 1; int pivot = a[pivotpos]; // sets the pivot's value while(ia[j]) // swap && sets new pivot, and restores the flag { swap(&a[i],&a[j]); if(pivotpos == i) pivotpos = j; else if(pivotpos == j) pivotpos = i; flag++; } else if(a[i] == a[j]) // avoids getting suck on a mirror of values (fx pivot on pos 3 of : 1-0-0-1-1) { if(pivotpos == i) j--; else if(pivotpos == j) i++; else { i++; j--; } flag++; } } }Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.