[ 62 , 71, 66, 69, 56] and [ 85 , 92, 79, 97, 82, 99] Your assignment requires f
ID: 3876755 • Letter: #
Question
[62, 71, 66, 69, 56] and [85, 92, 79, 97, 82, 99]
Your assignment requires finishing the Split function in the QuickSort algorithm on each of these two sub-lists. Show each list as each iteration highlighting which number gets changed, until the lists are sorted or the algorithm would finish with an error, which ever would come first. Make sure you show all work so I can understand the Quicksort.
Be sure to trace the pseudocode line by line and show the array after each iteration as well as the left, right and pivot. For example when sorting this sublist: [62, 71, 66, 69, 56]
l = 0
r = 4
pivot: 62
first iteration: [62, 71, 66, 69, 56]
l = 1
r = 4
pivot = 62
swap 71 and 56
second iteration:[62, 56, 66, 69, 71]
Second iteration:
finish the rest:
Explanation / Answer
QuickSort algorithm:
step-1 : choose the low index value as pivot
step-2 : Take two variables to point left and right of the list excluding pivot
step-3 : left points to the low index
step-4 : right points to the high index
step-5 : while value at left is less than pivot move right
step-6 : while value at right is greater than pivot move left
step-7: if both step-5 and step-6 does not match swap left and right
step-8 if left>= right, the point where they met is new pivot.
average and worst case time complexity are of O(n.log n)
QuickSort Pseudocode:
function partitionFunc(left,right,pivot)
leftPointer = left-1
rightPointer = right
while True do
while A[++leftPointer]<=pivot do
//do nothing
end while
while A[++leftPointer]<pivot do
//do nothing
end while
if leftPointer>=rightPointer
break;
else
swap leftPointer,rightPointer
end if
end while
swap leftPointer,right
return leftPointer
end function
--------------------------------------------------------------
procedure quickSort(left,right)
if right-left<=0
rerturn;
else
pivot = A[left]
partition = partitionFun(left, right, pivot)
quickSort(left,partition-1)
quickSort(partition+1,right)
end if
end procedure
-----------------------------------------------------------------
sorting this sublist: [62, 71, 66, 69, 56]
l = 0
r = 4
pivot: 62
move pivot at last
1st iteration [56, 71, 66, 69, 62]
now l=0 and r = 3
--------
2nd iteration: [56, 71, 66, 69, 62]
l = 1, r = 3, pivot = 62
---------
3rd iteration : [56, 71, 66, 69, 62]
l=1, r=2 and pivot=62
since r-l=1 swap r,pivot
-----------
4th iteration : [56, 62, 66, 69, 71]
l=0, r=1 and pivot=62
now the list is sorted
-------------------------------------------------------------------------------------------------------------------
lets go for second sub-list : [85, 92, 79, 97, 82, 99]
1st iteration: [85, 92, 79, 97, 82, 99]
pivot is 85, l=0,r=5
place pivot at last [99, 92, 79, 97, 82, 85]
l=0, r=4 and pivot= 85
swapt 99,82
2nd iteration: [82, 92, 79, 97, 99, 85]
l=0,r=4,pivot=85
3rd iteration : [82, 92, 79, 97, 99, 85]
l=1,r=4,pivot=85
4th iteration ; [82, 92, 79, 97, 99, 85]
l=1,r=3,pivot=85
5th iteration : [82, 92, 79, 97, 99, 85]
l=1,r=2 pivot=85
swap 92,79
[82, 79, 92, 97, 99, 85]
6th iteration
r-l=1
swap 92,85
[82, 79, 85, 97, 99, 92]
partition 1: l=0,r=2 list : [82,79,85] and partition 2 : l=3,r=5 list: [97,99,92]
apply alogithm for partion 1: l=0,r=2 list : [82,79,85]
iteration 1 : l=0,r=2, pivot = 82
keep pivot at last
[85,79,82]
l=0,r=1, list : [85,79,82]
swap 85,79
[79,85,82]
since r-l=1 swap r,pivot
[79,82,85]
list is sorted now goto partition 2
partition 2 : l=3,r=5 list: [97,99,92]
iteration 1: l=3,r=5,pivot 97
keep pivot at the end
[92,99,97]
iteration 2:
l=3,r=4 [92,99,97]
since r-l=1
swap r,pivot
[92,97,99]
now the list is sorted let combine partition 1 and partition 2 now
[79,82,85,92,97,99]
hence the solution
if you have any query feel free to ask, i am very delighted to help you.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.