VCE Stuff > VCE Computing: Software Development

Quick Sort Exam Question

<< < (2/2)

JeromeTT:
Which exam?

JeromeTT:
This question would probably never appear on a VCAA paper, but i'll try to give my thought process
I've highlighted the pivot in bold, and solved sections in red
{ 1,7,6,4,3,9,11}

The key point of quick sort is that all the values which are lower get moved to the left of the pivot and all the higher ones get right.
So in this array nothing changes.

Moving on to the next pivot (pivot is on the left as stated in the pseudo code)
{ 1,7,6,4,3,9,11}

All the lower values moved to the left.
{ 1,6,4,3,7,9,11}
{ 1,6,4,3,7,9,11}
{ 1,4,3,6,7,9,11}
{ 1,4,3,6,7,9,11}
{ 1,4,3,6,7,9,11}
{ 1,4,3,6,7,9,11}
{ 1,3,4,6,7,9,11}

Therefore 4 is the value of the last pivot.

yourfriendlyneighbourhoodghost:

--- Quote from: JeromeTT on October 19, 2019, 11:57:09 pm ---This question would probably never appear on a VCAA paper, but i'll try to give my thought process
I've highlighted the pivot in bold, and solved sections in red
{ 1,7,6,4,3,9,11}

The key point of quick sort is that all the values which are lower get moved to the left of the pivot and all the higher ones get right.
So in this array nothing changes.

Moving on to the next pivot (pivot is on the left as stated in the pseudo code)
{ 1,7,6,4,3,9,11}

All the lower values moved to the left.
{ 1,6,4,3,7,9,11}
{ 1,6,4,3,7,9,11}
{ 1,4,3,6,7,9,11}
{ 1,4,3,6,7,9,11}
{ 1,4,3,6,7,9,11}
{ 1,4,3,6,7,9,11}
{ 1,3,4,6,7,9,11}

Therefore 4 is the value of the last pivot.

--- End quote ---

How did you make quick sort look so easy lol? Thank you a bunch (: even though this wasn't my problem to be solved haha

JeromeTT:

--- Quote from: yourfriendlyneighbourhoodghost on October 17, 2019, 04:21:46 pm ---I am also confused, I though quick sort was just taking tye first number and swapping it each run, to have the numbers in chronological order. Are there any misconceptions in my behalf?

--- End quote ---

Yes you are correct in your understanding (i think).

For a quick sort visualiser visit this website
https://visualgo.net/bn/sorting
Just click on QUI on the top bar to go to quick sort.

However the pseudo code above is a bit different from how the site above does quicksort.
In the pseudo code line 8 states that the pivot IS the index you swap with, while in the website is states that pivot + 1 is the index to swap with.
This means that according to the pseudo code, all the lower values end up on the left without change in order, and same with the right.

I really doubt VCAA will have quicksort pseudocode on the exam, especially when they can't even do basic pseudocode (VCAA 2018 Exam Find the error  :) )

Unsplash:

--- Quote from: JeromeTT on October 21, 2019, 01:37:19 pm ---I really doubt VCAA will have quicksort pseudocode on the exam, especially when they can't even do basic pseudocode (VCAA 2018 Exam Find the error  :) )

--- End quote ---

How annoying was that mistake! Spent so long deciding whether to follow the pseudocode or the written instructions they gave us.

Navigation

[0] Message Index

[*] Previous page