0

I have two Arrays of doubles. One Array will be sorted and after this I want to check if every Element of the original Array is still in the sorted Array. I used the find() function of C++ but this pointer only points to the first Element if found, e.g. if you have as original Array {1, 1 ,1 ,1}, the sorted one is {1, 1, 1, 1} but find() only points to the first Element.

Do I really need to loop through the original Array and count the number of times the Elements occure and then loop through the sorted Array and do the same?

StarFighter
  • 69
  • 1
  • 8
  • Sorting will never remove elements from the array. If you sort every element that was in the original array will be in the sorted array. – André Puel Apr 23 '14 at 12:31
  • Ok, I'll bite. Why would simply sorting a sequence somehow remove elements? Regardless, [`std::upper_bound`](http://en.cppreference.com/w/cpp/algorithm/upper_bound) and [`std::unique`](http://en.cppreference.com/w/cpp/algorithm/unique) may be of some value to you. – WhozCraig Apr 23 '14 at 12:32
  • @AndréPuel, you could always have a defect in your sort. I took this to be a kind of sanity check on a sort that was written by hand rather than using a standard library sort. – Richard Chambers Apr 23 '14 at 12:33
  • @RichardChambers If you have a defect in your sort you will have to iterate over all elements, because you can not consider them sorted. – André Puel Apr 23 '14 at 12:36
  • Richard is right, I'm using a self-written sort-fuction and now I want to check that the sorted Array is really sorted and that I dont lose any of my Elements from the original Array. – StarFighter Apr 23 '14 at 12:38

2 Answers2

2

Since you just want to check if your array was sorted correctly, you can just sort the other array with std::sort which works correctly for sure and then compare the results:

your_sort(first_array);
std::sort(second_array.begin(),second_array.end());

bool sort_worked = std::equal(first_array.begin(),first_array.end(),
        second_array.begin());

Just in case you did not know:

Every standard library-container has the begin() and end() member functions. You should always use them, use std::vector as your default data structure and another standard container iff you have a good reason to do so. Do not use C-style arrays.

Baum mit Augen
  • 49,044
  • 25
  • 144
  • 182
  • If the person is using standard C-style arrays rather than Standard Library containers, here is [How to use std::sort to sort an array in C++](http://stackoverflow.com/questions/5897319/how-to-use-stdsort-to-sort-an-array-in-c) with an answer that provides for both C++11 and writing your own adapter for earlier compilers. – Richard Chambers Apr 23 '14 at 14:47
0

The find() function returns a pointer to the first occurence of the desired element within a range.

    std::find(first, last, value_to_be_searched)

if the element was not found it returns 'last'. You can loop through your first array and just check that for each element the find function returns something different from 'last' when called on your second array.

thiout_p
  • 717
  • 11
  • 15