3
\$\begingroup\$

I have this simple implementation for array sorting:

#include <iostream>
#include <stdlib.h>

using namespace std;

// some magic for the sorter
int compare(const void *i, const void *j) {
    int a = *(int *) i, b = *(int *) j;
    return a < b ? -1 : a > b ? 1 : 0;
}

int main() {
    int arr[100], temp = 0, count = 0;

    // reads values into the array (assumed integers as input)
    while (cin >> arr[count++]);
    count--;

    // what sorts the array
    qsort(arr, count, sizeof(int), compare);

    // prints everything but duplicate elements
    for (int i = 0; i < count; i++) {
        bool match = false;
        for (int j = 0; j < i && !match; j++)
            if (arr[i] == arr[j])
                match = true;
        if (!match)
            cout << arr[i];
    }
}

How can it be improved? I'd like to also remove duplicate elements rather than just silently ignoring them too.

\$\endgroup\$
6
  • 4
    \$\begingroup\$ std::sort(arr, arr+count); with std::sort from the header <algorithm>. It works with any container of any comparable value. \$\endgroup\$ Commented Mar 25, 2015 at 16:49
  • 1
    \$\begingroup\$ Then std::unique(arr, arr+count) to get rid of the duplicate elements. \$\endgroup\$ Commented Mar 25, 2015 at 16:51
  • 1
    \$\begingroup\$ Your test for uniqueness is very inefficient. Why not compare arr[i] with arr[i+1] and skip the sequence if equal? Keep trying to do things the hard way, you'll learn more this way. \$\endgroup\$ Commented Mar 25, 2015 at 21:08
  • \$\begingroup\$ The return statement in compare() can be simplified as: return (a > b) - (a < b); \$\endgroup\$ Commented Mar 25, 2015 at 21:11
  • 1
    \$\begingroup\$ Prefer the C++ std::sort much less chance to mess things up and the compiler can check all the type information so no need to use those nasty C cast operations. \$\endgroup\$ Commented Mar 25, 2015 at 22:28

3 Answers 3

Reset to default
8
\$\begingroup\$

You should use your standard libraries when you can. Consider that a std::set already does all the hard work, unique, and sorted values:

#include <iostream>
#include <set>

int main() {
    std::set<int> data;

    // reads values into the set (assumed integers as input)
    int val;
    while (std::cin >> val) {
        data.insert(val);
    }

    for(std::set<int>::iterator iter = data.begin(); iter != data.end(); ++iter) {
        std::cout << (*iter) << "\n";
    }

}

Note though, that the above implementation has horrible handling of issues that may come from invalid input. Still, the entire implementation is significantly simpler than yours.

\$\endgroup\$
3
  • \$\begingroup\$ Yes, but as I've said in my code, I'm not expecting anything other integers. If I end up getting something else, there's something that is significantly wrong about where I'm reading from. Thanks a lot! (My new version based off of this is now in the original post) \$\endgroup\$ Commented Mar 25, 2015 at 20:07
  • 1
    \$\begingroup\$ Please see What you may and may not do after receiving answers \$\endgroup\$ Commented Mar 25, 2015 at 20:09
  • \$\begingroup\$ You're really welcome. Pleased it made sense. \$\endgroup\$ Commented Mar 25, 2015 at 20:09
6
\$\begingroup\$

This would just be a comment but it doesn't all fit...

  1. In compare, you could simply return a-b instead of doing 2 compares.
  2. The print can be done with one pass over the array (O(N)) instead of O(N^2):

...

int i = 0;
int value;
while (i < count) {
    value = arr[i];
    i++;
    while (i < count && value == arr[i]) {
        i++;
    }
    cout << value;
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Agree. Also the input loop should test that count<100, and 100 should be a named constant. \$\endgroup\$ Commented Mar 25, 2015 at 17:34
  • 3
    \$\begingroup\$ Absolutely not! return a-b does not do the job!!! INT_MIN < 1 yet INT_MIN-1 invokes undefined behaviour (at least in C it does) and on CPUs with 2s complement arithmetic, INT_MIN-1 is INT_MAX, a positive value. The trick can only be used with arithmetic types smaller than int. \$\endgroup\$ Commented Mar 25, 2015 at 21:24
5
\$\begingroup\$

100 is a magic number, it should be a constant, let's call it MAX

qsort is the old c way to sort a collection, the c++ way would be to use std::sort. You're using c++11, so you could even replace your compare function with a lambda expression, so your sorting would looks like that. 

sort(arr, arr + MAX, [](int a, int b){ return a < b; });

In that case, you don't really need the lambda expression, because std::sort use the '<' operator by default, so your actual call is

sort(arr, arr + MAX);

You should prefer to use the standard containers such as std::set (which, like rolfl said, does exactly what you want) or std::vector, because it handle so much errors for you (If the use enters more than 100 values, your program wouldn't be valid) and is easier to use.

To find the unique values, you can use std::unique. It need the data to be sorted so you have to call std::sort first With an array, you will need to find the new size, so you can do it like that. If you have trouble understanding that line, please refer to this question 

int size = unique(arr, arr + MAX) - arr;

The nice thing about the standard library is that it have a function for nearly everything, including generating values for a collection. So in your case, if you know that you will always wants 100 values, why don't use the std::generate_n function?

int temp;
generate_n(arr, MAX, [&](){cin >> temp; return temp; });
\$\endgroup\$
2
  • \$\begingroup\$ generate_n -> that's pretty neat. lambda syntax and everything... As someone who does C++ about once every couple years I wish there was better ways to discover all these massive libraries. \$\endgroup\$ Commented Mar 25, 2015 at 21:01
  • \$\begingroup\$ Myself likewise :) \$\endgroup\$ Commented Mar 26, 2015 at 12:32

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.