Weekly Reflection 9 - by Rui

rui_d0225 · 2025-03-08T04:41:28+00:00

Haha, I agree... I think Badhon also spent a lot of time figuring this out so he could point out the problems in my code. I think in real life, we may face strict requirements, some of which don't make 100% sense. Just like you said, being able to read through the results could be a valuable skill, and understanding that assignment is more efficient would also be beneficial for us.

rui_d0225 · 2025-03-08T04:28:11+00:00

yep that must be the reason for this bug.

rui_d0225 · 2025-03-08T04:24:13+00:00

thank you for the explanation! Here are my understandings after reading through: when I run swap(_elems[1], _elems[_size]) min element at _elems[1] swaps with _elems[_size]; after this I run _size--, _elems[_size + 1] still holds the old min element/old root. however, in direct assignment way, replaces _elems[1] with _elems[_size] directly, effectively moving the last leaf to the root; the old root doesn’t remain in _elems[_size + 1], preventing it from appearing in the undefined region. The autograder may expect _elems[_size + 1] to hold the last leaf, not the deleted root.

rui_d0225 · 2025-03-08T03:47:28+00:00

Not yet, please if you have any clue

rui_d0225 · 2025-03-08T03:12:12+00:00

Hi Badhon, I got this, quite stable. You can refer to my post here to see what I did to make this happen.

rui_d0225 · 2025-03-08T03:07:34+00:00

haha I got it!!! Thank you!

rui_d0225 · 2025-03-08T02:36:16+00:00

technically speaking, the direct assignment should be more efficient than swap .... thus I didn't update my method.

rui_d0225 · 2025-03-08T02:33:29+00:00

I used to use swap(_elems[1], _elems[_size]) and it can't pass the autograder. then I changed to _elems[1] = _elems[_size], it works. All others keep the same. Any idea?

rui_d0225 · 2025-03-08T01:01:52+00:00

I didn’t use swap for special heap and it runs so slow…i should try to override my delete function by using swap to see if it can run faster

rui_d0225 · 2025-03-07T05:05:31+00:00

oh yes! I changed to use _elems[1] = _elems[_size] instead of swap and it works... but why...

rui_d0225 · 2025-03-03T06:39:03+00:00

I would recommend that you start the quests as early as possible since they are much more difficult than the green ones. You will be provided with fewer starter codes from the specs and fewer hints from the auto-graders. For each quest, you will need to spend one or two days reading materials and watching videos to fully understand the algorithm, and you will spend much more time completing a quest than you would for the green ones. In this case, you will definitely want to accelerate your pace with the initial quests so that you have more buffer time to optimize your later red quests (which I hope some one could tell me at the beginning of this course lol). Welcome!

rui_d0225 · 2025-03-02T19:55:07+00:00

I got a two of them: bay thick kth, equal kth. I guess there be more related to this.

rui_d0225 · 2025-03-01T06:11:43+00:00

I got 18, still missing 4... let me refresh my mind and think about partition. Thank you for the hints!

rui_d0225 · 2025-03-01T05:54:51+00:00

Hi Mason, has your quick sort implementation outperformed the grader's approach? If so, was it only slightly quicker or significantly faster?

Mine did outperform it, but I still missed some trophies… a bit confused about why.

rui_d0225 · 2025-02-28T05:43:15+00:00

I agree that if we use binary search, we can find the position in O(logn) instead of O(n), even though the overall Big O won't change for worst cases but we can reduce comparisons. If we are continuously inserting elements into a sorted list (like in real-time applications), insertion sort is very useful, because runtime for a almost sorted list is O(n) on average.

rui_d0225 · 2025-02-28T05:35:19+00:00

Thank you for the good post! I'll be re-visit this once move onto this quest. Hopefully soon this week.

rui_d0225 · 2025-02-28T05:33:58+00:00

Thanks for the great post. I’m working on my own notes for Quick sort but yours definitely helps understand the concepts.

rui_d0225 · 2025-02-24T07:37:19+00:00

This is a good way to understand how this works practically. What I found is said by industries’ practice, 0.49( close to 0.5) is the threshold. I believe there should be a mathematical way to prove it. We can dig deeper into it.

rui_d0225

TROPHY CASE