1. ## Bubblesorting Array elements

Hello,

i need some help understand what im doing wrong. Please point me in the right direction.

i will just post the relevant code:

main function with :
Code:
```int main()
{
int array1[5];
int array2[5];

einlesen(array1, 5);
....
....

arraySortieren(&array2, 5);
for (int e = 0; e < 5; e++)
{
printf("\nDas ist der %i. Wert bei der sortierung: %i", e + 1, e + 1, array2[e]);
}

getchar();
return 0;
}```
the einlesen functions looks like this: (input from user for the array elements)
Code:
```void einlesen(int* array, int länge){
for (int i = 0; i < länge; i++)
{
printf("Gib hier einen Wert ein");
scanf("%i", &array[i]);
}
printf("\n");
}```
the arraySortieren function looks like this:
Code:
```void arraySortieren(int* array, int len){
int tempStorage = 0;

for (int e = len; e > 1; e--)
{
for (int i = 0; i < len - 1; i++)
{
if (array[i] < array[i + 1])
{
tempStorage = array[i];
array[i] = array[i + 1];
array[i + 1] = tempStorage;
}

tempStorage = 0;
}
}
}```

Now here is the problem:

i marked the relevant parts yellow.

2. I think your bubble sort is wrong...

Ascending order bubble sort:
Code:
```void BubbleSort (int* Array , int Size)
{
int Temp; // int ctr = 0

for (int i = 0; i < Size; i++)
{
for (int j = 0; j < Size - i - 1; j++)
if (Array [j] > Array [j + 1])
{
Temp = Array [j];
Array [j] = Array [j + 1];
Array [j + 1] = Temp;
}

/*
std::cout << " Array after iteration - " << ++ctr << " - is: ";
for (int k = 0; k < Size; k++)
std::cout << Array [k] << " ";
std::cout << endl;
*/
}
}```
For descending order, change the > in if statement to <.

3. Eh, I'm really curious who has been going around teaching students to implement a bubble sort that doesn't stop when no more swaps are performed.

4. Originally Posted by laserlight
Eh, I'm really curious who has been going around teaching students to implement a bubble sort that doesn't stop when no more swaps are performed.
Interestingly, this website (Bubble Sort: An Archaeological Algorithmic Analysis) gives the following example (this is not a bubble sort):

Code:
```    for(int j=n-1; j > 0; j--)
for(int k=0; k < j; k++)
if (a[j] < a[k])
Swap(a,k,j);```
and goes on to say that this code snippet is "what is essentially a selection sort, but the current maximal element is stored/swapped into location a[j] on each pass"

Maybe lots of intro to programming textbooks are copying each other's "bubble sorts" and therefore all ending up with something that is not really a bubble sort at all. In my opinion the OPs code (and something the other day) more closely resembles this than bubble sort. Oh Well. Maybe Hodor is just getting too old.

5. Originally Posted by Hodor
In my opinion the OPs code (and something the other day) more closely resembles this than bubble sort.
They don't: this one doesn't always swap adjacent elements. Perhaps you missed:
Taking the description of bubble sort in [17] as definitive the code below is bubble sort. This version ``bubbles'' the largest elements to the end of the vector.

Code:
```void BubbleSort(Vector a, int n)
{
for(int j=n-1; j > 0; j--)
for(int k=0; k < j; k++)
if (a[k+1] < a[k])
Swap(a,k,k+1);
}```
Nearly every description of bubble sort describes how to terminate the sort early if the vector becomes sorted. This optimization requires checking if any swaps are made and terminating if no swaps are made after j iterations of the inner loop.
So, if you agree that terminating early is an optimisation for bubble sort, then it follows that terminating early is not a necessary condition for a sort to be a bubble sort. If you disagree, then it follows that this article that you linked makes an incorrect claim, i.e., the code shown is not bubble sort. However, the note 17 is "Knuth, D. The Art of Computer Programming: Sorting and Searching, 2 ed., vol. 3. Addison-Wesley, 1998.", which implies that contrary to your previous assertions, Knuth agrees that this is still (inefficient even compared to the canonical) bubble sort.

6. Originally Posted by laserlight
They don't: this one doesn't always swap adjacent elements. Perhaps you missed:

So, if you agree that terminating early is an optimisation for bubble sort, then it follows that terminating early is not a necessary condition for a sort to be a bubble sort. If you disagree, then it follows that this article that you linked makes an incorrect claim, i.e., the code shown is not bubble sort. However, the note 17 is "Knuth, D. The Art of Computer Programming: Sorting and Searching, 2 ed., vol. 3. Addison-Wesley, 1998.", which implies that contrary to your previous assertions, Knuth agrees that this is still (inefficient even compared to the canonical) bubble sort.
Fair enough, the webpage I linked to is wrong.

I have the book open in front of me now (I needed to re-read it based on your feedback) and Knuth does not state that terminating early is an optimization of bubble sort but an intrinsic part of it (pages 106-107). The only algorithm he gives (Fig 15 and Program B, p. 107) is based on the text discussion and has no swaps occurring as the terminating condition. In the section "refinements of the bubble sort" (pp. 109-110) Knuth does not present terminating early as a refinement because he's already said that the algorithm ends when no exchanges occur (discussion on pages 106-107 and Fig. 15). So it's not a refinement or an optimization according to my interpretation of Knuth.

