Bubble Sort Algorithm?
Hello, this is about the 2 for loops of the bubble sort algorithm:
for (i = 0; i < array.length – 1; i++) {
for (j = 0; j < array.length – i – 1; j++) {
I don't really understand what the two loops do exactly. Especially, I don't understand what the -1 and (-i – 1) are all about. I know that arrays start with array[0], but I thought that was already taken into account with the simple < instead of <=. So, I can't quite explain it (maybe -1 because the largest element is already in its place after sorting in the loop and is no longer considered by the algorithm). I would be happy if someone could explain this to me somehow. I feel so stupid -_-
(1 votes)
Loading...
The animation illustrates this very well: https://de.wikipedia.org/wiki/Bubblesort#Principle
At Algo, a disadvantaged couple is always compared. If the array has the length array.length, then there are exactly array.length – 1 of such pairs:
(first, second), (second, third), …
There is no longer a pair that starts with the last element.
The largest element always moves to the right, so that after comparison and if necessary Exchange of penultimate and last element is known to be the largest element on the right. Only the first to the penultimate element must be compared and determined, which is the largest. The whole is repeated until only the first and second elements are compared in a loop.
Overall, the pairs to be compared have a triangular pattern:
1. Iteration: (1, 2), (2, 3), … (n-2, n-1), (n-1, n)
Two. Iteration: (1, 2), (2, 3), … (n-2, n-1)
…
(n-1).te Iteration: (1, 2)
Thank you :
First, you have to understand what the inner loop is doing: it iterates once over the array and always compares two adjacent elements. If the first element is larger than the second element, it is interchanged. This has the effect that the largest element lands at the end of the array, as it moves further backwards in each iteration by the interchange until it is at the rear. Here is an example:
After the first pass, the largest element is in the right place, but the rest of the array is still unsorted. To sort the whole array, you have to repeat it several times – for this the outer loop is there!
After the second passage, the last 2 elements are sorted correctly, after the third passage the last 3 elements, and so on. Around an array of length n it is enough to sort the whole thing n – repeat once.
In the inner loop, however, we do not have to iterate over the entire array. As already explained, i Iterates the last i Elements sorted correctly. So we can n – i – 1 Compare stop.
Where's the "-1"? Because in order to compare all adjacent elements in an array, you need a comparison less than the length of the array. For example, in an array of length 5, this is exactly 4 comparisons, as you see above.
Thank you, that was really super explained 🙂 I think I’ve been through it now. I am Wifo Ersti and the arrays make me a lot of trouble, just like this point notation :/