Thread: Fill in the blank code - generic Bubble sort - C

  1. #1
    Registered User
    Join Date
    Nov 2019
    Posts
    135

    Fill in the blank code - generic Bubble sort - C

    Hello everyone.

    This is the correct filling of generic bubble sort code.

    Some little technical question about the first argument of genSort function -
    According to the main, I thought the right type to be passed at first is of ConstElement type, as the main defines an array of 5 ConstElement (which is defining an array of 5 const void pointers).
    Now, when we pass at the main the first argument (arrToSort) - we are actually passing the pointer to the first element which is of ConstElement type as I see the things.

    But, we see that the correct argument type of genSort function is Element.


    What's the problem with my understanding?

    Thanks!

    Code:
    #include <stdio.h>
    #include <assert.h>
    
    
    typedef void* Element;
    typedef const void* ConstElement;
    
    
    void genSort(Element arrToSort, int arrSize, int (*less)(ConstElement, ConstElement))
    {
        int numOfPasses;
        if (arrSize < 2)
            return;
        for (numOfPasses = 0 ; numOfPasses < arrSize ; ++numOfPasses) {
            int it;
            for (it = 0 ; it < arrSize - 1 ; ++it) {
                if (less(arrToSort[it+1], arrToSort[it]))
                {
                    ConstElement temp = arrToSort[it+1];
                    arrToSort[it+1] = arrToSort[it];
                    arrToSort[it] = temp;
                }
            }
        }
    }
    
    
    int IntLess(ConstElement a, ConstElement b) {
        int *i1 = (int*) a;
        int *i2 = (int*) b;
        assert(i1 != NULL && i2 != NULL);
        return (*i1 < *i2);
    }
    
    
    int main() {
        int A[5] = {5, 6, 2, 23, 9};
        int tempi;
        ConstElement arrToSort[5];
        for (tempi = 0 ; tempi < 5 ; ++tempi)
            arrToSort[tempi] = A + tempi;
        genSort(arrToSort, 5, &IntLess);
        /* will print 2 */
        printf("arrToSort[0] = %d\n", *((int *) arrToSort[0]));
        return 0;
    }

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,389
    That doesn't look correct to me: since arrToSort is a void*, arrToSort[i] is illegal as pointers to void cannot be dereferenced.

    By the way, it would be better not to typedef the pointer types here. Just leaving them as void* and const void* would make this kind of thing easier to spot. But your compiler should have complained... or you might be using a language extension.

    As for your question: well, you're going to be copying over, so the parameter should be void* not const void* since what it points to will be modified, whereas for comparing const void* makes sense because a comparison logically doesn't involve modification. I would have directly passed A to arrToSort in main, but then I would have also provided the size of an element to arrToSort.

    I suspect that you actually are supposed to sort pointers instead, that's why there's no element size. If so, then the arrToSort parameter is of the wrong type: it should be const void** instead, whereupon you're sorting const void* pointers themselves, not sorting ints via void* pointers.

    EDIT:
    Ah, I see it now. Yes, you're supposed to sort pointers to const void. Your intuition here is almost correct:
    Quote Originally Posted by HelpMeC
    Now, when we pass at the main the first argument (arrToSort) - we are actually passing the pointer to the first element which is of ConstElement type as I see the things.
    The thing is, arrToSort in main is an array to 5 const void*. Therefore, when passed as an argument, it becomes a const void**. So, the arrToSort parameter should be a const void**, i.e., a ConstElement*. Hence, the example's use of Element as the type is wrong, and your thinking of ConstElement is almost there.

    This also means that arrToSort[i] is okay: the result is a const void*, i.e., a ConstElement.
    Last edited by laserlight; 12-04-2019 at 01:21 PM.
    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

  3. #3
    Registered User
    Join Date
    Feb 2019
    Posts
    581
    This doen't seem to be bubble sort, but insertion sort...
    Insertion Sort
    Bubble Sort

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,389
    Quote Originally Posted by flp1969 View Post
    This doen't seem to be bubble sort, but insertion sort...
    Insertion Sort
    Bubble Sort
    It's bubble sort: the inner loop does repeated comparison of adjacent items and swaps them if they are out of order. The outer loop loops enough times to ensure that there are enough inner loop iterations to sort the entire range even in the worst case.
    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

  5. #5
    Registered User
    Join Date
    Nov 2019
    Posts
    135
    @laserlight
    First, thank you.

    I'm really confused by now.
    I have attached the image to the exercise as given.

    - Now you have turned my attention to the copy:
    We are really modifying the content of the elements - so, how is it legal to swap the elements (which are const void*) of the arrToSort in genSort function?

    Thank you!
    Attached Images Attached Images Fill in the blank code - generic Bubble sort - C-jpg 

  6. #6
    Registered User
    Join Date
    Nov 2019
    Posts
    135
    - And another point -
    When we pass in main the argument arrToSort - we are actually passing the address of the first ConstElement in arrToSort?
    Which is a pointer to ConstElement?

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,389
    Quote Originally Posted by HelpMeC
    We are really modifying the content of the elements - so, how is it legal to swap the elements (which are const void*) of the arrToSort in genSort function?
    It's legal because you know exactly what you're sorting: const void* objects. Basically, the idea is to sort pointers rather than the original int objects themselves. So, the sorted pointers will point to the int objects in their sorted order, without actually changing the original order of the int objects.

    Quote Originally Posted by HelpMeC
    When we pass in main the argument arrToSort - we are actually passing the address of the first ConstElement in arrToSort?
    Which is a pointer to ConstElement?
    Yes.
    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

  8. #8
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,646
    Quote Originally Posted by laserlight View Post
    It's bubble sort: the inner loop does repeated comparison of adjacent items and swaps them if they are out of order. The outer loop loops enough times to ensure that there are enough inner loop iterations to sort the entire range even in the worst case.
    Looks like insertion sort to me as well. According to Knuth (Vol 3) and Wikipedia the defining feature of insertion sort is that the terminating condition is when no swaps have occurred.

  9. #9
    Registered User
    Join Date
    Nov 2019
    Posts
    135
    @laserlight

    Ahh, do you mean the integer values themselves are the constant here and not the const void pointers themselves - thus, we can perform assignments on them?

    Thank you so much!

  10. #10
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,646
    Quote Originally Posted by HelpMeC View Post
    @laserlight
    First, thank you.

    I'm really confused by now.
    I have attached the image to the exercise as given.

    - Now you have turned my attention to the copy:
    We are really modifying the content of the elements - so, how is it legal to swap the elements (which are const void*) of the arrToSort in genSort function?

    Thank you!
    How is that legal?! It doesn't even compile!

    Code:
    #include <stdio.h>
    #include <assert.h>
    
    
    typedef void* Element;
    typedef const void* ConstElement;
    
    
    void genSort(Element arrToSort, int arrSize, int (*less)(ConstElement, ConstElement))
    {
        int numOfPasses;
        if (arrSize < 2)
            return;
        for (numOfPasses = 0 ; numOfPasses < arrSize ; ++numOfPasses) {
            int it;
            for (it = 0 ; it < arrSize - 1 ; ++it) {
                if (less(arrToSort[it+1], arrToSort[it]))
                {
                    Element temp = arrToSort[it+1];
                    arrToSort[it+1] = arrToSort[it];
                    arrToSort[it] = temp;
                }
            }
        }
    }
    
    
    int IntLess(ConstElement a, ConstElement b) {
        int *i1 = (int*) a;
        int *i2 = (int*) b;
        assert(i1 != NULL && i2 != NULL);
        return (*i1 < *i2);
    }
    
    
    int main() {
        int A[5] = {5, 6, 2, 23, 9};
        int tempi;
        ConstElement arrToSort[5];
        for (tempi = 0 ; tempi < 5 ; ++tempi)
            arrToSort[tempi] = A + tempi;
        genSort(arrToSort, 5, &IntLess);
        /* will print 2 */
        printf("arrToSort[0] = %d\n", *((int *) arrToSort[0]));
        return 0;
    }
    
    
    
    $ gcc -Wall isort.c 
    isort.c: In function ‘genSort’:
    isort.c:17:31: warning: dereferencing ‘void *’ pointer
       17 |             if (less(arrToSort[it+1], arrToSort[it]))
          |                               ^
    isort.c:17:48: warning: dereferencing ‘void *’ pointer
       17 |             if (less(arrToSort[it+1], arrToSort[it]))
          |                                                ^
    isort.c:17:31: error: invalid use of void expression
       17 |             if (less(arrToSort[it+1], arrToSort[it]))
          |                      ~~~~~~~~~^~~~~~
    isort.c:17:48: error: invalid use of void expression
       17 |             if (less(arrToSort[it+1], arrToSort[it]))
          |                                       ~~~~~~~~~^~~~
    isort.c:19:41: warning: dereferencing ‘void *’ pointer
       19 |                 Element temp = arrToSort[it+1];
          |                                         ^
    isort.c:19:32: error: void value not ignored as it ought to be
       19 |                 Element temp = arrToSort[it+1];
          |                                ^~~~~~~~~
    isort.c:20:26: warning: dereferencing ‘void *’ pointer
       20 |                 arrToSort[it+1] = arrToSort[it];
          |                          ^
    isort.c:20:44: warning: dereferencing ‘void *’ pointer
       20 |                 arrToSort[it+1] = arrToSort[it];
          |                                            ^
    isort.c:20:33: error: invalid use of void expression
       20 |                 arrToSort[it+1] = arrToSort[it];
          |                                 ^
    isort.c:21:26: warning: dereferencing ‘void *’ pointer
       21 |                 arrToSort[it] = temp;
          |                          ^
    isort.c:21:31: error: invalid use of void expression
       21 |                 arrToSort[it] = temp;

    Also, if you fix things and change line 9 to (adding the * before arrToSort)
    Code:
    void genSort(Element *arrToSort, int arrSize, int (*less)(ConstElement, ConstElement))
    It will compile but discards the const qualifiers all over the place:
    Code:
    $ gcc -Wall isort.c 
    isort.c: In function ‘main’:
    isort.c:42:13: warning: passing argument 1 of ‘genSort’ from incompatible pointer type [-Wincompatible-pointer-types]
       42 |     genSort(arrToSort, 5, &IntLess);
          |             ^~~~~~~~~
          |             |
          |             const void **
    isort.c:9:23: note: expected ‘void **’ but argument is of type ‘const void **’
        9 | void genSort(Element *arrToSort, int arrSize, int (*less)(ConstElement, ConstElement))
          |              ~~~~~~~~~^~~~~~~~~
    The correct code is:
    Code:
    #include <stdio.h>
    #include <assert.h>
    
    
    typedef void* Element;
    typedef const void* ConstElement;
    
    /* !!!!!!!!!!!! CHANGED to Element *arrToSort */
    void genSort(Element *arrToSort, int arrSize, int (*less)(ConstElement, ConstElement))
    {
        int numOfPasses;
        if (arrSize < 2)
            return;
        for (numOfPasses = 0 ; numOfPasses < arrSize ; ++numOfPasses) {
            int it;
            for (it = 0 ; it < arrSize - 1 ; ++it) {
                if (less(arrToSort[it+1], arrToSort[it]))
                {
                    Element temp = arrToSort[it+1];
                    arrToSort[it+1] = arrToSort[it];
                    arrToSort[it] = temp;
                }
            }
        }
    }
    
    
    int IntLess(ConstElement a, ConstElement b) {
        int *i1 = (int*) a;
        int *i2 = (int*) b;
        assert(i1 != NULL && i2 != NULL);
        return (*i1 < *i2);
    }
    
    
    int main() {
        int A[5] = {5, 6, 2, 23, 9};
        int tempi;
        Element arrToSort[5];   /* !!!!!!!!!!!!!! CHANGED */
        for (tempi = 0 ; tempi < 5 ; ++tempi)
            arrToSort[tempi] = A + tempi;
        genSort(arrToSort, 5, &IntLess);
        /* will print 2 */
        printf("arrToSort[0] = %d\n", *((int *) arrToSort[0]));
        return 0;
    }

    Edit: I have to ask, is this an actual school assignment or a free online course? Because that "correct" answer cannot be correct if it doesn't even compile :/
    Last edited by Hodor; 12-04-2019 at 01:56 PM.

  11. #11
    Registered User
    Join Date
    Nov 2019
    Posts
    135
    @Hodor -
    Thank you.

    But, what's the problem actually with the constant option?
    The const is applied on the data type (void - which is int in this case) - so, what's the problem with the swaps? You are assigning here the pointers which aren't constant to my understanding:
    Code:
    arrToSort[it+1] = arrToSort[it];
    So, why is the constant problematic here?

    And, to your other question - it's a course in the university. Actually, this is one of a tonne of questions we received to exercise towards the final exam in C this Friday...

    The real serious exercises, which are without these silly mistakes are given every week as a project. For example, I am given now a project to be submitted at the next week - which is dealing with Red-Black Trees, function pointers, some generic programming, using makefiles and libraries - like go and implement some insertion of a generic element to a Red-Black tree... In brief - build a Red Black Tree data structure.

  12. #12
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,646
    Quote Originally Posted by HelpMeC View Post
    @Hodor -
    Thank you.

    But, what's the problem actually with the constant option?
    The const is applied on the data type (void - which is int in this case) - so, what's the problem with the swaps? You are assigning here the pointers which aren't constant to my understanding:
    Code:
    arrToSort[it+1] = arrToSort[it];
    So, why is the constant problematic here?

    And, to your other question - it's a course in the university. Actually, this is one of a tonne of questions we received to exercise towards the final exam in C this Friday...

    The real serious exercises, which are without these silly mistakes are given every week as a project. For example, I am given now a project to be submitted at the next week - which is dealing with Red-Black Trees, function pointers, some generic programming, using makefiles and libraries - like go and implement some insertion of a generic element to a Red-Black tree... In brief - build a Red Black Tree data structure.

    The first error is the most serious (the function prototype being wrong) because you need to pass a ** and how they have it it's a *.
    As for the const problem, well it's not really a problem in this case. But, really everything should be const qualified if some part of it is. Discarding constness is not good programming practice. A better solution (than what I previously pasted) would be to change everything to be const qualified instead of discarding the qualification (it was said to be const, presumably, for a good reason)

    Code:
    void genSort(ConstElement *arrToSort, int arrSize, int (*less)(ConstElement, ConstElement))  /* Line 9 */
    /* ... */
        ConstElement temp = arrToSort[it+1]; /* line 19 */
    Also, this is definitely what Knuth calls "straight insertion sort" (Knuth, TAOCP Vol. 3, pp. 80-81). Bubble sort is slightly different (Knuth, TAOCP, Vol. 3, p. 107) but when optimised (to finish early if no swaps occur) it's almost (but not quite) the same as bubble sort. But really, teachers should write correct programs and call algorithms by their correct names.
    Last edited by Hodor; 12-04-2019 at 02:25 PM.

  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,389
    Quote Originally Posted by Hodor
    Looks like insertion sort to me as well. According to Knuth (Vol 3) and Wikipedia the defining feature of insertion sort is that the terminating condition is when no swaps have occurred.
    That's interesting: I've understood the defining feature of insertion sort as being "insert in relative position", whereas bubble sort's would be "always swap adjacent elements if out of order". That there is no termination as soon as no more swaps need to be performed should merely make it a more inefficient bubble sort, not turn it into insertion 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

  14. #14
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,646
    Quote Originally Posted by laserlight View Post
    That's interesting: I've understood the defining feature of insertion sort as being "insert in relative position", whereas bubble sort's would be "always swap adjacent elements if out of order". That there is no termination as soon as no more swaps need to be performed should merely make it a more inefficient bubble sort, not turn it into insertion sort.

    I've seen insertion sort presented as bubble sort in more than one book, but they really are subtly different. All my more technical books (as opposed to introductory books) make the same distinction as Knuth

    Edit: I had posted photos from Knuth TAOCP Vol 3 (pp. 80-81, p. 107) above showing the two algorithms as printed, but there was no point because the difference is reflected in the pseudocode on the wikipedia links given above anyway, and the wikipedia pseudocode is probably easier to read if you're not used to reading Knuth. I couldn't work out how to remove the images from the previous message so I deleted the entire message
    Last edited by Hodor; 12-04-2019 at 02:48 PM.

  15. #15
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,389
    Quote Originally Posted by Hodor View Post
    I've seen insertion sort presented as bubble sort in more than one book, but they really are subtly different. All my more technical books (as opposed to introductory books) make the same distinction as Knuth
    Wait, I just realised that you wrote: "According to Knuth (Vol 3) and Wikipedia the defining feature of insertion sort is that the terminating condition is when no swaps have occurred."

    That would mean that this is not insertion sort: it doesn't necessarily stop when no more swaps have occurred.

    Looking at the Wikipedia articles though, the bubble sort one states: "repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted." So, if we say that the second criterion is equally as important as the first, then indeed this is not bubble sort. Admittedly this is consistent with the definition from DADS: "Sort by comparing each adjacent pair of items in a list in turn, swapping the items if necessary, and repeating the pass through the list until no swaps are done."

    But, the entry for insertion sort states: "Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain." This is a bit more specific (practically an implementation outline) than the DADS version: "Sort by repeatedly taking the next item and inserting it into the final data structure in its proper order with respect to items already inserted."

    But either way they specify "one element" or "next element", whereas the algorithm in post #1 doesn't consider one element at a time: it moves all out of order elements closer into position in each inner loop iteration.

    Consequently, I think regarding this as a more inefficient bubble sort makes more sense than regarding it as an insertion sort. Of course, it isn't a 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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with easy Array and bubble sort code
    By Dkman in forum C Programming
    Replies: 2
    Last Post: 01-03-2017, 08:32 AM
  2. Bubble Sort Code :(
    By irishfeeney92 in forum C Programming
    Replies: 22
    Last Post: 05-03-2011, 07:22 AM
  3. Bubble Sort Code Problem...
    By h4rrison.james in forum C Programming
    Replies: 7
    Last Post: 01-22-2009, 07:43 AM
  4. Problem with Bubble Sort code
    By lisa1234 in forum C++ Programming
    Replies: 7
    Last Post: 01-13-2004, 03:40 PM

Tags for this Thread