Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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
3  
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
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
1  
Did you write the sort function? If in your experience both methods are equally slow then your sort is at least O(n^2). It doesn't look efficient. You should use the standard sort from the C library. – Florian F Nov 26 '15 at 15:44
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

If you want to sort time-efficient and it is guaranteed that your elements are numbers, then go for Radix-Sort. It is sorting your Dataset in O(a*n), a is the length of the longest/biggest number. 10 would get you a=2, 200 would get you a=3, 2*10^(100) would get you a=1000 and so on.

Quicksort can sort in O(log(n)*n) what is good, but can suck and be as bad as Bubblesort and sort your Dataset in Theta(n²).

Can you tell us how much time you have to sort it, or how much time you have in general?

share|improve this answer
3  
The OP posted this question in November of 2012. I'm fairly sure the question, constraints, and issues but memories in the past. Asking for clarification on them is likely not going to come up with any additional information. – user40980 Dec 24 '15 at 21:07
    
Ouh, just have seen it on the front on the App.... Well, sorry for that – Sparkay Dec 24 '15 at 21:09

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.