How do I make bubble sort work on range of indices?

Question

Hello SoloLearners,

I'm trying to customize bubble sort, where the method accepts a range of index <startIndex> and <lastIndex>. The goal was to sort array elements partially, from <startIndex> up to <lastIndex>.

But I think my implementation was logically flawed, cause it doesn't seem to be working as I'd expected it to be.

I need your help to find where I went wrong with the code, so I can fix it, please ...

Below I have attached the code link,

Thank you in advance 🙏

https://code.sololearn.com/cHi9pI0Ug0Sx/?ref=app

Answer 1

Ipang

I tried an own code and I think I got it now:

https://code.sololearn.com/cYufEED4AC1s/?ref=app

Assuming start = 3 and end = 5

In the first step you have to run from 3 to 5.
In the second step you can omit index 5 because it is already sorted.
But your outer loop starts at 3.

i = 3, last = 4
j = 3, k = last - i = 1
3 < 1 -> false

I think the problem can be solved if you start the outer loop at 0.

Answer 2

Denise Roßberg
Thanks very much 🙏

But I'm still not clear (sorry), so please if you have time, explain to me why `k = last - i` is causing this problem.

I got the base code from SoloLearn's bubble sort example https://www.sololearn.com/learn/651/?ref=app and in that code example it also decrease last index by 1 and <i> in the inner for loop

I really want to understand what I do wrong ...

Answer 3

The problem is that i is not starting at zero. The idea is that after the i-th iteration the i rightmost places in the array are sorted and thus do not need to be sorted again. It is just an improvement.

But your i is shifted by startIndex. You claim that the last startIndex places of your range are already sorted before you even start, which is not true. Whence the wrong result.

Simplest fix: shift i in the inner loop by startIndex

for( j = startIndex, k = last - (i-startIndex); j < k; j++

But a cleaner overall design would be better :) Like the one by Denise Roßberg.

Answer 4

Ani Jona 🕊
Thanks for pointing out the problem.

FYI I get the idea from Arrays.sort() which allows sorting in range. But then I got into trouble trying to sort in descending order because the array here contains primitive type values (no problem whatsoever when reference type were used).

Now I wonder how Arrays.sort() does ranged sorting, cause apart from the primitive vs reference type issue, it just works.

I was never any good with designs though, not too sure about the overall design thing 😁

Answer 5

Out of curiosity I made a split-sort using the tools provided by Java, in particular streams and functional programming to chain modular comparing strategies.

https://code.sololearn.com/cy22X7f8Z00Q

Answer 6

Ipang

I'm not sure but in your second loop: k = last
(instead of k = last - i)
Then it seems to work.

Answer 7

A bit of flashback ... this started with my attempt to answer a question, where (to my understanding), the OP has an array of `int`, and wants to group even numbers to the left, and odd numbers to the right. Plus different sorting order for even & odd numbers.

More of it here guys ...

https://code.sololearn.com/c7xBxYmeR565/?ref=app

Sorry if I confused anyone 😁

Answer 8

Ipang

Here is the source code of Arrays:
https://developer.classpath.org/doc/java/util/Arrays-source.html

I only had a rough look, but from what I can see, they use insertion sort for small arrays and quick sort for larger arrays.

Line 1716 -> sort(int[] a)
Line 1732 -> sort(int[] a, int fromIndex, int toIndex)

Line 2417 -> sort(Object a)

As you can see the sort method is overloaded so each type uses its own method. And they all have helper methods like swap(), qsort() and so on.

Answer 9

Denise Roßberg
A billion Thanks 🙏

Wow I should've figured such abilities won't be packed in small codes. Thousands of lines hides all the complexities LOL 😁

Answer 10

Remove unused variables,.. You may confused by lot of variables.. don't recall j value...
Just use, straight way :

for( int i = startIndex, tmp; i < lastIndex; i++ )
{
swapped = false;
for( int j = startIndex;j < lastIndex-1; j++ )
{

I hope this works...
Hope it helps...

Answer 11

Jayakrishna🇮🇳
Thanks for the hints 🙏

Some variables are there to cache calculation result. I just used them so the calculation doesn't repeat every time the loop condition is evaluated.

Answer 12

Jayakrishna🇮🇳
Yes it works still. I just have gotten used to caching evaluation results in loop.

About that Q&A, it's possible, but the OP hasn't been responding to my confirmation.

If it were possible, I'd mark all the answers here best, cause they are all helpful. But we know it's not possible.

Answer 13

Ipang Even if you retain variables, the way works I think.

May be it is solved but what I understood is for 2nd time sort,
first i = 5 last = 10-1=9
j=5 , k = last - i => 9-5=4 then j < k => 5<4 false so loop not starting..
May you got it already...

And from that q/a, may be OP need just a one left shift operation of array.. That's another way for that sample, I think..!!!

Answer 14

Ipang thanks for comments 🙏.
Oh that's enough for me. ..
But there are more deep answers than me I think.. Iam not gone through deep here. Iam glad if that helped you..