I think my compiler warnings are on, im using Visual Studio 2019 (havent changed any of the settings).
I also debugged but that didnt show anything either.
The problem was this: (my code without the proper output)
The solution :Code:printf("\nDas ist der %i. Wert bei der sortierung: %i", e + 1, e + 1, array2[e]);
Code:printf("\nDas ist der %i. Wert bei der sortierung: %i: %i ", e + 1, e + 1, array2[e]);
I dont know if the compiler warns for things like that since its only missing %i
@Zeus_: re Bubblesorting Array elements
That is not bubble sort, it's insertion sort.
Apart from the discussion I've had with laserlight -- and I have conceded that her point about early termination is correct -- the code in your post is still not bubble sort because in bubble sort the inner loop steps in the opposite direction to the outer loop. Both your loops start from lower array indices and work upwards. In bubble sort the loops "step" in opposite directions; e.g. if the outer loop decrements the inner loop increments. If they both step in the same direction then it's insertion sort. Not that it matters to the OP or probably anyone else because insertion sort implemented this way (i.e. not quite right) has the same O complexity as bubble sort (although maybe CPU pipelines etc etc make a difference). OP doesn't care about what it's called anyway, but still...
Code:#include <stdio.h> #include <stdlib.h> #define NELEMS(a) (sizeof ((a)) / sizeof (a[0])) /* Exercise for reader to complete: Add printf()s to show the values of * i, j and the value of the elements being swapped. The difference between * dodgybubblesort() and dodgyinsertionsort() is quite apparent because of the * way the array is traversed. */ void bubblesort(int a[], size_t n) /* Knuth's algorithm */ { size_t i, j; int has_swapped = 1; j = n; while (has_swapped) { has_swapped = 0; for (i = 1; i < j; ++i) { if (a[i] < a[i - 1]) { int t = a[i]; /* Swap */ a[i] = a[i - 1]; a[i - 1] = t; has_swapped = 1; } } --j; } } void dodgybubblesort(int a[], size_t n) { size_t i, j; for(i = 1; i < n; ++i) { for(j = 0; j < i; ++j) { if(a[i] < a[j]) { int t = a[i]; /* Swap */ a[i] = a[j]; a[j] = t; } } } } void dodgyinsertionsort(int a[], size_t n) { size_t i, j; for (i = 1; i < n; ++i) { for (j = 0; j < i; ++j) { if (a[i] < a[j]) { int t = a[i]; /* Swap */ a[i] = a[j]; a[j] = t; } } } } void printarray(int a[], size_t n) { size_t i; for (i = 0; i < n; ++i) { printf("%d", a[i]); } printf("\n"); } int main(void) { /* Could use const arrays and copy but this is a quick and dirty * example */ int a1[] = {6, 5, 4, 3, 2, 1}; int a2[] = {6, 5, 4, 3, 2, 1}; int a3[] = {6, 5, 4, 3, 2, 1}; printf("bubble sorted : "); bubblesort(a1, NELEMS(a1)); printarray(a1, NELEMS(a1)); printf("dodgy bubble sorted: "); dodgybubblesort(a2, NELEMS(a2)); printarray(a2, NELEMS(a2)); printf("dodgy insert sorted: "); dodgyinsertionsort(a3, NELEMS(a3)); printarray(a3, NELEMS(a3)); return 0; }
This is not a bubble sort as it does not always swap adjacent elements:
I guess that's why you call it "dodgy bubble sort", but isn't that just misleading?Originally Posted by Hodor
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
Code:#include <stdio.h> #include <stdlib.h> #define NELEMS(a) (sizeof ((a)) / sizeof (a[0])) /* Exercise for reader to complete: Add printf()s to show the values of * i, j and the value of the elements being swapped. The difference between * dodgybubblesort() and dodgyinsertionsort() is quite apparent because of the * way the array is traversed. */ void bubblesort(int a[], size_t n) /* Knuth's algorithm */ { size_t i, j; int has_swapped = 1; j = n; while (has_swapped) { has_swapped = 0; for (i = 1; i < j; ++i) { if (a[i] < a[i - 1]) { int t = a[i]; /* Swap */ a[i] = a[i - 1]; a[i - 1] = t; has_swapped = 1; } } --j; } } void dodgybubblesort(int a[], size_t n) { size_t i, j; for (i = n - 1; i > 0; --i) { for (j = 0; j < i; ++j) { if (a[j + 1] < a[j]) { int t = a[j]; /* Swap */ a[j] = a[j + 1]; a[j + 1] = t; } } } } void dodgyinsertionsort(int a[], size_t n) { size_t i, j; for (i = 1; i < n; ++i) { for (j = 0; j < i; ++j) { if (a[i] < a[j]) { int t = a[i]; /* Swap */ a[i] = a[j]; a[j] = t; } } } } void printarray(int a[], size_t n) { size_t i; for (i = 0; i < n; ++i) { printf("%d", a[i]); } printf("\n"); } int main(void) { /* Could use const arrays and copy but this is a quick and dirty * example */ int a1[] = {6, 5, 4, 3, 2, 1}; int a2[] = {6, 5, 4, 3, 2, 1}; int a3[] = {6, 5, 4, 3, 2, 1}; printf("bubble sorted : "); bubblesort(a1, NELEMS(a1)); printarray(a1, NELEMS(a1)); printf("dodgy bubble sorted: "); dodgybubblesort(a2, NELEMS(a2)); printarray(a2, NELEMS(a2)); printf("dodgy insert sorted: "); dodgyinsertionsort(a3, NELEMS(a3)); printarray(a3, NELEMS(a3)); return 0; }
Yes, it's dodgy, but I edited my original post but it came up as a new post (?)
It's dodgy only because it's missing the terminating condition (well, Knuth's terminating condition). I don't know why the "edit post" made a new post rather than correcting the original one. But the main gist of things is the direction of the loops
Edit: I'm sorry it didn't edit the original post but I *did* hit edit post... I have no idea what happened
> That is not bubble sort, it's insertion sort.
I'm pretty sure that that is bubble sort. I looked up through three references after you said that and I can tell for sure that it is not insertion sort. In fact, I looked up GeeksforGeeks to check if my understanding of bubble and insertion sort are correct. The bubble sort code that I posted is correct and similar to the one on their website unless they're wrong too. Insertion sort looks completely different to me and the two are not different because of the direction of loop movement. Insertion finds the smallest element, finds its correct position, right shifts each array element by one place from the position determined of the current element, and then places it at that index. Bubble sort, on the other hand, compares and swaps continuously until, let's say, the heaviest element is placed at it's correct position in ascending order bubble sort.
Insertion Sort - GeeksforGeeks
Bubble Sort - GeeksforGeeks
This is what I've learnt at school too and so I don't know if I'm wrong but I'm just sharing what I know and what I've learnt
"Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning." - Rick Cook, The Wizardry Compiled
Bubble sort misconceptions
Right at the bottom of the page
Lol, if that's the truth, RIP the 94 people (in the PCMC stream) who've learnt Bubble and Insertion sort at school and the thousands, probably millions of people, referring to GeeksforGeeks.
F
Last edited by Zeus_; 12-11-2019 at 04:54 AM.
"Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning." - Rick Cook, The Wizardry Compiled
I guess that since in my first post (6 minutes before my corrected "dodgy" post) I implemented the dodgybubblesort() in a not-so-dodgy way is kind of how silly and confusing it is. But if I draw the iterations and swaps on paper, the dodgybubblesort() (second post!) is certainly what Knuth calls insertion sort (albeit badly implemented) and not what he calls bubble sort.
Who knows. All I can see (on paper) is that the two are different. I guess that if either are implemented incorrectly they "degenerate" to a badly implemented insertion sort. Both of my dodgy functions are not how Knuth describes them and they have the same time and space complexity -- they just work differently but in a subtle way. So in both dodgy implementations I'd probably say that, using Knuth's algorithm names, they're not even named algorithms because they're implemented incorrectly. They really are different though... add the printf()s and what you (Zeus_) wrote is very different to Knuth's description of bubblesort() which terminates when no exchanges/swaps occur (yours is what Knuth, and I, would call a not perfect insertion sort). I guess I can add the printf()s to the code or take a photo of my paper diagram but I'm kind of over it Insertion sort is the better algorithm (for these simple exchange sorts) and I'm having trouble deciding whether or not I've ever used bubble sort in my life. I really don't know. I know I've used the in-place insertion sort at times but the bubble sort... I dunno.
Edit: TBH, I had never really even thought about it until someone questioned in another thread if the code in that thread was insertion or bubble sort (I think @john.c). After seeing the query I looked at Knuth and the wikipedia pages and concluded that, yes, the code in the other thread was a poorly implemented insertion sort rather than a bubble sort (using Knuth's descriptions of the two algorithms).
Last edited by Hodor; 12-11-2019 at 05:20 AM.