c++ sorting algorithm difficulty with array length

Question

I am having trouble coding a simple Bubblesort algorithm in C++ on Xcode. A particular problem is getting the length of the array, and I get an error saying "sizeof on array function will return size of int* instead of int[]." What does this mean? I tried to test the algorithm on the array {33,60,55,8,26} but am puzzled by how to construct an array length function.

  #include <iostream>
#include <array>
using namespace std;
#define ARRAY_SIZE(array) (sizeof((array))/sizeof((array[0])))

void swap(int n1, int n2){
    int temp = n1;
        n1 = n2;
        n2 = temp;
}
int count(int a[]){
    int len=0;
    for(int i = 0; i <= 20; i++){
        if(a[i] >= 0){
            len++; //len=len+1
        }
    }
    return len;
}
template <size_t N>
void BubbleSort( int a[], size_t len ){
     for(int i = 0;i <= len;i++){
         if(a[i] > a[i+1]){
             swap(a[i],a[i+1]);
         }
     }
 }
void printr(int arr[]){
    for(int i = 0; i <= len; i++){
        cout<<arr[i]<<"\n";
    }
}
int main(int argc, const char * argv[]) {
    int arr[] = {33,60,55,8,26};
    BubbleSort(arr, ARRAY_SIZE(arr));
    printr(arr);
    return 0;
}

I know there have been similar questions... but basically just pass the array size to the function (or better yet, use C++ container classes). — crashmstr, Aug 13 '15 at 15:50
Related: [How to find the 'sizeof'(a pointer pointing to an array)?](http://stackoverflow.com/questions/492384/how-to-find-the-sizeofa-pointer-pointing-to-an-array) — crashmstr, Aug 13 '15 at 15:54
Alternatively, you can use [`std::vector`](http://en.cppreference.com/w/cpp/container/vector) (dynamic size) or [`std::array`](http://en.cppreference.com/w/cpp/container/array) (fixed size) which both provide a `size` method (the container classes crashmstr talks about, at least, the two i can think of). Although passing a classic array and its size is perfectly fine (but don't use `sizeof`to determine its size and use Paul Roub's answer then). — Caninonos, Aug 13 '15 at 15:58
possible duplicate of [Length of array in function argument](http://stackoverflow.com/questions/8269048/length-of-array-in-function-argument) — phuclv, Aug 13 '15 at 16:37

score 2 · Answer 1 · answered Aug 13 '15 at 15:52

2

At this point:

void BubbleSort( int a[] ){

the size of a[] is unknown. It's an int *, for all intents and purposes. You need to calculate the known length of the array, and pass it in, e.g.

void BubbleSort( int a[], size_t len ){

called as:

int arr[] = {33,60,55,8,26};
BubbleSort(arr, ARRAY_SIZE(arr));

answered Aug 13 '15 at 15:52

Paul Roub

36,322
27
84
93

How does `BubbleSort(int a[])` differ from say, `BubbleSort(const int* a)`? Is there any difference? Would the latter be more readable? – crush Aug 13 '15 at 16:03
The rest of the code wouldn't change. In this case, it's really a style choice. For the purposes of this answer, I didn't want to change more code than strictly necessary. – Paul Roub Aug 13 '15 at 16:05
I still get an error: "redefinition of 'len' with a different type: 'int' vs 'size_t" – michel Aug 13 '15 at 16:41
`int len = ARRAY_SIZE(a);` (inside the function) is now both redundant *and* incorrect. Remove it. – Paul Roub Aug 13 '15 at 17:07

score 1 · Answer 2 · answered Aug 13 '15 at 16:03

#define ARRAY_SIZE(array) (sizeof((array))/sizeof((array[0])))

When applied to an int[], sizeof(array[0]) becomes sizeof(int), but sizeof(array) becomes sizeof(int*) (which is the same as sizeof(int[])). Array length does not exist: you need to store it separately.

You should use the std::vector<> container and the std::sort function from the standard library.

By the way, the BubbleSort function, even if it had a valid value of len (say, as another function parameter), is wrong. Try sorting {4,3,2,1}: you need two nested loops.

score 0 · Answer 3 · answered Aug 13 '15 at 16:27

This function, and similar ones from your example:

void BubbleSort(int a[])

are exactly equivalent to having defined them as:

void BubbleSort(int* a)

You're just taking a pointer. You cannot determine the size of an array from just a pointer - there's insufficient information there. The C approach would be to additionally pass in the size everywhere:

void BubbleSort(int* a, size_t len)

But in C++, we can do one better by actually deducing the array size:

template <size_t N>
void BubbleSort(int (&a)[N]) // N is the length of the array

Though even better would be to use a std::vector, which will make pretty much everything easier to deal with:

void BubbleSort(const std::vector<int>& a) // a.size() is the length

c++ sorting algorithm difficulty with array length

3 Answers3