Array Sorting in C++

Question

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.

• Morwenn: std::sort(arr, arr+count); with std::sort from the header <algorithm>. It works with any container of any comparable value.
• Morwenn: Then std::unique(arr, arr+count) to get rid of the duplicate elements.
• chqrlie: 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.
• chqrlie: The return statement in compare() can be simplified as: return (a > b) - (a < b);
• Loki Astari: 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.

Answer 1

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.

• T145: 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)
• rolfl: Please see What you may and may not do after receiving answers
• rolfl: You're really welcome. Pleased it made sense.

Answer 2

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;
}

• AShelly: Agree. Also the input loop should test that count<100, and 100 should be a named constant.
• chqrlie: 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.

Answer 3

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; });

• Bill Barry: 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.
• T145: Myself likewise :)