Home > Back-end >  I need to see if an array is sorted using pointers on the beginning and the end
I need to see if an array is sorted using pointers on the beginning and the end

Time:12-27

Implement isSorted. The function must return true if a floating-point array is sorted in ascending order. When called, pBegin points to the first element of the array and pEnd points to the last.

#include <iostream>
#include <string>
#include <iomanip>
using namespace std;
//
//
bool isSorted(double *pBegin,   double *pEnd){
     int size=pEnd-pBegin;
     int sum=0;
     for(int i =0; i < size; i  ){
         if(pBegin[i] > pBegin[i 1]){
             cout << "false" << endl;
             return false;
         }
     }
    cout << "true" << endl;
    return true;
}
//
// Ändra INTE här nedanför!
//
int main(){
    int size=3;
    double arr[]={-1.2 , 8.3 , 8.4};
    isSorted(&arr[0],&arr[3]);
    return 0;
}

CodePudding user response:

you need to change the boundry check, try this:

for(int i =0; i < size -1; i  ){
    if(pBegin[i] > pBegin[i 1]){
        cout << "false" << endl;
        return false;
    }
}

CodePudding user response:

You are initial statement is wrong:

When called, pBegin points to the first element of the array and pEnd points to the last.

Notice this:

isSorted(&arr[0],&arr[3]);

The element &arr[3] is one beyond the end of the array. So you have written code based on your initial statement and it accesses the 3 element (one beyond the end).

I would point out that in C when passing pointers (iterators) the end is usually one passed the end, so this looks normal. You just have to adjust your isSorted() function so that it does not accesses this element but stops one before.

So your loop should end one before size

     for(int i =0; i < size - 1; i  ){
         //            ^^^^^^^^
         // Note: Normally `size` is correct.
         //       But inside the loop you accesses element `i 1`
         //       So you need to take that into account.
         if(pBegin[i] > pBegin[i 1]){
         //                    ^^^

CodePudding user response:

Rethink how you are solving this

Your instructions are to use pointers:

  • one to the first element in your array,
  • the other to one past the last element.

But then you go and use integer indexing anyway. This won’t fly when you are graded.

The whole point of the exercise is to not use integer indices. You must only use the pointers.

What can I do with pointers?

  • You can dereference a pointer to access an element’s value.
     *begin → first element (element 0) of the array (same as begin[0])

  • You can add one to a pointer to make it point to the next element:
     begin → (now ‘begin‘ points to element 1 of the array)

You can use this knowledge to iterate over the array.

std::cout << *begin << "\n";  // print array[0]

  begin;
std::cout << *begin << "\n";  // print array[1]

  begin;
std::cout << *begin << "\n";  // print array[2]

...and so on...

The question is, how do you know when to stop?
Would the end pointer be able to help me here?

Iterators

This is the concept behind iterators in C . An iterator is just an object that looks and acts like a pointer. It can, in fact, be a pointer.

Said another way, you have been given a pair of iterators for your array of doubles. You use the first to access the elements of the array (to iterate over it). You use the second to know when to stop.

Fencepost errors

As already pointed out, the “end” (or “last”) iterator does not point to the last element — it points to one past the last element. In other words, it is invalid to use *end, since that would attempt to access an element outside the array.

[-1.2] [ 8.3] [ 8.4]
↑                    ↑
begin                end

This always seems to surprise people, but it is the same as if you were using integer indexing. You cannot access element number 3 of a 3-element array. You can access elements at indices 0, 1, and 2. But not 3, since that is past the end of the array.

--0--- --1--- --2--- --3---
[-1.2] [ 8.3] [ 8.4]

Printing output

You should not be printing anything from inside a yes/no function. The function returns a boolean value to the caller, and the caller then gets to decide what to print.

Your main function, then, should look like this:

#include <iostream>
#include <type_traits>  // for std::extent<>

int main(){

    // declare our array and get its length
    double arr[] = {-1.2 , 8.3 , 8.4};
    size_t size = std::extent<decltype(arr)>::value;

    // determine whether the array is sorted
    //   and tell him/her what we learned
    if (isSorted(&arr[0], &arr[size]))
        std::cout << "array is sorted\n";
    else
        std::cout << "array is NOT sorted\n";
}
  • Related