Login

Welcome, Guest. Please login or register.

March 29, 2024, 05:36:13 am

Author Topic: Quick Sort Exam Question  (Read 3521 times)  Share 

0 Members and 1 Guest are viewing this topic.

bobovikisan

  • Adventurer
  • *
  • Posts: 13
  • Gnobbling Gnott Gnome
  • Respect: 0
Quick Sort Exam Question
« on: October 14, 2019, 07:44:27 pm »
0
Hi guys this is a question that I have been doing!

Let A[] be an array of integers { 1,7,6,4,3,9,11}. What is the value of the pivot in line 7after a first run of the code in the “Partition” part?
Refer to the attachment of the image for the question. (I know! I know! the sort function has lowercase, but its a typo it should be uppercase)

The answer I got was 6, however the solutions says 4 without any explanation.
Also how do you know when the first run occurs in a recursive algorithm?
What is the precise definition of a first run?

Thanks Guys!
« Last Edit: October 14, 2019, 08:21:40 pm by bobovikisan »

Chessnutter

  • Trailblazer
  • *
  • Posts: 33
  • Respect: +4
Re: Quick Sort Exam Question
« Reply #1 on: October 17, 2019, 01:00:25 pm »
0
Would you be able to provide an image of the entire question please?
From my understanding of the question, the value of the pivot when line 7 is 'first run' is 1.
Offering tutoring for Algorithmics, Methods, Further and Software Development. Message me

Bachelor of Computer Science Advanced (Honours) at Monash

ATAR: 98.95
2019:
Software Development (45)
2020:
Algorithmics (40)
Methods (42)
Further (50)
English (42)
Data Analytics (36)

yourfriendlyneighbourhoodghost

  • Forum Obsessive
  • ***
  • Posts: 204
  • sleep now and dream, study now and live your dream
  • Respect: +34
Re: Quick Sort Exam Question
« Reply #2 on: October 17, 2019, 04:21:46 pm »
0
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?
2018: Studio Arts [37]
2019: English [38] Psychology [38] Vis Com [36] Software Development [40] Further Maths [35]
ATAR: 87.95 ❤️

2020-2023 Bachelor of Arts @ Unimelb

bobovikisan

  • Adventurer
  • *
  • Posts: 13
  • Gnobbling Gnott Gnome
  • Respect: 0
Re: Quick Sort Exam Question
« Reply #3 on: October 19, 2019, 10:40:21 am »
0
I believe that's selection sort ;D

bobovikisan

  • Adventurer
  • *
  • Posts: 13
  • Gnobbling Gnott Gnome
  • Respect: 0
Re: Quick Sort Exam Question
« Reply #4 on: October 19, 2019, 10:54:07 am »
0

The image is bigger than 3000kb I can't post :(
I double checked that is the question. I copied and pasted it.

However I think the algorithm it self is written wrong. By first run I think it means go through every single line of code at least once

JeromeTT

  • Trailblazer
  • *
  • Posts: 49
  • Respect: +2
Re: Quick Sort Exam Question
« Reply #5 on: October 19, 2019, 11:37:10 pm »
0
Which exam?
2018 - Software Development [49], Further Maths [50]

2019 - English [32], Maths Methods [38], Specialist Maths [31], Physics [37]
ATAR: 97.35

2020-2023
Bachelor of Computer Science Advanced (Hons) @ Monash

JeromeTT

  • Trailblazer
  • *
  • Posts: 49
  • Respect: +2
Re: Quick Sort Exam Question
« Reply #6 on: October 19, 2019, 11:57:09 pm »
+3
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.
2018 - Software Development [49], Further Maths [50]

2019 - English [32], Maths Methods [38], Specialist Maths [31], Physics [37]
ATAR: 97.35

2020-2023
Bachelor of Computer Science Advanced (Hons) @ Monash

yourfriendlyneighbourhoodghost

  • Forum Obsessive
  • ***
  • Posts: 204
  • sleep now and dream, study now and live your dream
  • Respect: +34
Re: Quick Sort Exam Question
« Reply #7 on: October 20, 2019, 05:06:10 pm »
0
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.

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
2018: Studio Arts [37]
2019: English [38] Psychology [38] Vis Com [36] Software Development [40] Further Maths [35]
ATAR: 87.95 ❤️

2020-2023 Bachelor of Arts @ Unimelb

JeromeTT

  • Trailblazer
  • *
  • Posts: 49
  • Respect: +2
Re: Quick Sort Exam Question
« Reply #8 on: October 21, 2019, 01:37:19 pm »
+2
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?

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  :) )

2018 - Software Development [49], Further Maths [50]

2019 - English [32], Maths Methods [38], Specialist Maths [31], Physics [37]
ATAR: 97.35

2020-2023
Bachelor of Computer Science Advanced (Hons) @ Monash

Unsplash

  • Forum Regular
  • **
  • Posts: 61
  • Respect: +9
Re: Quick Sort Exam Question
« Reply #9 on: October 24, 2019, 06:39:45 pm »
+1
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  :) )

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