7. Originally Posted by laserlight
Eh, I'm really curious who has been going around teaching students to implement a bubble sort that doesn't stop when no more swaps are performed.
Or teaching bubble sort at all.

Double, double toil and trouble;
File burn and data bubble.
Eye of Knuth and n-squared sorts
Code of newbs so full of warts.

8. Originally Posted by Zeus_
I think your bubble sort is wrong...

Ascending order bubble sort:
Code:
```void BubbleSort (int* Array , int Size)
{
int Temp; // int ctr = 0

for (int i = 0; i < Size; i++)
{
for (int j = 0; j < Size - i - 1; j++)
if (Array [j] > Array [j + 1])
{
Temp = Array [j];
Array [j] = Array [j + 1];
Array [j + 1] = Temp;
}

/*
std::cout << " Array after iteration - " << ++ctr << " - is: ";
for (int k = 0; k < Size; k++)
std::cout << Array [k] << " ";
std::cout << endl;
*/
}
}```
For descending order, change the > in if statement to <.

I dont think its the code for the bubble sort algorithm thats wrong. I changed mine to match yours to check if that was the problem, but the output is still : 1 2 3 4 5
It doesnt sort my input but instead just outputs 1-5.

9. by the way, i used this as a template(?) for my code, (its from the german wiki)

Code:
```bubbleSort(ArrayA)  for (n=A.size; n>1; --n){
for (i=0; i<n-1; ++i){
if (A[i] > A[i+1]){
A.swap(i, i+1)
} // Ende if
} // Ende innere for-Schleife }// Ende äußere for-Schleife```

The algorithm itself doesnt matter too much if its the proper bubble algorithm code or not (since i got it from wiki), i cant get the proper output, thats my main problem.

Now since im quite a noob yet, i still havent figured out what the problem is.

Our Teacher said we could try to do this since its for more advanced students and my class is just an introduction to C.(basic C stuff)

10. Code:
```void BubbleSort (int* Array , int Size)
{
int i , j , Temp;
bool SwapOccurred;

for (i = 0; i < Size - 1; i++)
{
SwapOccurred = false;
for (j = 0; j < Size - i - 1; j++)
{
if (Array [j] > Array [j + 1])
{
Temp = Array [j];
Array [j] = Array [j + 1];
Array [j + 1] = Temp;
SwapOccurred = true;
}
}
if (!SwapOccurred) break;
}
}```
This is what @laserlight mentions about. The other post of mine was written in a hurry so I didn't bother optimising it. I think this is the most optimal it gets but don't know for sure.
Also, @laserlight, are XOR swaps faster?

11. I dont think its the code for the bubble sort algorithm thats wrong. I changed mine to match yours to check if that was the problem, but the output is still : 1 2 3 4 5
It doesnt sort my input but instead just outputs 1-5.
What's your input? (1,2,3,4,5) ? If that's the case, and you want 5,4,3,2,1, you need to change the > in if statement to <

> printf("\nDas ist der %i. Wert bei der sortierung: %i", e + 1, e + 1, array2[e]);

You are missing a % before the i in 'ist' and that's why you get 1,2,3,4,5 always. I didn't see the mistake until now....

12. Originally Posted by Zeus_
What's your input? (1,2,3,4,5) ? If that's the case, and you want 5,4,3,2,1, you need to change the > in if statement to <
I do the input with scanf in another void function:
Code:
```void einlesen(int* array, int länge){
for (int i = 0; i < länge; i++)
{
printf("Gib hier einen Wert ein");
scanf("%i", &array[i]);
}
printf("\n");
}```
in the main function then i call the scanf function :
Code:
`einlesen(array2, 5);`
and then i call the bubblesort function(with the output):
Code:
```arraySortieren(&array2, 5);    for (int e = 0; e < 5; e++)
{
printf("\nDas ist der %i. Wert bei der sortierung: %i", e + 1, e + 1, array2[e]);
}```
so whatever my input is, it should normal get sorted with the bubblesort function(or am i wrong?)

13. See #4. You're missing a % before 'ist'

14. Originally Posted by Zeus_
See #4. You're missing a % before 'ist'
oh my god, your right. It didnt even cross my mind (nor my eyes) to look at that.

Now it works properly, thanks for point that out to me.

15. @Zeus_ XOR integer swaps are, in general, probably not faster on modern CPUs (and actually might be slower) than the trivial approach using a temporary variable. Compiler optimisations have improved along with architecture advances, optimizing the temp variable away, and in general the obvious approach of using a temporary variable is, in my experience, generally considered the best approach. The only places I use the XOR trick is for my Motorola 6502, 6510 and 68k programs and very few people care about these CPUs, and the code I write for them, anyhow. I vaguely recall using the XOR approach when I was writing 486 asm for a brief period but I think that was from habit rather than any empirical evidence that it was actually faster (I cannot recall ever actually testing or analysing it for speed on the 486); it's possible that the XCHG instruction (and friends) was faster than the xor trick even on 486 but I have no evidence for that because... too long ago

Edit, Something to ponder: I am confident that CPU designers are aware of the XOR bitwise swap and that however they actually do it in hardware as a single instruction is extremely likely to be faster than anything my compiler can spit out.