|The method I described about comparing the first and last is surprisingly fast.|
Can I ask what it is being compared with to make you suggest that it is fast? Did you compare it to
? I would love to see the results if you have. Note that one would have compare using at least
items to make a decent comparison. In tests that I have done in the past, I usually have
items or more. More about that below.
So your algorithm is basically a bubble sort, which is one of the worst performing sorts. I am not sure why you think you can improve on this very bad algorithm compared to what is routinely used.
|..... that big arrays like 1000 elements or more .....|
Are you aware that an array with
elements is actually quite small ? One million
ints is about 4MB - which is still small, if one is using an average machine with 8 or 16 GB of ram. One billion
ints is about 4 GB, is still not a stretch for the average machine. Even if one doubled that because of using 64 bit values like
, then doubled it again if it required as much ram to do the sorting as it does to store the data, we still only get to 16GB ram. That is too much for the average machine, but 1 billion is 6 orders of magnitude more then
I still think that the premise of your question is wrong: swapping / moving with pointers is not a slow operation. Swapping large objects by value is expensive, but C++ coders are always trying to avoid that.
In the past, I was comparing the performance of sorting
. With some advice from JLBorges
, I discovered that
could initialise and
sort 1 million ints faster than
could initialise 1 million ints. I had to go up to 8 million before I could get
to be faster. But
uses hashing, so if one inserts more data, then the hash function has to be recomputed for all the data again. So
was the overall winner.
The other things to consider: move semantics ; concurrency (aka threading) ; and cache effects. These can greatly improve running times. But the easiest thing to do is testing: get some hard data. Make sure you have a control like using std::sort for example to compare against.
I am sorry if I sound a bit harsh, but none of what you are saying makes any sense to me. I hope that i have pointed out some things that you may not have been aware of. Good Luck, and I look forward to your reply :+)