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
– crashmstr, Commented Aug 13, 2015 at 15:50
Related: How to find the 'sizeof'(a pointer pointing to an array)? — crashmstr
– crashmstr, Commented Aug 13, 2015 at 15:54
Alternatively, you can use std::vector<int> (dynamic size) or std::array<int, Size> (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 sizeofto determine its size and use Paul Roub's answer then). — Caninonos
– Caninonos, Commented Aug 13, 2015 at 15:58

Paul Roub · Accepted Answer · 2015-08-13 15:52:26Z

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, 2015 at 15:52

Paul Roub

36.5k27 gold badges88 silver badges95 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

crush Over a year ago

How does BubbleSort(int a[]) differ from say, BubbleSort(const int* a)? Is there any difference? Would the latter be more readable?

Paul Roub Over a year ago

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.

michel Over a year ago

I still get an error: "redefinition of 'len' with a different type: 'int' vs 'size_t"

Paul Roub Over a year ago

int len = ARRAY_SIZE(a); (inside the function) is now both redundant and incorrect. Remove it.

Lorenzo Gatti · Accepted Answer · 2015-08-13 16:03:01Z

1

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

answered Aug 13, 2015 at 16:03

Lorenzo Gatti

1,2901 gold badge10 silver badges15 bronze badges

Comments

Barry · Accepted Answer · 2015-08-13 16:27:27Z

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

Collectives™ on Stack Overflow

c++ sorting algorithm difficulty with array length

3 Answers 3

4 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related