wanton mortar
Hello, I'm having trouble executing QuickSort and I've followed the steps one by one but the result is not what i was expecting.
The outcome is supposed to be a list where everything after pivot is greater than it and everything before pivot is less than it. Im sure I am doing something wrong but ive spend so much time trying to solve it again and again and i always have the same output.
Help would be appreciated!
willow aspenBOT
Hello, I'm having trouble executing QuickSort and I've followed the steps one by...
+close
slate light
what do you pivot around?
wanton mortar
Pivot is the first element of the list, 7.
Index 0
I'm not sure what you've done here, we're not solving QuickSort with trees but with the following way:
Pivot is element 0
F is element 1
L is element N-1
F moves to the right till it finds a value greater than pivot.
L moves to the left till it finds a value less than pivot.
Swapping elements F and L.
This goes on while F<L.
Swapping pivot with F unless L is less than F.
The algorithm continues but at this point, everything before pivot should be less than it and everything after pivot greater than it.
slate light
have to be more precise than that
F moves to the right till it finds a value greater than pivot.
L moves to the left till it finds a value less than pivot.
in what order does this happen
worthy sphinx
You can't really swap 6 and 9. Can you? Because your F is bigger than L here.
wanton mortar
You can't really swap 6 and 9. Can you? Because your F is bigger than L here.
according to the algorithm, if low > high, nothing should happen, the while loop would stop and
pivot should change with first/low
and it would be 7 6 9 8 -> 6 7 9 8
6 7 9 8
slate light
you have nested loops here
wanton mortar
damn
wanton mortar
you have nested loops here
yeah
wanton mortar
and it would be 7 6 9 8 -> 6 7 9 8
wait no
worthy sphinx
pivot should change with first/low
Yes, so what you have shown in second row would not happen.
worthy sphinx
and it would be 7 6 9 8 -> 6 7 9 8
This is correct.
wanton mortar
This is correct.
wait why would it be correct?low would've already changed
slate light
why won't you do sorting with binary trees? 
slate light
same, just recursive instead of nested loop nonsense
wanton mortar
thats how it is teached in uni
we will learn abt trees and data structs in next semester
slate light
rip
wanton mortar
yeah...
worthy sphinx
wait why would it be correct?low would've already changed
I am trying to say that that is the correct form your array should obtain after completion of algorithm for this pivot.
Btw, show rest of your code. This much seems fine. You might be making an error in next function calls.
wanton mortar
this is not my code, its the code from uni so it shouldnt be wrong, im just tryna understand how quicksort works
wanton mortar
my whole problem is why this specific algorithm doesnt work with 7 6 9 8
worthy sphinx
It is working fine.
Once the while loop ends, you have this instance:
first = 0
low = 2
high = 1
Now, it will run the if clause at the end and set list[first] = list[high] = 6.
Then, list[high] = pivot = 7
Your array is now
6 7 9 8.
wanton mortar
Once the while loop ends, you have this instance:
first = 0
low = 2
high = 1
N...
first and low is the same thing, did you mean pivot?
wait
worthy sphinx
No. They are not the same.
worthy sphinx
Yes
More precisely, it's the starting index of subarray to be partitioned but in this case, it's zero.
wanton mortar
the if statement won't run because high > low is false since high = 1 and low = 2
worthy sphinx
No. If statement after the outer while loop. Did you delete a picture?
I can swear it was there moments ago. Lol
There was a picture with an "if else clause" inside it. I'm talking about that one.
Wherein you are returning the index of pivot after partition is done.
wanton mortar
worthy sphinx
Yes. This one.
wanton mortar
if pivot > list[high]
if 0 > 1 (false)
worthy sphinx
Pivot is not 0.
wanton mortar
why
worthy sphinx
Pivot is value at index 0 which is 7.
wanton mortar
aint pivot the index itself
worthy sphinx
Look at your code.
Pivot = list[first].
worthy sphinx
aint pivot the index itself
No.
wanton mortar
oh yes
hmm
wait so because low>high the first if statement didnt happen
and
because pivot > list[high]
which means 7 > 6,
7 and 6 swapped
so the list is now 6 7 9 8
extremely interesting
thanks a lot i shouldve looked at the code in detail
worthy sphinx
Happy to help.
wanton mortar
+close
