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

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:

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.

Originally Posted by flp1969

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.

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.

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.

Originally Posted by HelpMeC

@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 :/

Originally Posted by HelpMeC

@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.

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.

Originally Posted by laserlight

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

Originally Posted by Hodor

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.