Sorting Algorithm
Author
Hi! I have an array of integers and it can be up to 10000 integers in it. I have to proccess with all of those integers one by one BUT starting from the smallest and go to the biggest.
For now I am scanning through all of the array and finding the smallest and proccessing it then I am scanning again through all of the array and finding the smallest... till the end of the array.
also I am doing this code for some kind of competition and it wants me to do it in 1 seconds but for my programm it takes about 1.3 seconds.
What I think is;
Sorting the array for ONE time and saving it to a linked list and then proccess that linked list quickly.
But as I searched I have found many sorting algorithms.. Which I should use for a 10000 integer-array?
And one last thing, do arrays that contain 10000 variable matter for our "high-speed" computers?It occurs to me that it is a very huge number but sometimes computers can do a lot better :o
What I asked was just a sorting algorithm but I explained it in a detailed way.
Thanks, I am waiting for your replies :)
Answer: It depends. If you're allowed to use whatever libraries your language gives you, then use the standard sort function. C++ has std::sort, for example.
If not, it sounds like this is a one-time need, and the program doesn't need to be that fast, so the easiest algorithms to implement are insertion sort or selection sort. You can write selection sort in about 8 lines of easy to read code, although from your description of how you're handling the problem now, it's not going to be significantly faster. (It will be faster by some small constant, though).
10,000 numbers is basically nothing. You should be able to sort (or scan) that faster than you can react. I'd expect sorting 10k numbers to take on the order of 1 millisecond, at worst. (This obviously depends on lots of factors.)
Finally, if you already have an array of numbers, and you sort them so you can process them in order... why bother putting them in a linked list? Why not just leave them in the array and process them there? For the problem that you're describing, it sounds like the linked list would just make things slower.
Edit: Yeah, I didn't trust my original time guess (it's much easier to discuss relative performance than absolute numbers). It turns out I was pretty accurate. I threw together a tiny C# program to generate 10,000 random integers, then I sorted it using Array.Sort. My (not very good) laptop completes the sort in about 1.5 milliseconds. (That's 0.0015 seconds).
If not, it sounds like this is a one-time need, and the program doesn't need to be that fast, so the easiest algorithms to implement are insertion sort or selection sort. You can write selection sort in about 8 lines of easy to read code, although from your description of how you're handling the problem now, it's not going to be significantly faster. (It will be faster by some small constant, though).
10,000 numbers is basically nothing. You should be able to sort (or scan) that faster than you can react. I'd expect sorting 10k numbers to take on the order of 1 millisecond, at worst. (This obviously depends on lots of factors.)
Finally, if you already have an array of numbers, and you sort them so you can process them in order... why bother putting them in a linked list? Why not just leave them in the array and process them there? For the problem that you're describing, it sounds like the linked list would just make things slower.
Edit: Yeah, I didn't trust my original time guess (it's much easier to discuss relative performance than absolute numbers). It turns out I was pretty accurate. I threw together a tiny C# program to generate 10,000 random integers, then I sorted it using Array.Sort. My (not very good) laptop completes the sort in about 1.5 milliseconds. (That's 0.0015 seconds).
Your best bet for a large array is a selection/linear sort. It finds the lowest number in the array and places it in the first position. It is repeated until the array is sorted.
To run it you will need to find the smallest number: FindSmallest(), swap the two values: Swap() and display the array: DisplayNumbers()
To run it you will need to find the smallest number: FindSmallest(), swap the two values: Swap() and display the array: DisplayNumbers()
for (CurrentPos = 0; CurrentPos < (MAX_NUMS - 1); CurrentPos++){ DisplayNums( Number,MAX_NUMS ); LowestIndex=FindLowestIndex( Number,CurrentPos + 1,MAX_NUMS - 1; if (Number[LowestIndex] < Number[CurrentPos]) { Swap(Number[LowestIndex],Number[CurrentPos]); }}
I'd probably just radix sort the integers and be done with it.
For a very rough estimation of speed, the floating point radix sort I wrote in C# takes on average about 2.7 milliseconds to sort 10000 random floats and it is far from optimized. An integer radix sort should perform quite a bit better than that.
Regards,
ViLiO
For a very rough estimation of speed, the floating point radix sort I wrote in C# takes on average about 2.7 milliseconds to sort 10000 random floats and it is far from optimized. An integer radix sort should perform quite a bit better than that.
Regards,
ViLiO
Without boring you with complexities and big-o notation:
Quick-sort is considered one of the fastest sorting algorithms. Although it's usually implemented recursively so the number of recursions is limited by the call stack depth.
Heap-sort is quite fast also, almost on-par with quick-sort, but it isn't limited by the stack meaning it can run on much larger data sets than a typical quick-sort implementation.
Merge-sort is also one of the better algorithms, particularly popular when you only have sequential access (like a linked-list). It requires more memory than a heap-sort but it has the advantage of being a stable sort - although this doesn't seem to matter in your case.
Since you mentioned integers, you can also look into a Radix-sort, a lexicographical sort, which may be faster than all of the above, but then again maybe not [rolleyes].
On the off-chance that you're using C++ then you can just use std::sort, a typical implementation is a mix between quick-sort, heap-sort and insertion-sort making it very efficient and not call stack limited.
Quick-sort is considered one of the fastest sorting algorithms. Although it's usually implemented recursively so the number of recursions is limited by the call stack depth.
Heap-sort is quite fast also, almost on-par with quick-sort, but it isn't limited by the stack meaning it can run on much larger data sets than a typical quick-sort implementation.
Merge-sort is also one of the better algorithms, particularly popular when you only have sequential access (like a linked-list). It requires more memory than a heap-sort but it has the advantage of being a stable sort - although this doesn't seem to matter in your case.
Since you mentioned integers, you can also look into a Radix-sort, a lexicographical sort, which may be faster than all of the above, but then again maybe not [rolleyes].
On the off-chance that you're using C++ then you can just use std::sort, a typical implementation is a mix between quick-sort, heap-sort and insertion-sort making it very efficient and not call stack limited.
Author
Quote:Original post by osmanb
Finally, if you already have an array of numbers, and you sort them so you can process them in order... why bother putting them in a linked list? Why not just leave them in the array and process them there? For the problem that you're describing, it sounds like the linked list would just make things slower.
I thought that swapping the values in an array was much much slower but then(now) I remembered that it was "adding new things" which caused problems.I won't bother the linked lists now.
Thanks for your answers I'll post again when I finished it or when I have further questions.
Author
Quote:Original post by dmatter
On the off-chance that you're using C++ then you can just use std::sort, a typical implementation is a mix between quick-sort, heap-sort and insertion-sort hence making it very efficient.
I have never heard of that std::sort thing.. I'll look thanks !
I had written a bi-directional linked list (left and right node pointers) that I needed sorted. After considering some algorithms, I realized that my list had something in common with binary trees (which are sorted by nature); they both use left and right node pointers. So, I converted all the pointers in my list to a binary tree structure and back again to a list. The result: a sorted linked list. I also wrote a two-pass unsort algorithm to avoid the worst-case scenario of sorting a sorted list (which had about a 90 minute run time). So, the complexity of this algorition was O(2n + n log n) and sorted 250,000 objects in 1000 to 2000 ms on a P4 1.4GHz.
The algorithm used recursion to convert to a tree structure, then recursed the tree returning list "splices" which it would link together and ultimately return one large splice (the entire list).
Another implementation you might want to consider is the red-black tree which achieves O(n log n) in all cases.
The algorithm used recursion to convert to a tree structure, then recursed the tree returning list "splices" which it would link together and ultimately return one large splice (the entire list).
Another implementation you might want to consider is the red-black tree which achieves O(n log n) in all cases.
Quote:Original post by coderx75
Another implementation you might want to consider is the red-black tree which achieves O(n log n) in all cases.
IIRC a std::set is usually implemented as a red-black balanced binary tree; for the OP it might be worth considering using this container as opposed to sorting an array.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
