-3
$\begingroup$

I have done absolutely everything that i could to try to understand this algorithm. I did NOT want to go on without understanding it completely even though I know it might only be a single problem in the midterm and I think I might have already burned myself out anyways. I even performed the algorithm by hand, which did allow me to understand that when the high_border and low_border indices are equal, to only swap it with the pivot if arr[low_border] is greater than the pivot. This helped when I was trying to sort the following array: {3, 4, 1, 7, 5, 8, 0}. But even then, the computer only sometimes sorts it correctly. The same can be said for any other list. Here is the video that I tried to follow when learning about this algorithm:

https://www.youtube.com/watch?v=Fiot5yuwPAg&t=59s

Please help me, I have been at this for 9 total hours (3 last night, 3 before I went to class and another 3 right after class).

The full code for the program(in java) is here: https://pastebin.com/cRF1xjcs

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ A suggestion for you. Have a piece of paper, a pencil. Randomly pick 10 or more un-sorted numbers. Follow the algorithm, see if you can manually sort the numbers before you jump to the code. $\endgroup$
    – Nobody
    Oct 11, 2018 at 1:36
  • $\begingroup$ This seems more like a debugging question than a computer science question. Are you confused about the algorithm in general, or why your code isn't working? $\endgroup$
    – Draconis
    Oct 11, 2018 at 4:12

1 Answer 1

Reset to default
2
$\begingroup$

Elements that are equal to the pivot are not getting moved correctly. You need to change one of your checks (> or <, pick one; usual choice is to use >=) to include the equal case in partition. Also, your else if (high_border == low_border) can just be else, since that is your only option by your while loop break condition. In that case, you do not always swap end with something in the middle so that the pivot remains at the end of the array after every element larger than it in some cases. Switching the > to >= as I mentioned may fix that, but I would put an else case to swap the pivot with high_border just in case. Then you would also need to return high_border. I don't see any other problems with your code, but those couple of fixes are majorly important.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Sorry for responding very late, but which checks are you referring to? $\endgroup$
    – Michael Duboc
    Oct 31, 2018 at 18:45
  • $\begingroup$ I mean just testing less than or greater than causes issues when elements compare equal. Use >= instead of >. $\endgroup$
    – HackerBoss
    Nov 1, 2018 at 3:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.