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…
9
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.
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?
2