Thread: Bubblesorting Array elements

  1. #1
    Registered User
    Join Date
    Dec 2019
    Posts
    8

    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:

    Bubblesorting Array elements-unbenannt4-jpg

    i marked the relevant parts yellow.

  2. #2
    Registered User
    Join Date
    Aug 2019
    Location
    Inside a Singularity
    Posts
    230
    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 <.
    Last edited by Zeus_; 12-10-2019 at 11:09 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

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,416
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,682
    Quote Originally Posted by laserlight View Post
    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. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,416
    Quote 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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,682
    Quote Originally Posted by laserlight View Post
    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. #7
    Registered User
    Join Date
    Dec 2017
    Posts
    790
    Quote Originally Posted by laserlight View Post
    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.
    The world hangs on a thin thread, and that is the psyche of man. - Carl Jung

  8. #8
    Registered User
    Join Date
    Dec 2019
    Posts
    8
    Quote Originally Posted by Zeus_ View Post
    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. #9
    Registered User
    Join Date
    Dec 2019
    Posts
    8
    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. #10
    Registered User
    Join Date
    Aug 2019
    Location
    Inside a Singularity
    Posts
    230
    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?
    "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

  11. #11
    Registered User
    Join Date
    Aug 2019
    Location
    Inside a Singularity
    Posts
    230
    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....
    Last edited by Zeus_; 12-11-2019 at 03:15 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

  12. #12
    Registered User
    Join Date
    Dec 2019
    Posts
    8
    Quote Originally Posted by Zeus_ View Post
    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. #13
    Registered User
    Join Date
    Aug 2019
    Location
    Inside a Singularity
    Posts
    230
    See #4. You're missing a % before 'ist'
    "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

  14. #14
    Registered User
    Join Date
    Dec 2019
    Posts
    8
    Quote Originally Posted by Zeus_ View Post
    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. #15
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,682
    @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.
    Last edited by Hodor; 12-11-2019 at 03:44 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. passing array elements as an index to another array
    By kshruti1 in forum C Programming
    Replies: 6
    Last Post: 08-06-2019, 07:03 AM
  2. Replies: 2
    Last Post: 01-05-2019, 12:35 AM
  3. Replies: 2
    Last Post: 12-07-2011, 11:22 PM
  4. Sum of all elements in an array
    By SilentPirate007 in forum C Programming
    Replies: 6
    Last Post: 05-02-2010, 08:32 AM
  5. array of zero elements
    By George2 in forum C++ Programming
    Replies: 8
    Last Post: 02-17-2008, 07:10 AM

Tags for this Thread