Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I have to sort a set of 100000 integers as a part of a programming Q. The time limit is pretty restrictive, so I have to use the most time-efficient approach possible.

My current code -

#include<cstdio>
#include<algorithm>
using namespace std;

int main() {
    int n,d[100000],i;
    for(i=0;i<n;++i) {
                     scanf("%d",&d[i]);
    }
    sort(d,d+n);
    ....
}

Would this approach be more efiicient?

int main() {
    int n,d[100000],i;
    for(i=0;i<n;++i) {
                     scanf("%d",&d[i]);
                     sort(d,d+i+1);
    }
    ....
}

What is the most efficient way to sort a large dataset?

Note - Not homework...

share|improve this question
    
I am pretty sure your 2nd approach will be slower - but why don't you just test it? –  Doc Brown Nov 2 '12 at 7:38
    
@DocBrown I did, both are pretty inefficient. However the latter's apparently a bit faster... Strange, yes. –  7Aces Nov 2 '12 at 8:21
1  
let me guess - you are not measuring the speed of the sort, you are measuring the speed of the scanf –  Doc Brown Nov 2 '12 at 11:09
    
How big are the numbers? –  kevin cline Nov 2 '12 at 15:25
1  
@Aces: in that case, just create an array and count the number of occurrences of each value. That will give you linear runtime. –  kevin cline Nov 5 '12 at 19:12
show 3 more comments

1 Answer 1

up vote 3 down vote accepted

For maximum efficiency you only want to do the sort once, so version 2 is definitely not the way to go.

An alternative to just storing the numbers in an array in the order they are read and then sorting, is to use a data structure that will sort itself as each number is added, such as a (red/black) binary tree or a skip list. This will require additional memory for the pointer links between items, but may be faster - only an experiment can determine that.

However, efficiency of any particular sorting algorithm can often depend greatly on the initial order of the items - e.g. already sorted / inverse sorted / random.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.