0
$\begingroup$

Initial Bubble sort pseudocode(Typical):

1)foreach Element in array

2) initialise a flag that flips whenever a swap is done

3) Starting from the element, attempt to swap and update flag

4) If no swap is done, i.e flag remains true, break

We can improve the sorting algorithm further as values that are already sorted at the end of the array should not be checked in the subsequent passes. For example, when sorting [4,2,3,1,5,6], we get [2,3,1,4,5,6] after the first pass. We can see by observation that last 3 values (4,5,6) are already sorted and hence need not be looked at in the next pass.

I would think given the old source code[and my explained pseudocode], the checks will still be done in the inner loop even when previous outer iterations, no swap was done to a particular interval. I tried implementing a 2nd flag and an index variable to note the location which marks the start of a sorted interval. Here's my implementation in Java,I think it works, but I’m not sure whether I covered all cases.

Can someone verify if my algorithm is correct and if there is some flaw with it, please suggest an alternative.

The new pseudocode of my algorithm will be

1)foreach Element in array

2) initialise a flag that flips whenever a swap is done

3) if the localSorted flag is still true at the previous positions, break

4) Starting from the element, attempt to swap till end of array and update flag

5) Whenever a swap is done, the old localSorted status is questionable, hence set to false

6) If the localSorted status isnt changed even in the inner loop, break out

7) Otherwise set the localSorted at the first location

8) If no swap is done, i.e flag remains true, break

PS: Pardon me if my pseudocode is not really clear.

$\endgroup$
  • $\begingroup$ Unrelated to the actual question, but that does not look like "pseudocode"; it is more of a natural language (i.e., "English") description of an algorithm. $\endgroup$ – dkaeae Feb 28 at 7:32
  • $\begingroup$ Haha, I don't actually know what is the difference between both to be honest, pseudocode feels like Python code, but when I wrote something like that last time, someone accused me of using programming languages and make it unsuitable for the question, so now I just put the source code in a separate document. $\endgroup$ – Prashin Jeevaganth Feb 28 at 8:31
  • $\begingroup$ Pseudocode is a structured description which looks like ordinary code but has non-trivial, high-level statements in-between. The Wikipedia article seems a good read. Ultimately, it is about choosing the clearest and most readable presentation; if your algorithm idea is better expressed in (syntactically correct) Python, then that is the way it should be expressed. Only because you used a programming language in a question does not make it off-topic here; what makes it off-topic is asking about specifics of that concrete implementation. $\endgroup$ – dkaeae Feb 28 at 8:39
  • $\begingroup$ Is it off-topic just by putting my java code here[or just leaving it in this current state]? I believe I didn't use alot of Java syntax other than the declarations, and I also used as much API as possible so they are very verbose $\endgroup$ – Prashin Jeevaganth Feb 28 at 8:58
  • $\begingroup$ Asking about your Java implementation Java is off-topic. Asking whether your algorithm idea is correct (as an improvement over bubble sort), however, is on-topic. Hence, the question as it stands is in a gray zone; I presume an experienced user would answer it based on only the pseudocode you have given (and completely ignore your Java implementation). If that is not what you want, then you should consider posting the question on Stack Overflow or oven Code Review (and, as I've recommended, improving the presentation of your pseudocode or removing it altogether). $\endgroup$ – dkaeae Feb 28 at 9:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.